Evaluate Reverse Polish Notation
Evaluate postfix expressions with a stack, and get integer division truncation right
Problem Statement
Evaluate an arithmetic expression in Reverse Polish Notation (postfix), given as an array of tokens. Valid operators are +, -, * and /. Division between two integers truncates toward zero.
Input: ["2", "1", "+", "3", "*"]
Output: 9
Why: (2 + 1) × 3
Input: ["4", "13", "5", "/", "+"]
Output: 6
Why: 4 + (13 / 5) = 4 + 2
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22Intuition
In ordinary infix notation, 2 + 1 * 3 needs precedence rules and parentheses to be unambiguous. Postfix notation removes both: the operator comes after its operands, and the order of tokens fully determines the order of evaluation.
The key insight
Read the tokens left to right:
- A number → push it.
- An operator → pop the two most recent values, apply the operator, push the result back.
Those two most recent values are exactly the operator's operands. That is last-in-first-out, so a stack does all the bookkeeping.
Operand order matters for `-` and `/`
The stack pops in reverse. The first pop is the right operand.
right = stack.pop() # popped first → right-hand side
left = stack.pop() # popped second → left-hand side
result = left - rightGetting this backwards gives the correct answer for + and * and the wrong sign or ratio for - and / — a bug that passes half the test cases.
Watch it run
Approach
For each token
If it is an operator, pop two values (right first, then left), apply, push the result. Otherwise parse it as an integer and push.
Return the single remaining value
A valid RPN expression always leaves exactly one value on the stack.
Solution
def eval_rpn(tokens: list[str]) -> int:
"""Evaluate a postfix expression. Division truncates toward zero."""
stack: list[int] = []
for token in tokens:
if token in {"+", "-", "*", "/"}:
right = stack.pop() # popped FIRST → right operand
left = stack.pop() # popped SECOND → left operand
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
# int() truncates toward zero; // floors toward -infinity.
stack.append(int(left / right))
else:
stack.append(int(token))
return stack[0]The division trap — this is what the problem is really testing
"Truncate toward zero" means -7 / 2 is -3, not -4.
Python: -7 // 2 is -4 — floor division rounds toward negative infinity. Use int(-7 / 2), which gives -3. This is the single most common wrong answer on this problem.
TypeScript: Math.floor(-3.5) is -4. Use Math.trunc(-3.5), which gives -3.
For positive operands the two agree, so the bug hides until a negative appears — as it does in the third example above.
Detecting operators by exclusion is fragile
Testing if (!isNaN(Number(token))) also works, but negative numbers like "-11" start with -, so any check that looks only at the first character misclassifies them. Matching against the explicit set of four operators is unambiguous.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
- Time — one pass; each token causes a constant amount of stack work.
- Space — the stack holds at most
O(n)operands, reached when the expression is a long run of numbers before the first operator.
Edge Cases
Related Problems
- Valid Parentheses — the stack as a nesting checker
- Min Stack — a stack carrying extra state
- Simplify Path — a stack where popping means going up a directory