Stack applications: parenthesis matching; infix → postfix/prefix conversion; postfix evaluation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Push A, B; pop; push C; pop; pop. Output order? from Lesson 3.2.1
• What is the order of growth of a single loop over n items? from Lesson 2.2
• Which binds tighter in C: * or +? Which way does - associate? from Lesson 1.1.2

1 · The Hook

🎣

A spreadsheet must evaluate 3 + 4 * 2 correctly (11, not 14), handle brackets nested ten deep, and report (a + b] as an error. Doing this directly with precedence rules is fiddly. Two stack-based tricks make it mechanical: rewrite the expression so operators come after their operands, then evaluate it with one left-to-right scan.

2 · Predict First

🤔

Rewrite a + b * c - d so that each operator comes right after its two operands (no brackets needed). Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

a b c * + d -. b * c is formed first (b c *), added to a (a … +), and d is subtracted last. This is postfix notation.

Bracket matching

Scan left to right. Push every opening bracket. On a closing bracket, the top of the stack must be the matching opener: pop it; otherwise (or if the stack is empty) the expression is unbalanced. At the end the stack must be empty.

int matches(const char *s)
{
    char st[50];
    int top = -1;
    for (; *s; s++) {
        if (*s == '(' || *s == '[' || *s == '{')
            st[++top] = *s;
        else if (*s == ')' || *s == ']' || *s == '}') {
            char want = (*s == ')') ? '(' : (*s == ']') ? '[' : '{';
            if (top == -1 || st[top] != want)
                return 0;
            top--;
        }
    }
    return top == -1;
}

int main(void)
{
    printf("%d %d %d %d\n", matches("{[()()]}"), matches("([)]"), matches("(()"), matches("a*(b+c)"));
    return 0;
}

Output

1 0 0 1

Infix, postfix, prefix

Infix puts the operator between its operands (a + b) and needs precedence and brackets. Postfix (reverse Polish) puts it after (a b +); prefix (Polish) before (+ a b). Postfix and prefix never need brackets or precedence rules: the order of the symbols alone fixes the meaning.

Infix → postfix with an operator stack

Scan the infix expression left to right:

• Operand → append to the output.
• ( → push.
• ) → pop operators to the output until (; discard both brackets.
• Operator o → while the top is an operator with higher precedence, or equal precedence and o is left-associative, pop it to the output; then push o.
• At the end, pop everything to the output.

Precedence: ^ (power, right-associative) > * / % > + −. Right-associativity means a ^ b ^ c = a ^ (b ^ c), so an incoming ^ does not pop an equal ^.

Infix → prefix

One reliable method: reverse the infix expression, swap ( and ), convert to postfix (popping an equal-precedence operator only if it is right-associative), then reverse the result. Or simply place each operator before its two operand groups, working from the innermost bracket outwards: (a + b) * c − d / e → - * + a b c / d e.

Evaluating postfix

Scan left to right with a value stack. Operand → push. Operator → pop the right operand first, then the left, apply, push the result. The final value is the only item left.

int st[50], top = -1;
void push(int x) { st[++top] = x; }
int pop(void) { return st[top--]; }

int evalPostfix(const char *e)
{
    int a, b;
    for (; *e; e++) {
        if (*e >= '0' && *e <= '9') { push(*e - '0'); continue; }
        b = pop();                 /* right operand comes off first */
        a = pop();
        if (*e == '+') push(a + b);
        else if (*e == '-') push(a - b);
        else if (*e == '*') push(a * b);
        else if (*e == '/') push(a / b);
    }
    return pop();
}

int main(void)
{
    printf("%d %d\n", evalPostfix("534*+2-"), evalPostfix("623+-382/+*"));
    return 0;
}

Output

15 7

Order matters for − and /: for a b − the first pop gives b.

4 · Visual

Infix → postfix for a + b * ( c ^ d - e ) ^ ( f + g * h ) - i (computed): a b c d ^ e - f g h * + ^ * + i -.

Evaluating 8 2 3 ^ / 2 3 * + 5 1 * -

token  action                        stack
8      push                          8
2      push                          8 2
3      push                          8 2 3        <- deepest: 3 values
^      pop 3, pop 2, push 2^3 = 8    8 8
/      pop 8, pop 8, push 8/8 = 1    1
2 3    push, push                    1 2 3
*      push 2*3 = 6                  1 6
+      push 1+6 = 7                  7
5 1 *  push 5, 1, then 5*1 = 5       7 5
-      push 7-5 = 2                  2   -> result 2

Operands wait on the stack until their operator arrives.

5 · Worked Examples

Example 1 Easy

Convert (a + b) * (c - d) / e to postfix.

Solution

Brackets first: a b + and c d −; then * (left to right with /): a b + c d − *; then / e: a b + c d - * e /.

Example 2 Medium

Evaluate the postfix expression 6 2 3 + - 3 8 2 / + *. What is the largest number of values on the stack at once?

Solution

6 (2 3 +) − = 6 − 5 = 1. Then 3 (8 2 /) + = 3 + 4 = 7. Then 1 × 7 = 7. The stack reaches 4 values when it holds 1, 3, 8, 2.

Example 3 GATE

Convert a + b * (c ^ d - e) ^ (f + g * h) - i to postfix.

Solution

Follow the table in the Visual section. Key moments: ^ inside the first bracket waits for d; at ) the stack releases ^ and −; the second ^ after ) is pushed on top of * because ^ binds tighter; at the final − everything above + is popped. Result: a b c d ^ e - f g h * + ^ * + i -.

