Evaluate Reverse Polish Notation
You're given an array of strings tokens that spells out an arithmetic expression in Reverse Polish (postfix) notation, where each operator comes after its two operands. For example, ["5","3","-"] means 5 - 3 and ["2","3","4","*","+"] means 2 + 3 * 4. Each token is an integer (possibly negative, like "-11") or one of "+", "-", "*", "/". Return the value of the expression. Division truncates toward zero, so 7 / -2 is -3. The input is always valid and never divides by zero.
Examples
tokens = ["2","1","+","3","*"] returns 9
2 and 1 combine under + to give 3, and 3 and 3 combine under * to give 9. In ordinary notation that is (2 + 1) * 3.
tokens = ["4","13","5","/","+"] returns 6
13 / 5 is 2.6, which truncates to 2, and then 4 + 2 = 6. In ordinary notation that is 4 + (13 / 5).
tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] returns 22
9 + 3 = 12, then 12 * -11 = -132, and 6 / -132 truncates to 0. 10 * 0 = 0, then 0 + 17 = 17 and 17 + 5 = 22.
Constraints
- 1 <= tokens.length <= 10^4
- tokens[i] is an operator ("+", "-", "*", "/") or an integer in the range [-200, 200].
- The input is a valid expression in Reverse Polish notation.
- The answer and every intermediate result fit in a 32-bit integer.
Hints
Read the tokens left to right. When you reach an operator, its two operands are the two most recent values you haven't used yet.
Use a stack of integers: numbers are pushed, and each operator pops two values and pushes one result.
For each token: if it's a number, push it. If it's an operator, pop b (the right operand) and then a (the left operand), and push a op b with division truncating toward zero. When the tokens run out, the one value left on the stack is the answer.
Drill This: Your Approach First
Approach
In postfix notation an operator always applies to the two most recent values that haven't been used yet, which is last-in, first-out order, so a stack evaluates the expression in one pass. Push each number; on an operator, pop the right operand first, then the left, and push the result, truncating division toward zero. A valid expression leaves exactly one value, the answer. O(n) time and O(n) space for the stack.
Time
O(n)
Space
O(n)
Pitfall
Solutions
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String t : tokens) {
switch (t) {
case "+" -> stack.push(stack.pop() + stack.pop());
case "*" -> stack.push(stack.pop() * stack.pop());
case "-" -> {
int b = stack.pop();
stack.push(stack.pop() - b);
}
case "/" -> {
int b = stack.pop();
stack.push(stack.pop() / b);
}
default -> stack.push(Integer.parseInt(t));
}
}
return stack.pop();
}
}class Solution:
def evalRPN(self, tokens) -> int:
stack = []
for t in tokens:
if t in ("+", "-", "*", "/"):
b = stack.pop()
a = stack.pop()
if t == "+":
stack.append(a + b)
elif t == "-":
stack.append(a - b)
elif t == "*":
stack.append(a * b)
else:
stack.append(int(a / b)) # truncate toward zero
else:
stack.append(int(t))
return stack[0]