Evaluate Reverse Polish Notation
Evaluate an arithmetic expression given in Reverse Polish (postfix) notation.
- 1 <= tokens.length <= 10⁴
- tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
Intuition
Evaluate reverse polish notation computes the value of an expression in postfix form, where operators follow their operands: ["2", "1", "+", "3", "*"] means (2 + 1) × 3.
Postfix exists precisely because it needs no parentheses and no precedence rules — the order of tokens fully determines the order of evaluation. That property makes a stack the natural fit:
- Push every number; on an operator, pop the two most recent values, combine them, and push the result back.
The two most recently pushed values are always the correct operands, which is why one pass with no lookahead suffices.
The detail that breaks solutions is operand order. The first value popped is the second operand. For ["5", "3", "-"], popping gives 3 then 5, and the answer is 5 − 3 = 2, not 3 − 5. Addition and multiplication hide this error; subtraction and division expose it.
Division truncates toward zero, which differs from floor division for negative results. Python's -7 // 2 gives -4 where the problem requires -3, so int(a / b) or an explicit truncation is needed.
Token classification also needs care: a negative number like "-4" is an operand, not an operator, so test against the operator set rather than checking for a leading minus sign.
With valid input, exactly one value remains on the stack at the end, and that is the answer.
Postfix notation is a stack machine program: push operands, and on an operator pop two, apply, push back. No precedence rules and no parentheses — the ordering already encodes the tree, which is why compilers use this form.
Approach
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) time and O(n) space.
Understand why postfix suits a stack
Operators follow their operands, so no parentheses or precedence rules are needed. The two most recent values are always the right operands.
Push numbers, apply operators
Push each numeric token. On an operator, pop two values, combine them, and push the result. One pass with no lookahead completes the evaluation.
Respect the operand order
The first value popped is the second operand. For ["5", "3", "-"] the answer is 5 - 3, not 3 - 5 — addition and multiplication hide this bug, subtraction reveals it.
Truncate division toward zero
Division truncates toward zero, not floor. Python's -7 // 2 gives -4 where -3 is required, so use int(a / b) or truncate explicitly.
Classify tokens carefully
A token like "-4" is a negative operand, not an operator. Test membership in the operator set rather than looking for a leading minus sign.
Return the remaining value
With valid input, exactly one value is left on the stack when the tokens are exhausted, and that is the result.
Cost of the evaluation
Each token is processed once and pushed at most once, giving O(n) time and O(n) space for the stack.
Solution & live demo
Common pitfalls
Popping the operands in the wrong order
a = st.pop() b = st.pop() st.append(a - b)
b = st.pop() a = st.pop() st.append(a - b)
The stack returns the second operand first. Reversing them is invisible for + and * but silently wrong for - and /, which is what makes it a nasty bug.
Using floor division
st.append(a // b)
st.append(int(a / b))
The problem truncates toward zero, but Python's // floors toward negative infinity — so -7 // 2 gives −4 instead of the required −3. C++ and Java's integer division already truncates correctly.
Detecting operands by checking for digits
if t.isdigit():
if t not in ops:
isdigit returns false for negative numbers like "-4", which are then misread as the subtraction operator. Testing against the operator set classifies every token correctly.
Edge cases
Nothing is popped and that number is returned.
Parsing must accept a leading -, so check token in ops rather than testing for a digit.
The main trap — int(a / b) is correct, plain // is not.
Handled naturally; the stack simply grows deeper.