Evaluate Reverse Polish Notation (LeetCode 150): A Clean Stack Solution and the Details Interviewers
10 views
You are given an array of tokens representing an arithmetic expression in Reverse Polish Notation (postfix). Operators are +, -, * and /, operands are integers, and division truncates toward zero. Return the value of the expression. For example, ["2","1","+","3","*"] means (2 + 1) * 3 = 9.
The problem is short, but interviewers use it to see whether you handle the small details correctly: operand order, negative numbers and integer division.
Why a stack fits
In postfix notation every operator applies to the two most recent values that have not yet been consumed. That "most recent first" behavior is exactly what a stack gives you. Scan the tokens left to right:
- If the token is a number, push it.
- If it is an operator, pop the top two values, apply the operator, and push the result.
At the end, the stack holds exactly one value: the answer.
def evalRPN(tokens):
stack = []
for t in tokens:
if t in "+-*/" and len(t) == 1:
b = stack.pop()
a = stack.pop()
if t == '+':
stack.append(a + b)
elif t == '-':
stack.append(a - b)
elif t == '*':
stack.append(a * b)
else:
stack.append(int(a / b))
else:
stack.append(int(t))
return stack[0]
Time is O(n) and space is O(n) in the worst case (all numbers before operators).
Detail 1: operand order
The first value you pop is the right operand. For "-" and "/" this matters: ["4","13","5","/","+"] should give 4 + (13 / 5) = 6. If you swap a and b, subtraction and division silently break while addition and multiplication still pass, which is why some candidates only discover the bug late. Say "first pop is b, second pop is a" out loud.
Detail 2: negative numbers
A token like "-11" is a number, not an operator. Checking len(t) == 1 (or trying to parse an int first) avoids treating it as subtraction.
Detail 3: truncation toward zero
In Python, -7 // 2 is -4 because floor division rounds down. The problem wants -3. Using int(a / b) truncates correctly for the input sizes in this problem; in an interview you can also mention a pure integer approach: compute abs(a) // abs(b) and apply the sign. In Java and C++, integer division already truncates toward zero, so this pitfall is mainly Python's.
Follow-up questions to expect
- "What if the input could be invalid?" Check that the stack has at least two values before each operator and exactly one at the end; raise an error otherwise.
- "Convert infix to postfix." Describe the shunting-yard algorithm: an operator stack, precedence rules and parentheses.
- "Can you do it without an explicit stack?" A recursive solution that evaluates from the end of the array works, but the stack version is clearer.
- "Support exponentiation or unary minus." Discuss associativity: exponentiation is right-associative in infix, but in postfix the order is already explicit.
How to present it
Start with one sentence: "Postfix means each operator uses the last two unused values, so I'll keep a stack." Then code, then trace the example with the stack contents written out. That trace usually catches order bugs before the interviewer does.
Explaining small details under pressure is where many candidates stumble even on easy problems. Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, helping you keep track of edge cases while you think out loud.