Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Scan the tokens with a stack of operands. Push every number; on an operator, pop the top two operands, apply the operator (minding order: second-popped OP first-popped), and push the result back. The final value left on the stack is the answer. O(n) time, O(n) space. Postfix notation needs no precedence or parentheses handling — that's the whole point of it.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you model expression evaluation with an operand stack and get the operand *order* and division semantics right — the two places candidates slip.
Where candidates slip
Subtracting/dividing in the wrong order (a vs b), flooring division instead of truncating toward zero, or failing to parse multi-digit/negative number tokens.
How to stand out
State that postfix needs no precedence handling, label which pop is the left operand, and call out the truncate-toward-zero division rule before the interviewer asks about negatives.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewRead token tIs t an operator?NoYesExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 1 · Optimal
Stack of Operands (Optimal)
1Hint 1Explore hintHide hint
In '3 4 +', the operator comes last. When you finally reach an operator, which numbers are its operands — and where are they relative to the operator?
2Hint 2Explore hintHide hint
Push numbers as you read them. When you hit an operator, the two numbers it needs are the two most recently pushed — pop them.
3Hint 3Explore hintHide hint
Mind the order for - and /: the value popped first is the right-hand operand. Push the result back so it can feed later operators.
A · Core idea
Walk the token array once, maintaining a stack of integer operands.
Numbers wait, operators consume. When a token is a number, push it — it isn't actionable yet because in postfix the operator that will use it hasn't arrived. When a token is one of + - * /, its operands are the two most recently produced values, which sit on top of the stack. Pop them, apply the operator, and push the single result back so it can serve as an operand for a later operator. After the last token, exactly one value remains — the answer.
Operand order is the classic trap. For commutative operators (+, *) order is irrelevant, but for - and / it is not. The token sequence [a, b, '-'] means a - b. Since b was pushed last, it's popped first; a is popped second. So you must compute secondPop OP firstPop, i.e. a - b and a / b. Reversing them silently produces wrong answers on any expression with subtraction or division.
Division truncates toward zero. The problem requires truncation toward zero, not flooring. Java's int division already truncates toward zero, so a / b is correct. Python's // floors (-7 // 2 == -4), which is wrong here — use int(a / b) (float divide then truncate) or int(operator.truediv(...)) so -7 / 2 becomes -3.
Parsing tokens. Operands can be negative and multi-digit (-11, 200), so detect operators by exact string match against the four symbols and parse everything else with Integer.parseInt / int(). Checking only whether the first character is a digit would misclassify negative numbers as operators.
Why no precedence logic. That's the elegance of postfix: the linear order already encodes all grouping, so there are no parentheses to balance and no operator-precedence comparisons. This is exactly why compilers convert infix to postfix before evaluation.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
tokens = ["4","13","5","/","+"]Array state
"2"
push 2
6C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
RPN evaluation is the dual of Valid Parentheses: instead of matching nested delimiters, we resolve operands as soon as their operator appears. The stack 'defers' values until the operation that needs them shows up — the same defer-and-resolve discipline reused in infix-to-postfix conversion (shunting-yard) and basic calculator problems.
ComplexityO(n) time, O(n) space — Single pass over n tokens; each token is pushed and popped at most a constant number of times → O(n) time. The stack holds up to O(n) operands → O(n) space.
E · Edge cases and pitfalls8tokens = ["-11"] — Single negative number, no operator → return -11. Token parsing must accept the minus sign.Explore edge casesHide edge cases
Edge cases handled
tokens = ["-11"]Single negative number, no operator → return -11. Token parsing must accept the minus sign.tokens = ["7","2","/"]7 / 2 = 3 (truncates toward zero).tokens = ["-7","2","/"]-7 / 2 = -3 toward zero — Python // would give -4, hence int(a/b).tokens = ["3","4","-"]b=4, a=3 → 3 - 4 = -1; order matters.
Pitfalls
- Computing b - a / b / a instead of a - b / a / b — wrong operand order.
- Using Python // (floor) instead of int(a / b) (truncate) for division.
- Detecting numbers by Character.isDigit on the first char — misclassifies negative tokens.
- Returning stack size or the first element instead of the single remaining value.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int evalRPN(String[] tokens) { Deque<Integer> stack = new ArrayDeque<>(); for (String t : tokens) { switch (t) { case "+" -> stack.push(stack.pop() + stack.pop());Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Reversed operands on - and /
The first value popped is the RIGHT operand. For tokens [a, b, '-'] the answer is a - b, so you must subtract the first pop from the second pop, not the other way around.
Explore the code comparisonHide the code comparison
Reversed operands on - and /
The first value popped is the RIGHT operand. For tokens [a, b, '-'] the answer is a - b, so you must subtract the first pop from the second pop, not the other way around.
Don't write this
int b = stack.pop(), a = stack.pop();
stack.push(b - a); // wrong: this is b - aWrite this instead
int b = stack.pop(), a = stack.pop();
stack.push(a - b); // correct: left - right2Floor division instead of truncation
Python's // floors toward negative infinity, so -7 // 2 = -4, but the problem requires truncation toward zero (-3). Use int(a / b).
Explore the code comparisonHide the code comparison
Floor division instead of truncation
Python's // floors toward negative infinity, so -7 // 2 = -4, but the problem requires truncation toward zero (-3). Use int(a / b).
Don't write this
stack.append(a // b) # -7 // 2 == -4 (floor) — wrongWrite this instead
stack.append(int(a / b)) # int(-7 / 2) == -3 (toward zero)Revise
Carry the pattern into the interview
Pattern to remember
Operand stack for postfix evaluation
Code pattern to memorize
stack = []
for t in tokens:
if t in {'+','-','*','/'}:
b = stack.pop(); a = stack.pop() # a is the LEFT operand
stack.append(apply(a, b, t))
else:
stack.append(int(t))
return stack[-1]Rules to remember
- 1Push numbers; on an operator pop two operands and push the single result.
- 2Order matters for
-and/: the first pop is the right operand, the second pop is the left → computea OP bwhereawas popped second. - 3Division must truncate toward zero (the problem's rule), not floor —
6 / -132is0,-7 / 2is-3. - 4Parse with
Integer.parseInt/int()so negative tokens like-11are handled — don't test only the first char for a digit. - 5Exactly one value remains at the end for a well-formed expression — return the stack top.
Use this pattern when
- Evaluating postfix / RPN expressions
- Any 'apply an operator to the most recent operands' computation
- Compiler/calculator back-ends after converting infix to postfix
Choose another pattern when
- Input is infix with precedence and parentheses → first convert (shunting-yard) or use two stacks
- You need the parse tree, not just the value → build an expression tree instead
- Operators are unary or variadic → the fixed pop-two pattern doesn't apply directly
Interview takeaway
Postfix is stack-native: operands wait on the stack and each operator consumes the two most recent. Recognising that RPN removes all precedence/parenthesis logic — and that operand order on subtraction/division is the only gotcha — makes this a clean O(n) stack problem.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternOperand stack for postfix (RPN) evaluation. Recognise it when operators follow their operands: push numbers, and let each operator consume the two most recent. Foundational for calculator and infix-to-postfix (shunting-yard) problems.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Basic CalculatorInfix with parentheses and +/- — use a stack to handle sign flips across nested parentheses.
- Basic Calculator IIComing soonInfix with precedence — defer * and / by keeping a running stack of terms.
- Basic Calculator IIIComing soonParentheses plus precedence — combine the two-stack / recursion approaches.
- Valid ParenthesesThe structural cousin: match nested delimiters with a stack.