107. Evaluate Reverse Polish Notation
🔗 LeetCode Problem: 150. Evaluate Reverse Polish Notation
📊 Difficulty: Medium
🏷️ Topics: Stack, Array, Math
Problem Statement
You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation (RPN).
Evaluate the expression and 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 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
= 22
Constraints:
- 1 <= tokens.length <= 10^4
- tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].
🌟 ELI5: The Simple Idea!
What is Reverse Polish Notation (RPN)?
Normal notation (Infix): 2 + 3
Operator BETWEEN operands
Reverse Polish (Postfix): 2 3 +
Operator AFTER operands
Why RPN?
✓ No parentheses needed
✓ No operator precedence rules
✓ Easy to evaluate with a stack
How to evaluate:
"2 3 +" means "2 + 3"
Process left to right:
2 → Push to stack
3 → Push to stack
+ → Pop 3, pop 2, compute 2+3=5, push 5
Result: 5 ✓
"2 3 + 4 *" means "(2 + 3) * 4"
2 → Stack: [2]
3 → Stack: [2, 3]
+ → Pop 3, 2, push 5 → Stack: [5]
4 → Stack: [5, 4]
* → Pop 4, 5, push 20 → Stack: [20]
Result: 20 ✓
🎨 Visual Understanding
Example 1: Simple Expression
Input: ["2","1","+","3","*"]
Represents: (2 + 1) * 3 = 9
Process:
Token: "2"
Number → Push
Stack: [2]
Token: "1"
Number → Push
Stack: [2, 1]
Token: "+"
Operator → Pop two numbers
Pop: 1, 2
Compute: 2 + 1 = 3
Push result: 3
Stack: [3]
Token: "3"
Number → Push
Stack: [3, 3]
Token: "*"
Operator → Pop two numbers
Pop: 3, 3
Compute: 3 * 3 = 9
Push result: 9
Stack: [9]
Final result: 9 ✓
Example 2: Division
Input: ["4","13","5","/","+"]
Represents: 4 + (13 / 5) = 6
Process:
"4" → Stack: [4]
"13" → Stack: [4, 13]
"5" → Stack: [4, 13, 5]
"/" → Pop 5, 13, compute 13/5=2 → Stack: [4, 2]
"+" → Pop 2, 4, compute 4+2=6 → Stack: [6]
Result: 6 ✓
🎯 Approach: Stack Evaluation ⭐
The Standard Solution
Algorithm:
1. Create stack for numbers
2. For each token:
- If number: push to stack
- If operator: pop two numbers, compute, push result
3. Final stack top is the answer
Implementation
/**
* Stack-based RPN evaluation
* Time: O(n), Space: O(n)
*/
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (isOperator(token)) {
// Pop two operands
int b = stack.pop(); // Second operand
int a = stack.pop(); // First operand
// Compute based on operator
int result = compute(a, b, token);
// Push result
stack.push(result);
} else {
// It's a number
stack.push(Integer.parseInt(token));
}
}
// Final result is the only element left
return stack.pop();
}
private boolean isOperator(String token) {
return token.equals("+") || token.equals("-") ||
token.equals("*") || token.equals("/");
}
private int compute(int a, int b, String operator) {
switch (operator) {
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
case "/": return a / b;
default: throw new IllegalArgumentException();
}
}
⏰ Time: O(n) - Single pass through tokens
💾 Space: O(n) - Stack stores numbers
More Concise Version
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
switch (token) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
int divisor = stack.pop();
int dividend = stack.pop();
stack.push(dividend / divisor);
break;
default:
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
🔍 Super Detailed Dry Run
Example: tokens = ["2","1","+","3","*"]
Goal: Evaluate RPN expression = (2 + 1) * 3
═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════
stack = []
tokens = ["2","1","+","3","*"]
═══════════════════════════════════════════════════════════════
Iteration 1: token = "2"
═══════════════════════════════════════════════════════════════
Check: Is "2" an operator?
"+", "-", "*", "/" → No
Action: It's a number
Integer.parseInt("2") = 2
stack.push(2)
Stack: [2]
═══════════════════════════════════════════════════════════════
Iteration 2: token = "1"
═══════════════════════════════════════════════════════════════
Check: Is "1" an operator? No
Action: It's a number
Integer.parseInt("1") = 1
stack.push(1)
Stack: [2, 1]
═══════════════════════════════════════════════════════════════
Iteration 3: token = "+"
═══════════════════════════════════════════════════════════════
Check: Is "+" an operator? Yes
Action: Pop two operands and compute
b = stack.pop() = 1
a = stack.pop() = 2
Stack after pops: []
Compute: a + b = 2 + 1 = 3
stack.push(3)
Stack: [3]
Explanation:
We just evaluated "2 1 +" which is (2 + 1) = 3
═══════════════════════════════════════════════════════════════
Iteration 4: token = "3"
═══════════════════════════════════════════════════════════════
Check: Is "3" an operator? No
Action: It's a number
Integer.parseInt("3") = 3
stack.push(3)
Stack: [3, 3]
═══════════════════════════════════════════════════════════════
Iteration 5: token = "*"
═══════════════════════════════════════════════════════════════
Check: Is "*" an operator? Yes
Action: Pop two operands and compute
b = stack.pop() = 3
a = stack.pop() = 3
Stack after pops: []
Compute: a * b = 3 * 3 = 9
stack.push(9)
Stack: [9]
Explanation:
We just evaluated "3 3 *" which is (3 * 3) = 9
This uses the result from the previous operation
═══════════════════════════════════════════════════════════════
Final Result
═══════════════════════════════════════════════════════════════
All tokens processed
Stack contains: [9]
Return: stack.pop() = 9 ✓
Complete expression: (2 + 1) * 3 = 9
Example 2: tokens = ["4","13","5","/","+"]
Expression: 4 + (13 / 5)
"4" → Push 4 → [4]
"13" → Push 13 → [4, 13]
"5" → Push 5 → [4, 13, 5]
"/" → Pop 5, 13 → [4]
13 / 5 = 2
Push 2 → [4, 2]
"+" → Pop 2, 4 → []
4 + 2 = 6
Push 6 → [6]
Result: 6 ✓
Note: 13/5 in Java = 2 (truncates toward zero)
🎯 Why This Solution Works
The RPN Magic
Why RPN is stack-friendly:
Infix notation: 2 + 3 * 4
Need precedence rules
Need parentheses
Complex to evaluate
RPN notation: 2 3 4 * +
No precedence needed
No parentheses needed
Natural left-to-right evaluation
Stack naturally handles:
✓ Store operands
✓ Retrieve for operations
✓ Store intermediate results
Order of Operands Matters
CRITICAL: Pop order for non-commutative operations!
For subtraction:
"5 3 -" means 5 - 3 = 2
Stack: [5, 3]
Pop: b = 3, a = 5
Compute: a - b = 5 - 3 = 2 ✓
NOT: b - a = 3 - 5 = -2 ✗
For division:
"10 2 /" means 10 / 2 = 5
Stack: [10, 2]
Pop: b = 2, a = 10
Compute: a / b = 10 / 2 = 5 ✓
NOT: b / a = 2 / 10 = 0 ✗
General rule:
First pop = second operand (b)
Second pop = first operand (a)
Compute: a op b
Why Stack is Perfect
Every operation:
1. Takes most recent 2 values
2. Produces 1 result
3. Result becomes new "most recent"
This is EXACTLY what stack does!
Example: "1 2 + 3 4 + *"
1 2 + → 3 (intermediate result)
3 4 + → 7 (intermediate result)
3 7 * → 21 (final result)
Each intermediate result is pushed back
Ready for the next operation!
⚠️ Common Mistakes
Mistake 1: Wrong operand order
// ❌ WRONG - Order matters for - and /
int a = stack.pop();
int b = stack.pop();
stack.push(a - b); // Wrong order!
// ✓ CORRECT
int b = stack.pop(); // Second operand
int a = stack.pop(); // First operand
stack.push(a - b); // Correct order
Mistake 2: Inline pop for non-commutative ops
// ❌ WRONG - Evaluation order undefined!
case "-":
stack.push(stack.pop() - stack.pop());
// Could be (second - first) or (first - second)
// ✓ CORRECT - Explicit order
case "-":
int b = stack.pop();
int a = stack.pop();
stack.push(a - b);
Mistake 3: Not handling negative numbers
// ❌ WRONG - Treats "-11" as operator
if (token.equals("-")) {
// "-11" is a number, not operator!
}
// ✓ CORRECT - Parse as number
if (isOperator(token)) {
// Only operators: +, -, *, /
// Not numbers like "-11"
} else {
Integer.parseInt(token); // Handles negatives
}
Mistake 4: Using float division
// ❌ WRONG - Problem wants integer division
stack.push((int)(a / (float)b));
// ✓ CORRECT - Integer division truncates
stack.push(a / b);
Mistake 5: Not returning stack top
// ❌ WRONG - Returns stack size!
return stack.size();
// ✓ CORRECT - Return the result
return stack.pop();
🎯 Pattern Recognition
Problem Type: Expression Evaluation
Core Pattern: Stack Pattern 3 - Number Stack
When to Apply:
✓ Evaluate mathematical expressions
✓ RPN/Postfix notation
✓ Calculator implementations
✓ Expression parsing
Recognition Keywords:
- "reverse polish notation"
- "RPN"
- "postfix"
- "evaluate expression"
- "operators and operands"
Similar Problems:
- Baseball Game (LC 682) - Similar stack operations
- Basic Calculator (LC 224, 227) - Infix evaluation
- Basic Calculator III (LC 772) - Full calculator
- Different Ways to Add Parentheses (LC 241)
Key Components:
┌────────────────────────────────────────────┐
│ Stack: Store numbers and results │
│ Number: Push to stack │
│ Operator: Pop 2, compute, push result │
│ Order: First pop = b, second pop = a │
│ Compute: a op b │
│ Final: Pop stack for answer │
│ Time: O(n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is RPN evaluation"
Step 2: "I'll use a stack to track numbers"
Step 3: "Process each token left to right"
Key Points to Mention:
- RPN naturally works with stack
- Numbers: push to stack
- Operators: pop two, compute, push result
- Order matters for - and /: a op b
- Final answer is single value in stack
- Time: O(n), Space: O(n)
Walk Through Example:
"For ['2','1','+','3','*']:
'2' → Push: [2]
'1' → Push: [2,1]
'+' → Pop 1,2, compute 2+1=3, push: [3]
'3' → Push: [3,3]
'*' → Pop 3,3, compute 3*3=9, push: [9]
Result: 9"
Why Stack:
"RPN is designed for stack evaluation.
Operators always work on most recent values.
Stack provides O(1) access to recent values.
Results become new inputs naturally."
Critical Detail:
"Order matters for - and /:
First pop is second operand
Second pop is first operand
Compute: (second pop) op (first pop)"
Complexity:
"Time: O(n) - single pass through tokens.
Space: O(n) - stack stores intermediate results.
Optimal for this problem."
Edge Cases to Mention:
✓ Single number
✓ Negative numbers
✓ Division truncation
✓ Long expressions
📝 Quick Revision Notes
🎯 Core Concept:
Evaluate RPN: Use stack for numbers. Number → push. Operator → pop two (b=first, a=second), compute a op b, push result. Final: pop stack for answer. Order critical for - and /.
⚡ Quick Implementation:
import java.util.Stack;
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
int num1 = 0;
int num2 = 0;
for(String token : tokens) {
switch (token) {
case "+":
num2 = stack.pop();
num1 = stack.pop();
stack.push(num1 + num2);
break;
case "-":
num2 = stack.pop();
num1 = stack.pop();
stack.push(num1 - num2);
break;
case "*":
num2 = stack.pop();
num1 = stack.pop();
stack.push(num1 * num2);
break;
case "/":
num2 = stack.pop();
num1 = stack.pop();
stack.push(num1 / num2);
break;
default:
stack.push(Integer.parseInt(token));
break;
}
}
return stack.pop();
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.evalRPN(new String[] {"2","1","+","3","*"}) == 9);
System.out.println(s.evalRPN(new String[] {"4","13","5","/","+"}) == 6);
System.out.println(s.evalRPN(new String[] {"10","6","9","3","+","-11","*","/","*","17","+","5","+"}) == 22);
}
}
🔑 Key Insights:
- Pattern: Stack Pattern 3 (Number Stack)
- RPN: Operators AFTER operands
- Pop order: b first, a second
- Compute: a op b (NOT b op a)
- Handles: Negative numbers via parseInt
- Time: O(n), Space: O(n) ✓
🎪 Memory Aid:
"Numbers push, operators pop-compute-push!"
"Push nums, pop b-a, compute a op b!" ✨
⚠️ Critical Order:
For "-" and "/" operations:
❌ WRONG ORDER:
int a = stack.pop();
int b = stack.pop();
result = a - b; // Reversed!
Example: "5 3 -"
Stack: [5, 3]
Pop a=3, b=5
Compute: 3-5 = -2 ✗ (should be 2)
✓ CORRECT ORDER:
int b = stack.pop(); // Second operand
int a = stack.pop(); // First operand
result = a - b; // Correct!
Example: "5 3 -"
Stack: [5, 3]
Pop b=3, a=5
Compute: 5-3 = 2 ✓
🧪 Edge Cases
Case 1: Single number
Input: ["42"]
Output: 42
No operations
Case 2: Negative numbers
Input: ["3","-4","+"]
Output: -1
Handles negative input
Case 3: Division truncation
Input: ["10","3","/"]
Output: 3
10/3 = 3.33... → 3 (truncates)
Case 4: Multiple operations
Input: ["2","1","+","3","*"]
Output: 9
(2+1)*3 = 9
Case 5: Complex expression
Input: ["4","13","5","/","+"]
Output: 6
4+(13/5) = 4+2 = 6
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(n)
Where n = tokens.length
Single pass: O(n)
for (String token : tokens)
Per token: O(1)
- isOperator check: O(1)
- parseInt: O(1) for given constraints
- Pop: O(1)
- Compute: O(1)
- Push: O(1)
Total: O(n) ✓
Space Complexity: O(n)
Stack space:
Worst case: all numbers
Example: ["1","2","3","4","5"]
Stack: [1,2,3,4,5]
Then all operations at end
Maximum stack size ≤ n
Total: O(n) ✓
🔄 Infix vs RPN Comparison
Expression: (2 + 3) * 4
Infix notation: (2 + 3) * 4
✗ Need parentheses
✗ Need precedence rules
✗ Complex to evaluate
RPN notation: 2 3 + 4 *
✓ No parentheses needed
✓ No precedence rules
✓ Simple stack evaluation
Evaluation steps (RPN):
2 → [2]
3 → [2,3]
+ → [5]
4 → [5,4]
* → [20]
That's it! Natural left-to-right!
📚 Related Problems
Same Pattern: - Baseball Game (LC 682) - Similar stack operations - Crawler Log Folder (LC 1598) - Stack state tracking
Expression Evaluation: - Basic Calculator (LC 224) - Infix with +,-,() - Basic Calculator II (LC 227) - Infix with +,-,*,/ - Basic Calculator III (LC 772) - Full calculator - Different Ways to Add Parentheses (LC 241)
Advanced: - Expression Add Operators (LC 282) - Generate expressions
Happy practicing! 🎯
Note: This problem teaches Stack Pattern 3: Number Stack with operations! Master this and you understand: (1) RPN evaluation, (2) operator precedence elimination, (3) stack for intermediate results, (4) operand order importance. This is the foundation for calculator problems! Very common at Amazon, Meta, Apple! 💪✨