Evaluating postfix
expressions with a stack

The operators come after their operands

You're handed an expression like 2 3 1 * + 9 -. The operators sit after the numbers they act on. That's postfix notation. Ordinary math is infix — the operator lives between its operands (2 + 3). Postfix flips it: 2 3 +.

It looks like text to chew through. It isn't. The string is just how the input is written down. The actual question is quieter and more interesting:

Answer that honestly and the stack falls out on its own. You never have to memorize "postfix → stack" — you can rederive it every time.

Precedence is already baked in

In infix, 2 + 3 * 4 needs rules — multiply before add — so it means 2 + (3 * 4) = 14. Postfix writes the execution order out in the open:

When * appears in 2 3 4 * +, the two numbers waiting right in front of it are 3 and 4. Multiply → 12. The expression is now effectively 2 12 + → 14. No parentheses, no precedence table, no expression tree to build. You only need to remember unfinished numbers.

The newest operands get used first

Scan 2 3 1 * + 9 - slowly. You read 2, then 3, then 1 — nothing can happen, so they wait. Then * arrives. Which two numbers does it grab? The two most recent: 3 and 1. Their result, 3, becomes a fresh number that might feed a later operator.

"Most recent in, first one out." That phrase is the definition of a stack: Last In, First Out. So the stack isn't just convenient here. It matches the literal shape of the problem.

Analogies that make LIFO click

Step through the machine

Walk one token at a time through 2 3 1 * + 9 -. Watch numbers get pushed, and watch each operator pop the top two and push its result back. Use Next, or hit Play to autorun.

Notice the last subtraction: the stack holds [5, 9], but the answer is 5 − 9 = −4, not 9 − 5. That ordering trap is the single most common bug — the next section is entirely about it.

The first pop is the right operand

For 5 9 - the operation is 5 - 9. But when you pop, the top of the stack comes off first — and the top is 9. So the first pop is the right operand, the second pop is the left one.

int a = stack.pop();  // 9
int b = stack.pop();  // 5
int r = a - b;        // 4  ✗

int right = stack.pop(); // 9
int left  = stack.pop(); // 5
int r = left - right;    // -4 ✓

Two cases, that's the whole thing

Once the reasoning is right, the code reads almost like English. For every token: if it's a number, push it. If it's an operator, pop two, apply, push the result. When you're done, the one value left on the stack is the answer.

# create an empty stack
for each token:
    if token is a number:
        push(token)
    else:                 # it's an operator
        right = pop()
        left  = pop()
        push( left op right )

return pop()             # the final answer

Every completed operation produces a new operand, which is why you push the result back. In 2 3 + 4 *, the 2 3 + becomes 5, and that 5 is exactly what 4 * needs next.

Your best debugging tool

When a stack solution misbehaves, don't stare at the code — build a table. Track the token, the action, and the stack state after it. The bug usually jumps out.

One number left, guaranteed

Each number pushes one value (+1). Each binary operator pops two and pushes one (net −1). A valid postfix expression has exactly one more operand than operators, so the stack collapses to a single value:

For 2 3 1 * + 9 -: four operands (2, 3, 1, 9), three operators (*, +, −). Since 4 = 3 + 1, it's valid — and it must end with one number. The deeper reason is an invariant: at any point, the stack holds exactly the fully-evaluated sub-results that no later operator has consumed yet.

Postfix is a tree walked bottom-up

The expression 2 3 4 * + means 2 + (3 * 4). Draw it as a tree and read it in postorder — left child, right child, then the node — and you get the postfix string back. That's literally why it's called "post"-fix: the operator prints after its operands.

postorder: 2 → 3 → 4 → * → +   =   2 3 4 * +

Where the operator sits

Same expression, 2 + (3 * 4), written three ways. The only thing that moves is the operator's position relative to its operands.

Linear, and you can't do better

You have to at least look at every token, so O(n) time is optimal. A naive approach — repeatedly scanning a list for the next operator and rewriting it in place — also works but wastes effort re-searching. The stack's insight is that the operands you need are always already on top, so no searching is required.

Four ways people break this

A clean Java solution

Prefer Deque<Integer> backed by ArrayDeque over the legacy Stack class. The switch reads naturally: a token is either one of three operators, or (default) a number.

import java.util.*;

public class Main {
    static int apply(int left, int right, String op) {
        switch (op) {
            case "+": return left + right;
            case "-": return left - right;
            case "*": return left * right;
            default: throw new IllegalArgumentException(op);
        }
    }

    static int evaluate(String expr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : expr.split(" ")) {
            if (t.equals("+") || t.equals("-") || t.equals("*")) {
                int right = stack.pop();   // first pop = right
                int left  = stack.pop();   // second pop = left
                stack.push(apply(left, right, t));
            } else {
                stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(evaluate("2 3 1 * + 9 -")); // -4
    }
}

Don't memorize code — memorize this chain

1. I scan the tokens left to right.
2. Numbers can't be used yet, so they wait.
3. An operator needs the two latest waiting values.
4. "Latest first" means LIFO, and LIFO means a stack.
5. Pop right, pop left, compute left op right, push the result.
6. When the tokens run out, the one value left is the answer.