Evaluate Reverse Polish Notation — Operand Stack Calculator

Problem Statement#

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN). Valid operators are +, -, *, and /. Each operand may be an integer or another expression. Division between two integers truncates toward zero.

Constraints:

• 1 <= tokens.length <= 10^4
• tokens[i] is either an operator +, -, *, /, or an integer in the range [-200, 200].
• The given RPN expression is always valid.

Input:  tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input:  tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = (4 + 2) = 6

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Why This Problem Matters#

LC 150 is the canonical example of how stacks power expression evaluation — the same technique used by every compiler and calculator on the planet. Reverse Polish Notation eliminates the need for parentheses by using operand order to define precedence.

Companies that ask this problem: Amazon, LinkedIn, Microsoft, and Bloomberg. It is often a warm-up before harder expression problems like Basic Calculator I/II (LC 224, 227) and Decode String (LC 394).

Understanding RPN evaluation is essential for:

• Compiler design: abstract syntax trees and code generation.
• Calculator apps: many calculators use RPN internally.
• Stack machines: the JVM and Python's CPython both use stack-based bytecode execution.
• Expression parsing: converting infix to postfix and evaluating.

The Core Insight#

What is RPN? In normal (infix) notation, operators go between operands: 2 + 3. In RPN (postfix), operators come after their operands: 2 3 +. The order of evaluation is always left-to-right, and no parentheses are needed.

Stack evaluation: Process tokens left to right:

• If the token is a number, push it onto the stack.
• If the token is an operator (+, -, *, /), pop two operands from the stack (second-pop is the left operand, first-pop is the right operand), apply the operator, and push the result.

After processing all tokens, the stack contains exactly one element — the final result.

Why LIFO is perfect here: The last two operands pushed are the ones needed for the current operator. The LIFO property of a stack naturally gives us the most recently seen operands in the correct order.

Division truncation toward zero: In Python, // floors toward negative infinity, which differs from truncation toward zero for negative numbers. Use int(a / b) instead of a // b.

Visual Dry Run#

Input: ["4","13","5","/","+"]

Result: 6 ✓

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

Result: 9 ✓

Solution (Optimal)#

# Python — operand stack, O(n) time and space
def evalRPN(tokens: list[str]) -> int:
    stack = []
    operators = {'+', '-', '*', '/'}
 
    for token in tokens:
        if token in operators:
            # Pop two operands: b is second-to-top (right), a is top (left)
            # Wait — actually: pop order is LIFO, so first pop = right operand
            b = stack.pop()   # right operand (pushed second)
            a = stack.pop()   # left operand (pushed first)
 
            if token == '+':
                stack.append(a + b)
            elif token == '-':
                stack.append(a - b)
            elif token == '*':
                stack.append(a * b)
            else:  # '/'
                # Truncate toward zero (not floor division)
                stack.append(int(a / b))
        else:
            stack.append(int(token))
 
    return stack[0]

// JavaScript — operand stack, O(n) time and space
function evalRPN(tokens) {
    const stack = [];
    const operators = new Set(['+', '-', '*', '/']);
 
    for (const token of tokens) {
        if (operators.has(token)) {
            const b = stack.pop();   // right operand
            const a = stack.pop();   // left operand
 
            switch (token) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/':
                    // Truncate toward zero (same as C/Java integer division)
                    stack.push(Math.trunc(a / b));
                    break;
            }
        } else {
            stack.push(parseInt(token, 10));
        }
    }
 
    return stack[0];
}

Complexity:

Common Mistakes#

1. Popping operands in the wrong order. The first pop gives the right operand (pushed second); the second pop gives the left operand (pushed first). a - b where b is first-popped and a is second-popped. Getting this backwards makes 5 1 - evaluate to 1 - 5 = -4 instead of 5 - 1 = 4.

2. Using Python's // for division. Python's // (floor division) truncates toward negative infinity: -7 // 2 = -4, but RPN truncates toward zero: -7 / 2 = -3. Use int(a / b) instead.

3. Not converting string tokens to integers. Tokens arrive as strings. Forgetting int(token) when pushing operands causes string concatenation instead of addition on +.

4. Using token not in operators check by comparing to "+" or "-" or "*" or "/". Comparing strings with in a set is O(1) and clean. Chaining == comparisons is verbose and error-prone.

5. Assuming only single-digit numbers. Tokens can be negative ("-3") or multi-digit ("100"). int(token) handles both correctly, but trying to check token.isdigit() fails for negative numbers (the - sign makes it return False).

Interview Tips#

• Explain the pop order: "The stack is LIFO. When we push operands in order a b, then apply operator op, we pop b first (right operand) then a (left operand). So a op b = second-pop op first-pop."
• Address Python division: "Python's // floors toward negative infinity, which differs from C/Java truncation toward zero for negative dividends. I use int(a / b) to match the expected behavior."
• Connect to compiler design: "RPN is exactly the postfix bytecode that stack-based virtual machines like the JVM and CPython use. Every method call, arithmetic, and comparison compiles down to push/pop/apply operations."

Follow-up Questions#

1. Basic Calculator I (LC 224) — evaluate +, -, with parentheses (no *, /). Requires precedence handling.
2. Basic Calculator II (LC 227) — evaluate +, -, *, / without parentheses. Use a stack to handle *// before +/-.
3. Convert infix to RPN. The Shunting-yard algorithm uses a stack to handle operator precedence during conversion.
4. What if the operator set includes ^ (exponentiation)? Add a case in the switch; handle right-associativity of ^ if converting from infix.
5. Evaluate with variables. Maintain a variable map alongside the operand stack; push variable values when encountered.

Key Takeaways#

• Operand stack pattern: push numbers, pop two operands when an operator is encountered, push the result. Final stack top is the answer.
• Pop order matters: first pop = right operand, second pop = left operand. This is the most common bug in this problem.
• Python division: always use int(a / b) (not a // b) for RPN — the problem requires truncation toward zero, not floor division.
• Detecting negative numbers in tokens: int(token) handles both negative numbers ("-3") and multi-digit numbers ("100") — do not use token.isdigit() as the branch condition.
• RPN is the postfix form that eliminates ambiguity and parentheses — the exact format used by stack-based virtual machines internally.
• This problem is a direct stepping stone to Basic Calculator I/II and expression parsing problems at FAANG.