150. Evaluate Reverse Polish Notation - Detailed Explanation

Problem Statement

You’re given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation. Evaluate the expression and return the result as an integer. Valid operators are +, -, *, and /. Each operand may be an integer or another expression in RPN. Division between two integers should truncate toward zero.

Examples

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:  
  Step by step:  
  9 3 + → 12  
  12 –11 * → –132  
  6 ÷ (–132) → 0  (truncated)  
  10 * 0 → 0  
  0 + 17 → 17  
  17 + 5 → 22  

Constraints

• 1 ≤ tokens.length ≤ 10⁴
• Each tokens[i] is either an operator "+", "-", "*", "/" or an integer in the range [−200, 200].
• The given RPN expression is always valid and the result fits in a 32‑bit signed integer.

Hints

1. How would you evaluate an expression in infix notation? Can you adapt that to RPN?
2. When you see a number, you need to store it until you have two operands for an operator.
3. A stack is perfect: push numbers, and when you see an operator, pop two, compute, then push the result.

Approach (Stack‑Based One‑Pass)

1. Initialize an empty stack of integers.
2. Iterate through each token in tokens:
   • If it’s a number (check by trying to parse), convert and push onto the stack.
   • Otherwise it’s an operator:
     1. Pop the top two values in LIFO order: let b = stack.pop(), then a = stack.pop().
     2. Compute res = apply(a, b, operator).
     3. Push res back onto the stack.
3. After processing all tokens, the stack contains exactly one value, the final result. Pop and return it.

Why It Works

Reverse Polish Notation is designed so that you never need to look backward or worry about precedence or parentheses. By pushing operands and applying operators immediately when they appear, you naturally respect the intended grouping.

Step‑by‑Step Walkthrough

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

• See "2" → push 2; stack = [2]
• See "1" → push 1; stack = [2,1]
• See "+" → pop b=1, a=2 → compute 2+1=3 → push 3; stack = [3]
• See "3" → push 3; stack = [3,3]
• See "*" → pop b=3, a=3 → compute 3*3=9 → push 9; stack = [9]
  End → pop 9 as result.

Complexity Analysis

• Time: O(n), where n = number of tokens, since each token is pushed or popped at most once.
• Space: O(n), for the stack in the worst case (all numbers).

Python Code