~20 minutes · stack evaluation · Python
Tonight's problem is Evaluate Reverse Polish Notation. It looks like a math problem, but interviews use it to test whether you can keep one clean rule in your head while symbols arrive left to right. You do not need a parser. You need a stack.
Push operands; on an operator, pop two, combine, push the result — postfix needs no precedence rules.
Postfix notation puts each operator after its operands, so 2 1 + 3 * means (2 + 1) * 3. That ordering is why Reverse Polish notation can be evaluated left to right with a stack, without parentheses or precedence rules (Wikipedia: Reverse Polish notation).
A stack is last-in, first-out: the newest unresolved value is the first one removed (Wikipedia: stack). In Python, a plain list is enough for this lesson: append pushes to the end, and pop removes from the end (Python docs: using lists as stacks).
One trap matters for this LeetCode problem: division must truncate toward zero. Python's // is floor division, so negative cases can round the wrong way (Python docs: arithmetic operations). The code below divides magnitudes, then restores the sign.
A slow approach is to keep rewriting the token list: scan until you find number number operator, replace those three tokens with the computed value, then scan again. It works, but each replacement can require another scan and list shift, so it drifts toward O(n²).
["2", "1", "+", "3", "*"]
^ ^ ^
replace with 3, then continueThe better approach keeps the unresolved operands on a stack. The moment an operator arrives, the two values it needs are exactly the top two stack items.
The stack keeps only unresolved numbers; each operator immediately collapses the top two into one result.
def evalRPN(tokens):
stack = []
for t in tokens:
if t not in "+-*/":
stack.append(int(t)); continue # operands wait
b, a = stack.pop(), stack.pop() # right operand pops first
if t == "+": stack.append(a + b)
elif t == "-": stack.append(a - b)
elif t == "*": stack.append(a * b)
else:
q = abs(a) // abs(b) # truncate toward zero
stack.append(q if a * b > 0 else -q)
return stack[-1]The order of the pops is the whole bug risk. For subtraction and division, a is the older value and b is the newer top value, so the operation is a - b or a / b, not the reverse.
For division and subtraction, name the first pop b so the older value still stays on the left.
Try this smaller postfix expression: ["4", "13", "5", "/", "+"]. Before opening the answer, say which two values the / operator pops, what gets pushed back, and what the final stack contains.
Read left to right. Push 4, push 13, push 5. The / pops 5 as b, then 13 as a, and pushes 2. Now the stack is [4, 2]. The + pops 2 and 4, pushes 6, and the final answer is 6.
| Approach | Time | Space |
|---|---|---|
| Repeated rewrite (scan, replace, scan again) | O(n²) | O(n) |
| Stack evaluation (push operands, pop on operators) | O(n) | O(n) |
The stack version is linear because every token is handled once, and each operand is pushed once and popped once.
1. What happens when the next token is an operator?
2. If the first pop is b and the second pop is a, how should subtraction run?
b pops first and a pops second, subtraction is a - b.3. Which input exposes Python // as the wrong division choice?
7 // -3 floors to -3, but truncation toward zero should produce -2.4. Which problem shape is this exact pattern?
Solve Evaluate Reverse Polish Notation tonight, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:
Watch NeetCode — Evaluate Reverse Polish Notation after your attempt, as the compare step. Do not use it before the 20–25 minute attempt window.
Stuck or curious? Ask your teacher (the agent) — that's what it's for.