Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation is the classic stack problem. It looks intimidating, but a stack turns it into a clean one-pass scan — and it teaches you exactly when a stack is the right tool.

The slow way first

You might try to convert the RPN back to normal infix notation, add parentheses, then evaluate that — or write a recursive parser. Both are fiddly and easy to get wrong: you have to track operator precedence and matching brackets. That is a lot of machinery for what turns out to be a very simple scan.

The question to ask: when I read an operator, where are its two operands? In RPN they are always the two most recent numbers that have not yet been used. "Most recent, not yet used" is the exact description of a stack.

The idea: push numbers, pop on an operator

Keep a stack. Scan the tokens left to right:

• If the token is a number, push it.
• If the token is an operator, pop the top two values (b first, then a), compute a op b, and push the result back.

When the scan ends, the stack holds exactly one value — the answer.

The key insight: an operator always combines the two newest numbers. Because a stack gives you those instantly with two pops, the whole evaluation is one linear pass with no parsing.

Walk through it

Step through the animation. The tok pointer scans the tokens; the stack grows upward on the right. We push 2, then 1. At + we pop 1 and 2, push 3. We push 3, giving [3, 3]. At * we pop 3 and 3, push 9. One value remains — the answer is 9.

Pseudocode

stack = empty
for each token:
    if token is a number:
        push int(token)
    else:                       # token is an operator
        b = pop()               # second operand (popped first!)
        a = pop()               # first operand
        push a (op) b           # apply and push the result
return the single value left on the stack

The Python solution

def eval_rpn(tokens):
    ops = {"+": add, "-": sub, "*": mul, "/": truediv}
    stack = []
    for tok in tokens:
        if tok not in ops:
            stack.append(int(tok))
        else:
            b = stack.pop()
            a = stack.pop()
            res = ops[tok](a, b)
            stack.append(int(res))
    return stack[0]

• ops maps each operator string to a function (from operator import add, sub, mul, truediv). It avoids a long if/elif chain.
• A token is a number whenever it is not in ops, so int(tok) is safe (this handles negatives like "-4" correctly).
• Order matters: we pop b first, then a, and compute a op b. For - and / the operands are not interchangeable, so getting this backwards breaks those cases.
• int(res) truncates the division result toward zero, matching the problem rule.
• After the loop the stack has exactly one element, so stack[0] is the answer.

Complexity

We touch each token once and every stack operation is constant time, so the whole thing is O(n) time. The stack can hold up to about half the tokens at once, so it uses O(n) extra space.

When this pattern shows up

Practice