Evaluate Reverse Polish Notation (LeetCode 150)

The problem

You get a list of string tokens that form an arithmetic expression in Reverse Polish Notation (postfix): operators come after their two operands. Tokens are integers or one of + - * /. Division truncates toward zero. The expression is always valid, and there is no division by zero. Return its integer value.

Input:  ["2", "1", "+", "3", "*"]
Output: 9

It means (2 + 1) * 3: the + applies to 2 and 1, and the * applies to that result and 3.

How to think about it

Start with brute force. You could repeatedly scan the list for the first operator, replace it and its two preceding numbers with the result, and repeat. Each replacement rebuilds the list, so that is O(n²) and fiddly to get right.

The key insight: an operator always uses the two most recent unused values. In postfix, when you read an operator, its operands are the last two values produced, whether they were literal numbers or results of earlier operators. “Last produced, first used” is LIFO, so a stack holds the pending operands. Numbers get pushed. An operator pops two, combines them, and pushes the result back, where it becomes an operand for something later.

Order of operands matters. The first pop is the right operand b, the second is the left operand a. For + and * it does not matter, but a - b and a / b come out wrong if you swap them.

Which pattern is this? A stack used to evaluate an expression. The tell is “tokens that combine with the most recent ones”, the same shape as bracket matching. Postfix is popular in interviews because it needs no precedence rules or parentheses.

Approach

1. Create an empty stack st.
2. For each token t:
   • If t is an operator, pop b, then pop a, compute a op b, and push the result. For /, use int(a / b) so the result truncates toward zero.
   • Otherwise convert t to an integer and push it.
3. The single value left on the stack is the answer.

Solution

def eval_rpn(tokens):
    st = []
    for t in tokens:
        if t in "+-*/":
            b = st.pop(); a = st.pop()          # b is the right operand
            if t == '+': st.append(a + b)
            elif t == '-': st.append(a - b)
            elif t == '*': st.append(a * b)
            else: st.append(int(a / b))         # truncate toward zero, not floor
        else:
            st.append(int(t))
    return st[0]
# eval_rpn(["2","1","+","3","*"]) -> 9

Dry run

One value remains, so the answer is 9.

Complexity

• Time: O(n). Each token is handled once with O(1) work.
• Space: O(n). In the worst case, about half the tokens are numbers waiting on the stack.

Edge cases and pitfalls

• Negative numbers such as "-11" are numbers, not operators. The check t in "+-*/" is safe only because a multi-character string like "-11" is not a substring of "+-*/". Don’t change it to t[0] in "+-*/".
• Floor vs truncation. Python’s // floors: -7 // 2 is -4, but the problem wants -3. int(-7 / 2) gives -3. This is the most common bug on this problem.
• Operand order for - and /: pop b first, then a.
• Single number input like ["5"] returns 5 with no operators at all.
• Float precision in a / b is fine for 32-bit inputs. For huge integers, compute abs(a) // abs(b) and fix the sign instead.

Related problems

• Valid Parentheses (LeetCode 20): the simplest stack-over-tokens problem.
• Asteroid Collision (LeetCode 735): each new item interacts with the top of the stack and may replace it.
• Min Stack (LeetCode 155): another stack where what you push depends on what is already on top.