LeetCode 150 - Evaluate Reverse Polish Notation
This problem asks us to evaluate an arithmetic expression written in Reverse Polish Notation, also called postfix notation. Instead of placing operators between operands as in standard infix notation, Reverse Polish Notation places operators after their operands.
Difficulty: 🟡 Medium
Topics: Array, Math, Stack
Solution
LeetCode 150, Evaluate Reverse Polish Notation
Problem Understanding
This problem asks us to evaluate an arithmetic expression written in Reverse Polish Notation, also called postfix notation. Instead of placing operators between operands as in standard infix notation, Reverse Polish Notation places operators after their operands.
For example, the infix expression:
(2 + 1) * 3
becomes:
2 1 + 3 *
The input is given as an array of strings called tokens. Each token is either:
- An integer value
- One of the four operators:
+,-,*,/
The goal is to evaluate the entire expression and return the final integer result.
A very important detail is how division behaves. Integer division must truncate toward zero. This matters especially for negative numbers. For example:
6 / -132 = 0
because the decimal result is truncated toward zero instead of rounded down.
The problem guarantees several important properties:
- The expression is always valid
- There will never be division by zero
- Intermediate results fit inside a 32-bit integer
- Every operator will always have enough operands available
The constraint tokens.length <= 10^4 tells us the solution should be efficient. A quadratic solution would be unnecessarily slow for large inputs, while a linear solution is ideal.
Some important edge cases include:
- Expressions containing only a single number
- Negative operands
- Division involving negative numbers
- Long chains of operations
- Nested expressions represented implicitly through postfix ordering
A naive implementation can easily mishandle operand order for subtraction and division. Since postfix notation evaluates operands in sequence, the second popped value is actually the left operand.
For example:
["4", "2", "-"]
means:
4 - 2
not:
2 - 4
This is one of the most common mistakes in this problem.
Approaches
Brute Force Approach
A brute force strategy would repeatedly scan the token array looking for patterns of:
number number operator
Whenever such a pattern is found, we compute the result and replace those three tokens with the computed value.
For example:
["2","1","+","3","*"]
would become:
["3","3","*"]
then:
["9"]
This approach works because every valid postfix expression eventually reduces to a single value after repeatedly evaluating local operations.
However, this method is inefficient because each reduction may require shifting elements in the array, and we may repeatedly rescan the list. In the worst case, this leads to quadratic time complexity.
Optimal Approach, Stack
The key observation is that Reverse Polish Notation naturally matches stack behavior.
When we encounter a number, we store it because it may be used later by an operator.
When we encounter an operator, we immediately apply it to the two most recent operands.
A stack is perfect for this because:
- The most recent operands are always the next ones needed
- Push operations store operands
- Pop operations retrieve operands in reverse order
This allows us to process the expression in a single left-to-right pass.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(n) | Repeatedly rescans and modifies the token list |
| Optimal | O(n) | O(n) | Uses a stack for single-pass evaluation |
Algorithm Walkthrough
- Create an empty stack to store intermediate integer values.
- Iterate through each token in the input array from left to right.
- For each token, determine whether it is an operator or an integer.
- If the token is an integer:
- Convert it to an integer
- Push it onto the stack
This stores the operand until it is needed by a future operator. 5. If the token is an operator:
- Pop the top value from the stack, this is the right operand
- Pop the next value from the stack, this is the left operand
The order matters because subtraction and division are not commutative. 6. Apply the operator to the two operands.
+performs addition-performs subtraction*performs multiplication/performs integer division truncated toward zero
- Push the computed result back onto the stack.
This result may itself become an operand for future operations. 8. Continue processing until all tokens have been evaluated. 9. After processing completes, the stack contains exactly one value, the final result. Return it.
Why it works
The algorithm maintains an important invariant:
After processing any prefix of the token list, the stack contains exactly the intermediate results needed to evaluate the remaining expression.
Every operand is pushed exactly once, and every operator consumes exactly two operands and produces exactly one new value. Since postfix notation guarantees that operands appear before their operators, the stack always contains the correct operands at the moment an operator is encountered.
Because the input expression is guaranteed to be valid, the algorithm will finish with exactly one value remaining on the stack, which is the correct final result.
Python Solution
from typing import List
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
operators = {"+", "-", "*", "/"}
for token in tokens:
if token not in operators:
stack.append(int(token))
else:
right = stack.pop()
left = stack.pop()
if token == "+":
result = left + right
elif token == "-":
result = left - right
elif token == "*":
result = left * right
else:
result = int(left / right)
stack.append(result)
return stack[-1]
The implementation follows the stack-based algorithm directly.
We first create an empty stack and define a set containing the valid operators. Using a set allows constant-time operator checks.
As we iterate through the tokens:
- Numbers are converted to integers and pushed onto the stack.
- Operators trigger evaluation.
When an operator appears, we pop two operands from the stack. The first popped value is the right operand, and the second popped value is the left operand.
For division, we use:
int(left / right)
This is important because Python's floor division operator // rounds downward for negative numbers instead of truncating toward zero.
For example:
-3 // 2 == -2
but the problem requires:
-3 / 2 == -1
Using int(left / right) correctly truncates toward zero.
Finally, the stack contains one value, which we return as the answer.
Go Solution
package main
import "strconv"
func evalRPN(tokens []string) int {
stack := []int{}
operators := map[string]bool{
"+": true,
"-": true,
"*": true,
"/": true,
}
for _, token := range tokens {
if !operators[token] {
num, _ := strconv.Atoi(token)
stack = append(stack, num)
} else {
right := stack[len(stack)-1]
stack = stack[:len(stack)-1]
left := stack[len(stack)-1]
stack = stack[:len(stack)-1]
var result int
switch token {
case "+":
result = left + right
case "-":
result = left - right
case "*":
result = left * right
case "/":
result = left / right
}
stack = append(stack, result)
}
}
return stack[len(stack)-1]
}
The Go implementation is very similar to the Python version, but there are a few language-specific differences.
Go slices are used as stacks. Appending pushes a value, and slicing removes the last element.
String-to-integer conversion uses:
strconv.Atoi(token)
Go integer division already truncates toward zero, so no special handling is needed for division.
Unlike Python, Go requires explicit stack index management when popping values.
Worked Examples
Example 1
Input:
["2","1","+","3","*"]
| Token | Action | Stack |
|---|---|---|
"2" |
Push 2 | [2] |
"1" |
Push 1 | [2, 1] |
"+" |
Pop 1 and 2, compute 2 + 1 | [3] |
"3" |
Push 3 | [3, 3] |
"*" |
Pop 3 and 3, compute 3 * 3 | [9] |
Final answer:
9
Example 2
Input:
["4","13","5","/","+"]
| Token | Action | Stack |
|---|---|---|
"4" |
Push 4 | [4] |
"13" |
Push 13 | [4, 13] |
"5" |
Push 5 | [4, 13, 5] |
"/" |
Compute 13 / 5 = 2 | [4, 2] |
"+" |
Compute 4 + 2 = 6 | [6] |
Final answer:
6
Example 3
Input:
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
| Token | Action | Stack |
|---|---|---|
"10" |
Push 10 | [10] |
"6" |
Push 6 | [10, 6] |
"9" |
Push 9 | [10, 6, 9] |
"3" |
Push 3 | [10, 6, 9, 3] |
"+" |
Compute 9 + 3 = 12 | [10, 6, 12] |
"-11" |
Push -11 | [10, 6, 12, -11] |
"*" |
Compute 12 * -11 = -132 | [10, 6, -132] |
"/" |
Compute 6 / -132 = 0 | [10, 0] |
"*" |
Compute 10 * 0 = 0 | [0] |
"17" |
Push 17 | [0, 17] |
"+" |
Compute 0 + 17 = 17 | [17] |
"5" |
Push 5 | [17, 5] |
"+" |
Compute 17 + 5 = 22 | [22] |
Final answer:
22
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Each token is processed exactly once |
| Space | O(n) | The stack may store up to n operands |
The algorithm performs a constant amount of work for each token. Every number is pushed once, and every operator pops two values and pushes one result. Since no token is revisited, the total runtime is linear.
The stack can grow proportionally to the number of operands in the expression, so the worst-case auxiliary space complexity is linear.
Test Cases
from typing import List
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
operators = {"+", "-", "*", "/"}
for token in tokens:
if token not in operators:
stack.append(int(token))
else:
right = stack.pop()
left = stack.pop()
if token == "+":
stack.append(left + right)
elif token == "-":
stack.append(left - right)
elif token == "*":
stack.append(left * right)
else:
stack.append(int(left / right))
return stack[-1]
solution = Solution()
assert solution.evalRPN(["2", "1", "+", "3", "*"]) == 9
# Basic nested operations
assert solution.evalRPN(["4", "13", "5", "/", "+"]) == 6
# Division before addition
assert solution.evalRPN(
["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
) == 22
# Complex nested expression
assert solution.evalRPN(["5"]) == 5
# Single operand only
assert solution.evalRPN(["3", "-4", "+"]) == -1
# Negative number handling
assert solution.evalRPN(["7", "3", "/"]) == 2
# Positive division truncation
assert solution.evalRPN(["-7", "3", "/"]) == -2
# Negative division truncates toward zero
assert solution.evalRPN(["4", "2", "-"]) == 2
# Correct operand order for subtraction
assert solution.evalRPN(["2", "3", "*"]) == 6
# Multiplication
assert solution.evalRPN(["15", "7", "1", "1", "+", "-", "/", "3", "*", "2", "1", "1", "+", "+", "-"]) == 5
# Large classic RPN example
| Test | Why |
|---|---|
["2", "1", "+", "3", "*"] |
Validates basic stack evaluation |
["4", "13", "5", "/", "+"] |
Tests integer division |
| Complex nested example | Validates multiple chained operations |
["5"] |
Tests single-value input |
["3", "-4", "+"] |
Tests negative operands |
["7", "3", "/"] |
Tests positive truncating division |
["-7", "3", "/"] |
Tests negative truncation behavior |
["4", "2", "-"] |
Verifies operand order correctness |
["2", "3", "*"] |
Simple multiplication case |
| Large classic example | Stress test for stack operations |
Edge Cases
Single Number Input
An expression may contain only one token, such as:
["42"]
A naive implementation might assume every expression contains operators and attempt invalid stack pops.
The current implementation handles this naturally because numbers are simply pushed onto the stack, and if no operators appear, the single value remains as the final result.
Negative Division
Division involving negative numbers is a common source of bugs because programming languages differ in how integer division behaves.
For example:
["-7", "3", "/"]
should produce:
-2
not:
-3
Python's // operator rounds downward, which would give the wrong answer. Using:
int(left / right)
ensures truncation toward zero, exactly matching the problem requirements.
Operand Order for Subtraction and Division
Subtraction and division are not commutative, so operand order matters.
For example:
["4", "2", "-"]
means:
4 - 2
not:
2 - 4
A common mistake is reversing the popped operands.
The implementation avoids this by assigning:
right = stack.pop()
left = stack.pop()
and then evaluating:
left operator right
which preserves the correct evaluation order.