[Medium] 150. Evaluate Reverse Polish Notation
This is a classic stack problem that requires evaluating mathematical expressions written in Reverse Polish Notation (RPN). The key insight is using a stack to process operands and operators in the correct order.
Given an array of strings representing a valid Reverse Polish Notation expression, evaluate the expression and return the result.
In Reverse Polish Notation:
- Operands come before operators
- Each operator takes its two preceding operands
- Division truncates 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: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = 22
Constraints
- 1 <= tokens.length <= 10^4
- tokens[i] is either an operator: “+”, “-“, “*”, or “/”, or an integer in the range [-200, 200]
Thinking Process
The solution uses a stack-based approach:
- Stack Processing: Use a stack to store operands
- Operator Detection: Check if current token is an operator
- Operation Execution: Pop two operands, perform operation, push result
- Final Result: The remaining element in stack is the answer
Common Approaches
Typical techniques for this pattern:
| Approach | Time | Space | Notes |
|---|---|---|---|
| Monotonic stack (this problem) | O(n) | O(n) | Next greater/smaller element |
| Parentheses matching | O(n) | O(n) | Push open, pop on close |
| Expression evaluation | O(n) | O(n) | Operand + operator stacks |
| Stack simulation | O(n) | O(n) | Process in LIFO order |
Solution
Time Complexity: O(n) - Process each token once
Space Complexity: O(n) - Stack can hold up to n/2 operands
java
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stk = new ArrayDeque<>();
Set<String> ops = Set.of("+", "-", "*", "/");
for (String token : tokens) {
if (!ops.contains(token)) {
stk.push(Integer.parseInt(token));
} else {
int b = stk.pop();
int a = stk.pop();
switch (token) {
case "+" -> stk.push(a + b);
case "-" -> stk.push(a - b);
case "*" -> stk.push(a * b);
case "/" -> stk.push(a / b);
}
}
}
return stk.pop();
}
}
Solution Explanation
Approach: Monotonic stack (this problem)
Key idea: The solution uses a stack-based approach:
How the code works:
- Stack Processing: Use a stack to store operands
- Operator Detection: Check if current token is an operator
- Operation Execution: Pop two operands, perform operation, push result
- Final Result: The remaining element in stack is the answer
Walkthrough — input tokens = ["2","1","+","3","*"], expected output 9:
((2 + 1) * 3) = 9
Step-by-Step Example
Let’s trace through Solution 1 with tokens = ["2","1","+","3","*"]:
Step 1: Process “2”
- Not an operator, push to stack:
[2]
Step 2: Process “1”
- Not an operator, push to stack:
[2, 1]
Step 3: Process “+”
- Operator detected, pop two operands:
num2=1, num1=2 - Perform addition:
2 + 1 = 3 - Push result to stack:
[3]
Step 4: Process “3”
- Not an operator, push to stack:
[3, 3]
Step 5: Process “*”
- Operator detected, pop two operands:
num2=3, num1=3 - Perform multiplication:
3 * 3 = 9 - Push result to stack:
[9]
Result: 9
Common Mistakes
- Single Operand: Expression with only one number
- Negative Numbers: Tokens like “-11” (length > 1)
- Division by Zero: Not possible with valid RPN
-
Large Numbers: Integer overflow considerations
- Operand Order: Swapping the order of popped operands
- Negative Number Detection: Not handling multi-character tokens correctly
- Stack Underflow: Not checking if stack has enough operands
- Integer Division: Forgetting that division truncates toward zero
References
- LC 150: Evaluate Reverse Polish Notation on LeetCode
- LeetCode Discuss — LC 150: Evaluate Reverse Polish Notation
- LeetCode Editorial (may require premium)
Key Takeaways
- Stack LIFO: Last In, First Out property matches RPN evaluation order
- Operator Precedence: RPN eliminates need for operator precedence rules
- Operand Order: First popped operand is the second operand in the operation
- Integer Division: Division truncates toward zero (C++ behavior)