Language Selection
Choose your preferred programming language
Showing: Python
Evaluate Reverse Polish Notation
Problem Statement
Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, and /. Each operand may be an integer or another expression.
Note that division between two integers should truncate toward zero.
It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result and there will not be any division by zero operation.
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
Constraints
1 <= tokens.length <= 10^4tokens[i]is either an operator:"+","-","*", or"/", or an integer in the range[-200, 200]
Approach 1: Stack-Based Evaluation (Optimal)
Algorithm
Use a stack to evaluate the Reverse Polish Notation expression.
Steps:
- Use a stack to store operands
- For each token:
- If it’s a number, push it to the stack
- If it’s an operator, pop two operands, perform the operation, and push the result
- Return the final result from the stack
Implementation
Python:
def evalRPN(tokens):
"""
Evaluate Reverse Polish Notation using stack
Time: O(n)
Space: O(n)
"""
stack = []
for token in tokens:
if token in ["+", "-", "*", "/"]:
# Pop two operands
b = stack.pop()
a = stack.pop()
# Perform operation
if token == "+":
result = a + b
elif token == "-":
result = a - b
elif token == "*":
result = a * b
elif token == "/":
result = int(a / b) # Truncate toward zero
stack.append(result)
else:
# Push number to stack
stack.append(int(token))
return stack[0]
Java:
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String token : tokens) {
if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
// Pop two operands
int b = stack.pop();
int a = stack.pop();
// Perform operation
int result;
switch (token) {
case "+":
result = a + b;
break;
case "-":
result = a - b;
break;
case "*":
result = a * b;
break;
case "/":
result = a / b; // Truncate toward zero
break;
default:
result = 0;
}
stack.push(result);
} else {
// Push number to stack
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
Go:
func evalRPN(tokens []string) int {
stack := make([]int, 0)
for _, token := range tokens {
if token == "+" || token == "-" || token == "*" || token == "/" {
// Pop two operands
b := stack[len(stack)-1]
stack = stack[:len(stack)-1]
a := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// Perform operation
var result int
switch token {
case "+":
result = a + b
case "-":
result = a - b
case "*":
result = a * b
case "/":
result = a / b // Truncate toward zero
}
stack = append(stack, result)
} else {
// Push number to stack
num, _ := strconv.Atoi(token)
stack = append(stack, num)
}
}
return stack[0]
}
JavaScript:
function evalRPN(tokens) {
const stack = [];
for (const token of tokens) {
if (token === "+" || token === "-" || token === "*" || token === "/") {
// Pop two operands
const b = stack.pop();
const a = stack.pop();
// Perform operation
let result;
switch (token) {
case "+":
result = a + b;
break;
case "-":
result = a - b;
break;
case "*":
result = a * b;
break;
case "/":
result = Math.trunc(a / b); // Truncate toward zero
break;
}
stack.push(result);
} else {
// Push number to stack
stack.push(parseInt(token));
}
}
return stack[0];
}
C#:
public class Solution {
public int EvalRPN(string[] tokens) {
var stack = new Stack<int>();
foreach (string token in tokens) {
if (token == "+" || token == "-" || token == "*" || token == "/") {
// Pop two operands
int b = stack.Pop();
int a = stack.Pop();
// Perform operation
int result;
switch (token) {
case "+":
result = a + b;
break;
case "-":
result = a - b;
break;
case "*":
result = a * b;
break;
case "/":
result = a / b; // Truncate toward zero
break;
default:
result = 0;
break;
}
stack.Push(result);
} else {
// Push number to stack
stack.Push(int.Parse(token));
}
}
return stack.Pop();
}
}
Complexity Analysis
- Time Complexity: O(n) - Each token is processed once
- Space Complexity: O(n) - For the stack
Key Insights
- Stack-Based Evaluation: Use stack to store operands and perform operations
- Postfix Notation: Operands come before operators in RPN
- Division Truncation: Division should truncate toward zero
- Operator Precedence: RPN eliminates the need for operator precedence
- Recursive Approach: Alternative approach using recursion
Edge Cases
- Single Number:
["5"]→5 - Negative Numbers:
["-2", "3", "+"]→1 - Division by Zero: Not possible as per problem constraints
- Large Numbers: Handle integer overflow
- Mixed Operations:
["2", "1", "+", "3", "*"]→9
Follow-up Questions
- Infix to Postfix: How would you convert infix to postfix notation?
- Different Operators: What if you have more operators like ^, %?
- Floating Point: What if you need to handle floating point numbers?
- Error Handling: How would you handle invalid expressions?
Common Mistakes
- Division Truncation: Not truncating division toward zero
- Operand Order: Swapping the order of operands for subtraction and division
- Stack Management: Not properly managing stack operations
- Type Conversion: Not converting string tokens to integers
Interview Tips
- Clarify Requirements: Ask about division behavior and operator support
- Discuss Approaches: Mention both stack and recursive approaches
- Handle Edge Cases: Discuss single numbers and negative numbers
- Explain Algorithm: Walk through the stack-based evaluation process
- Consider Optimizations: Discuss space and time optimizations