Evaluate Reverse Polish Notation — Stack Solution Explained

Reverse Polish Notation (RPN), also called postfix notation, places operators after their operands. Instead of writing 3 + 4, you write 3 4 +. This eliminates the need for parentheses and operator precedence rules.

This is LeetCode 150, a classic stack problem.

Why RPN Exists

Notation	Expression	Needs Parens?	Needs Precedence?
Infix	3 + 4 * 2	Yes	Yes
Postfix (RPN)	3 4 2 * +	No	No
Prefix	+ 3 * 4 2	No	No

RPN is used in HP calculators, the Forth programming language, and internally by many compilers.

The Algorithm

The evaluation algorithm is beautifully simple:

1. Scan tokens left to right
2. If it is a number, push it onto the stack
3. If it is an operator, pop two numbers, apply the operator, push the result
4. The final value on the stack is the answer

def eval_rpn(tokens: list[str]) -> int:
    """
    Evaluate Reverse Polish Notation.
    LeetCode 150.
    Time: O(n), Space: O(n)
    """
    stack = []

    for token in tokens:
        if token in {'+', '-', '*', '/'}:
            b = stack.pop()  # second operand (popped first!)
            a = stack.pop()  # first operand

            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            elif token == '/':
                # Truncate toward zero, not toward -infinity
                stack.append(int(a / b))
        else:
            stack.append(int(token))

    return stack[0]

Step-by-Step Trace

Example: ["2", "1", "+", "3", "*"] = (2 + 1) * 3 = 9

Token  Action              Stack
─────  ──────              ─────
"2"    push 2              [2]
"1"    push 1              [2, 1]
"+"    pop 1,2 → 2+1=3    [3]
"3"    push 3              [3, 3]
"*"    pop 3,3 → 3*3=9    [9]

Result: 9 ✓

Example: ["4", "13", "5", "/", "+"] = 4 + (13 / 5) = 6

Token  Action                Stack
─────  ──────                ─────
"4"    push 4                [4]
"13"   push 13               [4, 13]
"5"    push 5                [4, 13, 5]
"/"    pop 5,13 → 13/5=2    [4, 2]
"+"    pop 2,4 → 4+2=6      [6]

Result: 6 ✓

Complex: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]

Infix equivalent: ((10 * (6 / ((9+3) * -11))) + 17) + 5

Token   Stack after
─────   ───────────
"10"    [10]
"6"     [10, 6]
"9"     [10, 6, 9]
"3"     [10, 6, 9, 3]
"+"     [10, 6, 12]           ← 9+3=12
"-11"   [10, 6, 12, -11]
"*"     [10, 6, -132]         ← 12*-11=-132
"/"     [10, 0]               ← 6/-132=0 (truncate)
"*"     [0]                   ← 10*0=0
"17"    [0, 17]
"+"     [17]                  ← 0+17=17
"5"     [17, 5]
"+"     [22]                  ← 17+5=22

Result: 22 ✓

The Python Division Gotcha

This is a critical detail that trips up many candidates:

# Python floor division (//)
6 // -132    # = -1  (rounds toward -infinity)

# What LeetCode expects (truncation toward zero)
int(6 / -132)  # = 0  ✓

# More examples:
int(-7 / 2)    # = -3  ✓ (truncate toward zero)
-7 // 2        # = -4  ✗ (floor toward -infinity)

Rule: Always use int(a / b) instead of a // b for this problem.

Operand Order Matters

When popping two values for an operator, the first popped is the right operand:

b = stack.pop()  # RIGHT operand
a = stack.pop()  # LEFT operand
result = a OP b  # a is left, b is right

This matters for subtraction and division:

["5", "3", "-"]  → 5 - 3 = 2  (not 3 - 5)
["6", "2", "/"]  → 6 / 2 = 3  (not 2 / 6)

Clean Implementation with Lambda

def eval_rpn_clean(tokens: list[str]) -> int:
    """
    Cleaner version using a dictionary of operations.
    """
    ops = {
        '+': lambda a, b: a + b,
        '-': lambda a, b: a - b,
        '*': lambda a, b: a * b,
        '/': lambda a, b: int(a / b),
    }
    stack = []

    for token in tokens:
        if token in ops:
            b, a = stack.pop(), stack.pop()
            stack.append(ops[token](a, b))
        else:
            stack.append(int(token))

    return stack[0]

Edge Cases

# Single number
assert eval_rpn(["42"]) == 42

# Negative numbers
assert eval_rpn(["-3", "2", "+"]) == -1

# Division resulting in zero
assert eval_rpn(["1", "3", "/"]) == 0

# Negative division (truncate toward zero)
assert eval_rpn(["7", "-2", "/"]) == -3

Complexity

Metric	Value	Why
Time	O(n)	Process each token once
Space	O(n)	Stack holds at most n/2 operands

When to Use This Pattern

• Expression evaluation: Any time you parse and evaluate mathematical expressions
• Calculator applications: RPN calculators are simpler to implement than infix ones
• Compiler internals: Many compilers convert infix to postfix before evaluation
• Stack machine emulation: JVM and Python bytecode use stack-based evaluation

Related Problems

• Basic Calculator — infix evaluation with precedence
• Expression Evaluation — infix to postfix conversion
• Valid Parentheses — simpler stack matching