6 · GATE Traps

⚠️

• In postfix evaluation the first pop is the right operand: a b − is a − b.
• ^ is right-associative: a ^ b ^ c → a b c ^ ^, not a b ^ c ^.
• Equal-precedence left-associative operators pop each other: a − b − c → a b − c −.
• A closing bracket pops up to and including the matching opening bracket; brackets never reach the output.
• Bracket matching fails both on a wrong opener and on leftover openers at the end.

8 · Memory Hook

🧠

“Operands go straight out; operators wait on a stack by rank.” A higher rank cuts in line; an equal rank waits its turn (unless it is ^, which stacks up to the right).

9 · Connect the Dots

Lesson 3.2.1 built a stack; this lesson used it to match brackets, convert expressions and evaluate them. Stacks impose an order on how items leave. Next lesson answers: if numbers 1, 2, 3, … arrive in order and pass through a stack, which output orders are possible, and how many are there?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markPostfix

The postfix form of a * (b + c) - d is:

• (A) - * a + b c d
• (B) a b + c * d -
• (C) a b c + * d -
• (D) a b c * + d -

Q2NAT1 markEvaluate

What value does evalPostfix("534*+2-") from the lesson return?

Numerical answer: ________

Q3MCQ2 marksPrefix

The prefix form of (a + b) * c - d / e is:

• (A) a b + c * d e / -
• (B) - + a b * c / d e
• (C) - * + a b c / d e
• (D) * + a b - c / d e

Q4NAT2 marksStack depth

While evaluating 8 2 3 ^ / 2 3 * + 5 1 * -, what is the largest number of values on the stack at once?

Numerical answer: ________

Q5MSQ1 markBrackets

Which strings are balanced?

• (A) ([)]
• (B) (()
• (C) ()[]{}
• (D) {[()()]}

11 · Rule Card

• Brackets: push openers; closer must match the top; empty at the end.
• Postfix: operand → output; ( push; ) pop to (; operator pops higher (or equal, if left-assoc) then pushes; end pops all.
• Precedence ^ > * / % > + −; ^ right-associative.
• Prefix: reverse, swap brackets, convert, reverse — or place operators before their operands from inside out.
• Evaluate postfix: operand push; operator pops right then left, pushes result.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

bracket matchinginfixpostfix (reverse Polish)prefix (Polish)operator stackvalue stackright-associative ^

13 · Answer Vault