Evaluate Reverse Polish Notation

Difficulty: Medium
Topics: Array, Math, Stack
Link: https://leetcode.com/problems/evaluate-reverse-polish-notation/

Problem Description

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

The valid operators are '+', '-', '*', and '/'.
Each operand may be an integer or another expression.
The division between two integers always truncates toward zero.
There will not be any division by zero.
The input represents a valid arithmetic expression in a reverse polish notation.
The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:


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

Example 2:


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

Example 3:


Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Constraints:

1 <= tokens.length <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Solution

1. Problem Deconstruction

Technical Restatement: Given a sequence of string tokens representing a valid Reverse Polish Notation (postfix) expression, implement a stack-based evaluator that processes operands and operators according to RPN semantics. The algorithm must handle four binary arithmetic operations (+, -, *, /) with integer truncation toward zero, maintain 32-bit integer precision for all intermediate calculations, and return the final computed value. The solution must process tokens in left-to-right order, pushing operands onto a stack and applying operators to the top two stack elements.

Beginner Explanation: Imagine you have a list of numbers and math symbols, but they’re arranged in a special “backward” way. Instead of writing “2 + 3”, you write “2 3 +”. To solve it: read through the list, remember numbers you see, and when you hit a math symbol, use it on the last two numbers you remembered. Replace those two numbers with the answer, and keep going until you have one number left.

Mathematical Formulation: Let $S$ be a stack data structure. For each token $t_i$ in the sequence $[t_1, t_2, ..., t_n]$ :

If $t_i \in \mathbb{Z}$ (integer operand): $S.\text{push}(\text{int}(t_i))$
If $t_i \in \{+, -, \times, \div\}$ $t_{i} \in {+, -, \times, \div}$ (operator):
- $b = S.\text{pop}()$ , $a = S.\text{pop}()$
- $S.\text{push}(f_{op}(a, b))$ $S . push (f_{o p} (a, b))$ where:
  - $f_+(a,b) = a + b$
  - $f_-(a,b) = a - b$
  - $f_\times(a,b) = a \times b$
  - $f_\div(a,b) = \text{truncate}(a / b)$

Constraint Analysis:

1 <= tokens.length <= 10^4: Requires O(n) time complexity with efficient O(n) space usage. Brute force recursion could cause stack overflow.
Operators limited to +, -, *, /: No need to handle exponentiation, modulus, or unary operators.
Division truncates toward zero: Critical for negative division (e.g., -5/2 = -2, not -3). Must use language-specific truncation, not floor division.
No division by zero: Eliminates defensive checks, simplifying code.
Valid RPN expression: Guarantees stack never underflows and ends with exactly one value.
32-bit integer range: Intermediate calculations won’t overflow, but we must use integer math, not floating point.

2. Intuition Scaffolding

Real-World Metaphor: Like a chef following a recipe where ingredients (numbers) are laid out, and cooking steps (operators) combine the last two ingredients into a new dish. Each cooking operation consumes two ingredients and produces one new dish, eventually yielding a final meal.

Gaming Analogy: Think of a puzzle game where you collect number tokens and have operation power-ups. When you use a power-up, it combines your two most recently collected tokens. The game ends when all power-ups are used, leaving one combined token value.

Math Analogy: Postfix notation eliminates parentheses by making operator precedence explicit. It’s like writing a mathematical expression tree in post-order traversal, where we evaluate child nodes before their parent.

Common Pitfalls:

Wrong operand order: For subtraction/division, the first popped element is the right operand
Floating-point division: Using float division then converting loses precision for large numbers
Floor vs truncation: Python’s // floors toward -∞, but we need truncation toward 0
Stack underflow: Assuming valid input prevents this, but real implementations need error handling
Type confusion: Forgetting to convert string tokens to integers before operations

3. Approach Encyclopedia

Brute Force (Recursive):

