Evaluate Reverse Polish Notation
Problem
Given an array of strings tokens representing an arithmetic expression in Reverse Polish Notation, return the evaluation of the expression.
- 1 ≤ tokens.length ≤ 10⁴
- tokens[i] is either an operator: '+', '-', '*', or '/', or an integer in string format
- The given RPN expression is always valid
Example
tokens = ["2", "1", "+", "3", "*"]9The expression corresponds to ((2 + 1) * 3). The algorithm processes tokens sequentially: push 2 and 1 onto the stack, encounter '+', pop 1 and 2, compute 2 + 1 = 3, push 3 back. Next, push 3, encounter '*', pop 3 and 3, compute 3 * 3 = 9, push 9. The final stack top is 9, the result.
Approach
Straightforward Solution
A naive approach might try to recursively parse the expression or convert it to infix notation, which is complex and inefficient. Alternatively, scanning tokens and evaluating operators immediately without a stack would fail to maintain correct operand order.
Core Observation
Reverse Polish Notation expressions can be evaluated using a stack because each operator applies to the two most recent operands. This last-in-first-out property aligns naturally with stack operations.
Path to Optimal
The key recognition signals are 'Reverse Polish Notation', 'operators apply to previous two operands', and 'evaluate expression'. These indicate the Stack pattern because the problem requires last-in-first-out access to operands. By pushing operands onto a stack and applying operators to the top two elements, the algorithm maintains correct evaluation order and handles nested expressions naturally.
Optimal Approach
Iterate through tokens. For operands, convert to integer and push onto the stack. For operators, pop the top two operands, apply the operator in correct order (paying attention to subtraction and division), and push the result back. After processing all tokens, the stack contains the final result. This approach runs in O(n) time with O(n) space.
Time
O(n)
Each token is processed exactly once. Stack push and pop operations are O(1), so total time is linear in the number of tokens.
Space
O(n)
In the worst case, all tokens are operands and pushed onto the stack, requiring O(n) auxiliary space proportional to input size.
Pattern Spotlight
Stack (Expression Evaluation)
Use a stack to store operands and apply operators to the top two elements, ensuring correct operand order and enabling linear-time evaluation of postfix expressions.
Solution
| 1 | class Solution:
|
| 2 | def evalRPN(self, tokens: list[str]) -> int:
|
| 3 | stack = []
|
| 4 | for c in tokens:
|
| 5 | if c == "+":
|
| 6 | stack.append(stack.pop() + stack.pop())
|
| 7 | elif c == "-":
|
| 8 | a, b = stack.pop(), stack.pop()
|
| 9 | stack.append(b - a)
|
| 10 | elif c == "*":
|
| 11 | stack.append(stack.pop() * stack.pop())
|
| 12 | elif c == "/":
|
| 13 | a, b = stack.pop(), stack.pop()
|
| 14 | stack.append(int(b / a))
|
| 15 | else:
|
| 16 | stack.append(int(c))
|
| 17 | return stack[0] |
| 1 | class Solution { |
| 2 | public int evalRPN(String[] tokens) { |
| 3 | Deque<Integer> stack = new ArrayDeque<>(); |
| 4 | |
| 5 | for (String token : tokens) { |
| 6 | if (token.equals("+")) { |
| 7 | stack.push(stack.pop() + stack.pop()); |
| 8 | } else if (token.equals("-")) { |
| 9 | int a = stack.pop(); |
| 10 | int b = stack.pop(); |
| 11 | stack.push(b - a); |
| 12 | } else if (token.equals("*")) { |
| 13 | stack.push(stack.pop() * stack.pop()); |
| 14 | } else if (token.equals("/")) { |
| 15 | int a = stack.pop(); |
| 16 | int b = stack.pop(); |
| 17 | stack.push(b / a); |
| 18 | } else { |
| 19 | stack.push(Integer.parseInt(token)); |
| 20 | } |
| 21 | } |
| 22 | |
| 23 | return stack.peek(); |
| 24 | } |
| 25 | } |
Step-by-Step Solution
Initialize an Empty Stack to Store Operands
| 3 | stack = []
|
Objective
To prepare a data structure that will hold operands and intermediate results during evaluation.
Key Insight
A stack perfectly models the evaluation order of Reverse Polish Notation expressions. By pushing operands and popping them when an operator is encountered, the algorithm maintains the correct order of operations without recursion or complex parsing.
Interview Quick-Check
Core Logic
The stack stores operands and intermediate results, enabling last-in-first-out access required by RPN evaluation.
Common Pitfalls & Bugs
Using a queue or list without stack semantics would fail to maintain correct operand order.
Iterate Through Tokens and Evaluate Expression Using Stack Operations
| 4 | for c in tokens:
|
| 5 | if c == "+":
|
| 6 | stack.append(stack.pop() + stack.pop())
|
| 7 | elif c == "-":
|
| 8 | a, b = stack.pop(), stack.pop()
|
| 9 | stack.append(b - a)
|
| 10 | elif c == "*":
|
| 11 | stack.append(stack.pop() * stack.pop())
|
| 12 | elif c == "/":
|
| 13 | a, b = stack.pop(), stack.pop()
|
| 14 | stack.append(int(b / a))
|
| 15 | else:
|
| 16 | stack.append(int(c))
|
Objective
To process each token, pushing operands or applying operators to the top two operands on the stack.
Key Insight
The algorithm distinguishes operators from operands. For operators, it pops the top two operands, applies the operator in the correct order (important for '-' and '/'), and pushes the result back. For operands, it converts the string to an integer and pushes it. This approach ensures correct evaluation order and handles all valid RPN expressions in a single pass.
Interview Quick-Check
Core Logic
For each operator, pop the top two operands, apply the operator with correct operand order, and push the result; for operands, convert and push.
State & Boundaries
Ensure the stack always has at least two operands before applying an operator to avoid runtime errors.
Common Pitfalls & Bugs
Incorrect operand order for subtraction and division leads to wrong results; the second popped operand is the left operand.
Complexity
Each token is processed once, and stack operations are O(1), resulting in O(n) time complexity.
Return the Final Result from the Stack
| 17 | return stack[0] |
Objective
To output the evaluated integer result after processing all tokens.
Key Insight
After processing all tokens, the stack contains exactly one element: the final evaluation result. Returning this element completes the evaluation process.
Interview Quick-Check
Core Logic
The final stack element is the result of the entire RPN expression evaluation.
State & Boundaries
The stack should contain exactly one element at this point; otherwise, the input expression was invalid.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
stack.append(stack.pop() + stack.pop())Pop the top two operands, add them, and push the result back onto the stack.
This line performs the core arithmetic operation for addition, combining the two most recent operands and maintaining the stack state for further evaluation.
stack.append(stack.pop() * stack.pop())Pop the top two operands, multiply them, and push the result.
This line executes the multiplication operation and maintains the stack state for further processing.
stack.append(int(b / a))Perform integer division with truncation toward zero and push the result.
Using int(b / a) ensures division truncates toward zero as required, which differs from floor division and is critical for correctness.
a, b = stack.pop(), stack.pop()Pop the top two operands in correct order for subtraction.
Popping operands in this order ensures the left operand is the second popped value, preserving correct subtraction semantics.
a, b = stack.pop(), stack.pop()Pop the top two operands in correct order for division.
Popping operands in this order ensures the left operand is the second popped value, preserving correct division semantics.
return stack[0]Return the final evaluated result from the top of the stack.
After processing all tokens, the stack contains exactly one element representing the fully evaluated expression, which is the correct output.
stack = []Initialize an empty stack to hold operands and intermediate results.
The stack is essential for storing operands in a last-in-first-out manner, which aligns perfectly with the evaluation order of Reverse Polish Notation expressions.
stack.append(b - a)Compute the difference (left operand minus right operand) and push the result.
This line applies subtraction correctly and updates the stack with the intermediate result, enabling continued evaluation.
else:If the token is not an operator, convert it to an integer and push onto the stack.
This line handles operands by converting string tokens to integers and storing them for future operations, enabling the stack-based evaluation.
if c == "+":Check if the current token is the addition operator '+'.
Identifying operators allows the algorithm to apply the correct arithmetic operation to the top two operands on the stack.
elif c == "-":Check if the current token is the subtraction operator '-'.
Detecting subtraction is necessary to apply the correct operation with attention to operand order.
elif c == "*":Check if the current token is the multiplication operator '*'.
Recognizing multiplication allows the algorithm to perform the corresponding arithmetic operation on the top two operands.
elif c == "/":Check if the current token is the division operator '/'.
Identifying division is essential to apply the correct arithmetic operation with proper operand order and truncation.
for c in tokens:Begin iterating over each token in the input list.
Sequentially processing tokens ensures the algorithm respects the order of the RPN expression, which is critical for correct evaluation.
stack.append(int(c))End of the for loop iteration over tokens.
Completing the iteration ensures all tokens are processed in order, maintaining the integrity of the evaluation.
Test Your Understanding
Why must the operator apply to the two most recently pushed operands, and why is operand order important for subtraction and division?
Because Reverse Polish Notation defines operators to apply to the two immediately preceding operands, which are naturally accessed via a stack's last-in-first-out order. Operand order matters for subtraction and division since these operations are not commutative; the second popped operand is the left operand, and the first popped is the right operand.
Related Problems
Stacks pattern
Don't just read it. Drill it.
Reconstruct Evaluate Reverse Polish Notation from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Evaluate Reverse Polish Notation drill