How Would You Evaluate Reverse Polish Notation?
Learn how to evaluate reverse Polish notation with a stack in O(n) time, with a full Python implementation and pitfalls.
Expected Interview Answer
Reverse Polish Notation (postfix) is evaluated in a single left-to-right pass using a stack: push every number, and whenever an operator is seen, pop its two most recent operands, apply the operator, and push the result back — the final and only stack value is the answer.
Because postfix notation places operators after their operands, there is never any ambiguity about precedence or the need for parentheses — the order tokens appear in already encodes exactly how to group them. A stack naturally models this: numbers accumulate on top until an operator arrives, at which point the operator consumes the two topmost numbers (the second-popped is the left operand, the first-popped is the right operand, which matters for subtraction and division) and pushes the computed result back as if it were just another number. This runs in a single O(n) pass with O(n) space for the stack in the worst case, versus the more complex two-pass, precedence-aware parsing that infix expressions require. It is a direct, practical demonstration of why compilers often convert infix to postfix internally before evaluating.
- Single O(n) left-to-right pass, no backtracking
- No parentheses or precedence rules ever needed
- Stack push/pop directly mirrors operand/operator consumption
- Foundation for how compilers evaluate expressions internally
AI Mentor Explanation
Think of a scoring analyst reading a sequence of numbers and symbols where numbers are runs scored and a symbol like plus means 'combine the two most recent totals'. Reading left to right, every run count gets stacked up on a scratchpad; when a plus or minus symbol appears, the analyst pops the top two totals off the scratchpad, combines them exactly as instructed, and writes the combined total back onto the scratchpad as if it were a fresh number. By the time the whole sequence is read, only one number remains on the scratchpad, and that is the final match total, with no need to ever re-read earlier numbers or worry about operator precedence. This is exactly how reverse Polish notation collapses to a single stack-driven pass.
Step-by-Step Explanation
Step 1
Initialize an empty stack
Tokens are processed strictly left to right, one at a time, with no lookahead needed.
Step 2
Push numbers as encountered
Any numeric token is converted and pushed directly onto the stack.
Step 3
Pop two operands on an operator
Pop the top two values; the second-popped is the left operand, the first-popped is the right operand — order matters for - and /.
Step 4
Apply and push the result
Compute the operator on the two operands and push the result back; after the last token, exactly one value remains: the answer.
What Interviewer Expects
- Correctly identify a stack as the right structure with no need for parentheses handling
- Get operand order right for non-commutative operators (subtraction, division)
- State O(n) time and O(n) worst-case space complexity
- Handle integer division truncation correctly if the language requires it (e.g. toward zero)
Common Mistakes
- Swapping operand order on subtraction or division (using first-popped as left operand)
- Not validating that exactly one value remains on the stack at the end
- Forgetting to handle negative numbers or multi-digit numbers when tokenizing a raw string
- Using float division and division truncation rules inconsistently across languages
Best Answer (HR Friendly)
“I would scan the expression left to right using a stack. Any number gets pushed onto the stack, and whenever I hit an operator, I pop the top two numbers off, apply the operator being careful about the order for subtraction and division, and push the result back on. By the end, the only number left on the stack is the answer.”
Code Example
def eval_rpn(tokens):
stack = []
ops = {
"+": lambda a, b: a + b,
"-": lambda a, b: a - b,
"*": lambda a, b: a * b,
"/": lambda a, b: int(a / b), # truncate toward zero
}
for token in tokens:
if token in ops:
right = stack.pop()
left = stack.pop()
stack.append(ops[token](left, right))
else:
stack.append(int(token))
return stack.pop()
# Example: ["2", "1", "+", "3", "*"] -> (2 + 1) * 3 = 9
print(eval_rpn(["2", "1", "+", "3", "*"]))Follow-up Questions
- How would you convert an infix expression to postfix (Shunting Yard algorithm)?
- How would you handle unary minus or floating-point numbers in the tokenizer?
- How would you evaluate a prefix (Polish) expression instead — from left or right?
- What edge cases (division by zero, malformed input) should the function guard against?
MCQ Practice
1. Evaluating ["4", "13", "5", "/", "+"] with a stack gives which result?
13 / 5 truncates to 2, then 4 + 2 = 6.
2. When an operator is popped in RPN evaluation, which popped value is the left operand?
The second-popped value was pushed earlier, so it is the left operand; this matters for non-commutative operators like - and /.
3. What is the time complexity of evaluating an RPN expression with n tokens?
Each token is processed exactly once with O(1) stack operations, giving O(n) overall.
Flash Cards
What data structure evaluates RPN expressions? — A stack.
On an operator token, which operand is popped first? — The right operand is popped first; the second pop is the left operand.
What is the time complexity of RPN evaluation? — O(n), a single left-to-right pass.
Why does RPN never need parentheses? — Postfix order already encodes grouping and precedence unambiguously through token order.