function evaluate(tokens):
    if tokens has only one element:
        return int(tokens[0])
    
    find the first operator at position i
    left_result = evaluate(tokens[0:i-2]) 
    right_operand = int(tokens[i-1])
    return apply_operator(left_result, right_operand, tokens[i])

Time Complexity: $O(n^2)$ - each recursive call scans remaining tokens Space Complexity: $O(n)$ - recursion stack depth

Optimal (Stack-based):

Stack: []
For each token in tokens:
    if token is operator:
        b = pop stack, a = pop stack
        result = apply_operator(a, b, token)
        push result to stack
    else:
        push int(token) to stack
Return stack's only element

Time Complexity Derivation:

$n$ tokens processed once → $O(n)$
Each stack operation $O(1)$ → $O(n)$ total

Space Complexity Derivation:

Worst-case stack size: $\lceil n/2 \rceil$ operands → $O(n)$

ASCII Visualization for ["2","1","+","3","*"]:

Step  Token  Stack     Action
0     -      []        Start
1     "2"    [2]       Push operand
2     "1"    [2,1]     Push operand  
3     "+"    [3]       Pop 1, Pop 2 → 2+1=3 → Push 3
4     "3"    [3,3]     Push operand
5     "*"    [9]       Pop 3, Pop 3 → 3*3=9 → Push 9

4. Code Deep Dive

def evalRPN(tokens):
    stack = []
    
    for token in tokens:
        if token in {"+", "-", "*", "/"}:
            # Pop operands (note order: b then a)
            b = stack.pop()
            a = stack.pop()
            
            # Apply operation based on token
            if token == "+":
                result = a + b
            elif token == "-":
                result = a - b  # a - b (not b - a!)
            elif token == "*":
                result = a * b
            else:  # token == "/"
                # Truncate toward zero, not floor division
                result = int(a / b)  # Key: int() truncates toward 0
                
            stack.append(result)
        else:
            # Convert string to integer and push
            stack.append(int(token))
    
    return stack[0]

Line-by-Line Analysis:

Line 2: Empty stack initialization
Line 4: Linear scan through all tokens
Line 5: Operator detection using set lookup (O(1))
Lines 7-8: Critical operand popping order: right operand b pops first
Lines 11-18: Arithmetic operations with special handling for division truncation
Line 21: Operand conversion from string to integer
Line 24: Final result is the stack’s sole element

Edge Case Handling:

Example 2: ["4","13","5","/","+"]
- Line 18: 13 / 5 = 2.6 → int(2.6) = 2 (truncation)
- Line 11: 4 + 2 = 6 ✓
Example 3: Complex nested operations correctly handle negative division:
- 6 / -132 = -0.045 → int(-0.045) = 0 (truncate toward zero)

5. Complexity War Room

Hardware-Aware Analysis:

At maximum constraint (10^4 tokens), stack uses ~40KB memory (4 bytes/int × 10^4/2 elements)
Fits comfortably in L2/L3 cache, enabling fast stack operations
Branch prediction benefits from operator distribution patterns

Industry Comparison Table:

Approach	Time	Space	Readability	Interview Viability
Brute Force	O(n²)	O(n)	6/10	❌ Fails large input
Stack-based	O(n)	O(n)	9/10	✅ Optimal solution
Tree-based	O(n)	O(n)	5/10	❌ Overcomplicated

6. Pro Mode Extras

Variants Section:

Multiple Data Types: Extend to support floating-point with configurable precision
Additional Operators: Add ^ (exponentiation), % (modulo), or unary -
Expression Validation: Check for invalid sequences before evaluation
RPN to Infix: Convert postfix back to parenthesized infix notation

Interview Cheat Sheet:

First Mention: “Stack-based approach achieves O(n) time/space complexity”
Division Emphasis: “Use truncation toward zero, not floor division”
Operand Order: “First popped is right operand for non-commutative operations”
Constraint Leverage: “Valid input assumption eliminates error handling”
Testing Strategy: “Verify with negative division and complex nesting”

#150 - Evaluate Reverse Polish Notation