LeetCode #150 Medium

Evaluate Reverse Polish Notation

Evaluate an arithmetic expression given in Reverse Polish (postfix) notation.

stackmathstrings

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1class Solution:
▶2    def evalRPN(self, tokens):
▶3        st = []
▶4        ops = {'+', '-', '*', '/'}
▶5        for t in tokens:
▶6            if t not in ops:
▶7                st.append(int(t))
▶8                continue
▶9            b = st.pop()
▶10            a = st.pop()
▶11            if t == '+':
▶12                st.append(a + b)
▶13            elif t == '-':
▶14                st.append(a - b)
▶15            elif t == '*':
▶16                st.append(a * b)
▶17            else:
▶18                st.append(int(a / b))
▶19        return st[-1]

05

Edge cases

Single number token

Nothing is popped and that number is returned.

Negative numbers in the input

Parsing must accept a leading -, so check token in ops rather than testing for a digit.

Division truncating toward zero

The main trap — int(a / b) is correct, plain // is not.

Deeply nested expressions

Handled naturally; the stack simply grows deeper.

06

Complexity

Time

O(n)

Space

O(n)

One pass; the stack depth is bounded by the expression's nesting.