How to Explain Evaluate Reverse Polish Notation in a Coding Interview (Step-by-Step)

Reverse Polish Notation is the stack problem that proves you understand why stacks exist — not just how to use them. The algorithm is elegant and short. What trips candidates up is the operand-order subtlety on subtraction and division, and the integer truncation rule that Python gets wrong by default.

In this post, you’ll learn how to walk an interviewer through LeetCode 150 with confidence: what RPN is and why a stack solves it naturally, the pop-order gotcha, the truncation-toward-zero detail, a full token-by-token stack trace, and every edge case worth calling out.

Problem Statement

Examples

Constraints

• 1 <= tokens.length <= 104
• tokens[i] is either an operator or an integer in the range [-200, 200]
• The expression is always valid — no division by zero

What Is Reverse Polish Notation?

“RPN eliminates the need for parentheses entirely. Each operator always applies to the two most recently seen operands — which is exactly what a stack gives us. The top two items on the stack are always the operands for the next operator.”

The Key Insight — Operators Always Act on the Top Two

“The reason a stack is the natural structure here is that evaluation in RPN is last-in-first-out: the most recently pushed operands are the ones consumed by the next operator. A stack encodes that ordering for free.”

The Four Operators — and the Pop-Order Gotcha

“When we pop two values, the first pop gives the right operand and the second pop gives the left operand. For addition and multiplication this doesn’t matter — they’re commutative. For subtraction and division it matters enormously. If I pop a then b, the correct operation is b - a and b / a — not the other way around.”

Step 2: Explain the Algorithm in Plain English

Stack Trace Visualised — [“2″,”1″,”+”,”3″,”*”]

Expected result: ((2 + 1) * 3) = 9. Tracing every token step by step.

The Truncation Gotcha — Python Division vs. the Problem’s Rule

“This is the subtlest part of the problem. Using b // a in Python would give the wrong answer for any division that produces a negative non-integer result. int(b / a) uses Python’s float division first, then int() which truncates toward zero — matching the problem’s spec exactly.”

Step 3: Talk Through the Code

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        operators = {'+', '-', '*', '/'}

        for token in tokens:
            if token not in operators:
                stack.append(int(token))   # Convert string to int and push
            else:
                a = stack.pop()            # Right operand (most recently pushed)
                b = stack.pop()            # Left operand

                if token == '+':
                    stack.append(b + a)
                elif token == '-':
                    stack.append(b - a)    # b - a, NOT a - b
                elif token == '*':
                    stack.append(b * a)
                elif token == '/':
                    stack.append(int(b / a))  # Truncate toward zero, not //

        return stack[0]

Point out the operator set check token not in operators — it’s cleaner than token.lstrip('-').isdigit() because it handles negative number tokens like "-11" correctly without any string manipulation. Negative numbers are valid tokens and will fail the operator check, routing them correctly to int(token).

Step 4: Highlight Edge Cases

Step 5: State Time and Space Complexity

“Time is O(n) — one pass through the token array, one O(1) operation per token. Space is O(n) in the worst case: an expression like ['1','2','3','4','+','+','+'] pushes all operands before any operator fires. The stack can hold at most n/2 elements at peak for a fully balanced expression, but we still call it O(n).”

Interview Checklist for Evaluate Reverse Polish Notation

• Explain what RPN is — operator comes after its operands, no parentheses needed
• Name the LIFO property — the most recent two values are always the next operands
• State the algorithm: numbers push, operators pop-compute-push
• Explicitly call out the pop order — first pop is right operand, second is left
• Show why this matters: subtraction and division are non-commutative
• Call out the truncation-toward-zero rule — and why Python’s // is wrong for negatives
• Use int(b / a) not b // a for division
• Use token not in operators to cleanly handle negative number tokens like "-11"
• Call out: single token → push and return; deeply nested → handled transparently
• State O(n) time and O(n) space

Related Problems to Practice

If you can solve Evaluate Reverse Polish Notation cleanly, try these next: