Expression handling with a stack: parentheses, infix → postfix, postfix evaluation

If you type 2 + 3 * 4 on a calculator you get 14, not 20. How does the machine apply the precedence rules? The answer: two stack algorithms. First it converts the expression to a parenthesis-free form (postfix), then it evaluates that form in a single left-to-right pass. The same stack idea is used for parenthesis matching in editors. The exam has three question types: is it balanced, convert to postfix (often with a stack table), evaluate the postfix.

Golden rules:

1. The last parenthesis opened must be the first closed. A stack checks exactly this.
2. In postfix the order of operands doesn’t change. Only the operators move.
3. A higher-precedence operator is popped from the stack first.
4. When evaluating postfix, the first one popped is the right operand.

Balanced parentheses

The algorithm: read from left to right. Push an opening parenthesis. When a closer arrives, if the stack is empty or the opener on top is not of the same type, it is unbalanced. If the stack is not empty at the end, it is unbalanced.

static boolean isBalanced(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;
            char open = st.pop();
            if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{'))
                return false;
        }
    }
    return st.isEmpty();
}

{[()()]} -> true
([)] -> false
(() -> false
())( -> false
{[]}() -> true
a*(b+c] -> false

The state of the stack after each character (left to right: bottom → top):

input: ( [ ] { } )
(  stack(bottom->top): (
[  stack(bottom->top): ([
]  stack(bottom->top): (
{  stack(bottom->top): ({
}  stack(bottom->top): (
)  stack(bottom->top): (empty)
end: empty -> balanced

PITFALL · Counting is not enough. The check “number of openers = number of closers” says yes for ([)], but the expression is wrong. For )( the counts are equal too but the order is wrong. For type and order, a stack is a must.

Three notations: infix, postfix, prefix

Postfix is also called Reverse Polish Notation (RPN). Its advantage: the precedence information is built into the order, and the machine reads from left to right and evaluates with a single stack.

A quick way to convert by hand: fully parenthesize the expression, then move each operator to the place of its own closing parenthesis. A + B * C → (A + (B * C)) → A B C * +.

The infix → postfix algorithm

An output string and an operator stack are used.

For each token:
  operand (letter/number) → write to the output
  (                       → push onto the stack
  )                       → pop and write to the output until ( is reached; discard (
  operator op             → as long as the stack is not empty, the top is not ( AND
                            [ prec(top) > prec(op)  or  prec(top) == prec(op) and op is left-associative ]
                            pop and write to the output; then push op
At the end: pop what is left in the stack and write it to the output

Java code (for single-letter operands):

static int prec(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': case '%': return 2;
        case '^': return 3;
    }
    return 0;
}

static String toPostfix(String infix) {
    StringBuilder out = new StringBuilder();
    Deque<Character> st = new ArrayDeque<>();
    for (char c : infix.toCharArray()) {
        if (c == ' ') continue;
        if (Character.isLetterOrDigit(c)) out.append(c);
        else if (c == '(') st.push(c);
        else if (c == ')') {
            while (st.peek() != '(') out.append(st.pop());
            st.pop();                        // discard (
        } else {
            while (!st.isEmpty() && st.peek() != '(' &&
                   (prec(st.peek()) > prec(c) || (prec(st.peek()) == prec(c) && c != '^')))
                out.append(st.pop());
            st.push(c);
        }
    }
    while (!st.isEmpty()) out.append(st.pop());
    return out.toString();
}

Worked trace: A + B * C - D / E

token  stack      output
A      (empty)    A
+      +          A
B      +          AB
*      +*         AB
C      +*         ABC
-      -          ABC*+
D      -          ABC*+D
/      -/         ABC*+D
E      -/         ABC*+DE
end    (empty)    ABC*+DE/-

The critical moment is the - token: there is a * on top (precedence 2 > 1), so it is popped. Then there is a + on top (equal precedence, left to right), which is popped too. Only after that is - pushed. When / arrives, the - on top has lower precedence, so it stays.

The program converted a series of expressions:

A+B*C -> ABC*+  maxStack=2
(A+B)*C-D -> AB+C*D-  maxStack=2
A*(B+C)/D-E -> ABC+*D/E-  maxStack=3
A-B-C -> AB-C-  maxStack=1
A^B^C -> ABC^^  maxStack=2
(A+B)*(C-D) -> AB+CD-*  maxStack=3
A+B*(C^D-E)^(F+G*H)-I -> ABCD^E-FGH*+^*+I-  maxStack=6

maxStack is the largest size the stack reached during the conversion; it is sometimes asked on the exam.

PITFALL · The right-associative ^. $A^{B^C}$ means $A^{(B^C)}$ in mathematics. If you pop the ^ on top when an equal-precedence ^ arrives, you write AB^C^, which is $(A^B)^C$. The right answer is ABC^^.

Evaluating a postfix expression

This time the stack holds numbers.

For each token:
  number    → push
  operator  → right = pop(), left = pop(), push(left op right)
At the end a single number remains in the stack: the result

static int evalPostfix(String expr) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String tok : expr.trim().split("\\s+")) {
        if (tok.matches("-?\\d+")) st.push(Integer.parseInt(tok));
        else {
            int right = st.pop();
            int left = st.pop();
            switch (tok) {
                case "+": st.push(left + right); break;
                case "-": st.push(left - right); break;
                case "*": st.push(left * right); break;
                case "/": st.push(left / right); break;
            }
        }
    }
    return st.pop();
}

Worked trace: 4 7 2 - * 3 +

The stack after each token (bottom → top):

4    4
7    4 7
2    4 7 2
-    4 5
*    20
3    20 3
+    23
23

Check: convert the postfix back to infix. 7 2 - = (7 − 2), 4 (7−2) * = 4 · 5, 20 3 + = 23. Correct.

TIP · Operand order. For 9 5 - 2 - the correct result is (9 − 5) − 2 = 2. If you take the pop order the other way, you get first 5 − 9 = −4, then 2 − (−4) = 6. Memorize the sentence “the first one out goes on the right”.

Detecting a faulty expression: if when an operator arrives there aren’t two numbers in the stack, or if more than one number remains at the end, the expression is broken (like 3 +).

Common mistakes

6    6
2    6 2
3    6 2 3
+    6 5
-    1        (6 - 5)
3    1 3
8    1 3 8
2    1 3 8 2
/    1 3 4    (8 / 2)
+    1 7
*    7

static boolean isBalanced(String s) {
    Deque<Character> st = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.isEmpty()) return false;          // extra closer
            char open = st.pop();
            if ((c == ')' && open != '(') ||
                (c == ']' && open != '[') ||
                (c == '}' && open != '{')) return false;   // type mismatch
        }
    }
    return st.isEmpty();                             // is any opener left open
}

static int evalPostfix(String expr) {
    Deque<Integer> st = new ArrayDeque<>();
    for (String tok : expr.trim().split("\\s+")) {
        if (tok.matches("-?\\d+")) {
            st.push(Integer.parseInt(tok));
        } else {
            int right = st.pop();    // RIGHT first
            int left = st.pop();
            switch (tok) {
                case "+": st.push(left + right); break;
                case "-": st.push(left - right); break;
                case "*": st.push(left * right); break;
                case "/": st.push(left / right); break;
            }
        }
    }
    return st.pop();
}

token  stack      output
A      (empty)    A
*      *          A
(      *(         A
B      *(         AB
-      *(-        AB
C      *(-        ABC
)      *          ABC-
+      +          ABC-*
D      +          ABC-*D
end    (empty)    ABC-*D+