Evaluate Reverse Polish Notation
Evaluate an arithmetic expression given in Reverse Polish (postfix) notation.
Open on LeetCode ↗Intuition
The instinct is to pop two values and apply the operator to whichever order they come out in, since addition and multiplication don't care about order. That instinct is what breaks subtraction and division: the second value you pop is the left operand, not the first, and getting it backwards still produces plausible-looking (wrong) answers, so the bug hides instead of crashing. Push numbers; on an operator, pop b then a, apply a op b, and push the result.
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
Why postfix needs no precedence
Infix requires precedence and brackets because the operator sits between its operands and the grouping is ambiguous. In postfix, an operator always applies to the two most recently completed values, so the order of evaluation is fully determined by position.
Push operands, reduce on operators
Scan the tokens. A numeric token is pushed. An operator pops b then a — note the order — computes a op b, and pushes the result. Getting this backwards silently produces wrong answers for - and / while + and * still look fine, which makes it hard to spot.
Truncate division toward zero
The problem specifies truncation toward zero, but Python's // floors, so -7 // 2 gives -4 instead of -3. Use int(a / b) or int(operator.truediv(a, b)) instead. At the end the stack holds exactly one value — the answer. O(n) time, O(n) space.
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.