Evaluate Reverse Polish Notation
Last Updated: March 29, 2026
Understanding the Problem
We are given a mathematical expression, but not in the usual infix notation like (2 + 1) * 3. Instead, it is written in Reverse Polish Notation (RPN), also called postfix notation. In RPN, the operator comes after its two operands. So 2 + 1 becomes 2 1 +, and (2 + 1) * 3 becomes 2 1 + 3 *.
The beauty of RPN is that it does not need parentheses. The order of operations is completely determined by the position of operators relative to operands. Every time we encounter an operator, we know it applies to the two most recent operands. This "last in, first out" behavior points directly to a stack.
Key Constraints:
1 <= tokens.length <= 10^4→ With up to 10,000 tokens, we need O(n) or O(n log n). A single-pass O(n) stack approach is ideal.- Values in the range
[-200, 200]→ Intermediate results fit in a 32-bit integer (the problem guarantees this), so no overflow handling needed. - Division truncates toward zero → In most languages, integer division already truncates toward zero, but in Python, the
//operator floors toward negative infinity. We needint(a / b)instead. - Input is always valid → We do not need to handle malformed expressions or mismatched operator/operand counts.
Approach 1: Stack-Based Evaluation
Intuition
Think about how RPN works. Consider the expression ["2","1","+","3","*"], which represents (2 + 1) * 3. As we scan from left to right:
- We see
2, then1. These are just numbers, so we remember them. - We see
+. This means "add the last two numbers." That gives us2 + 1 = 3. Now we forget about2and1individually, and just remember3. - We see
3. Another number. We remember it alongside our running result of3. - We see
*. Multiply the last two numbers:3 * 3 = 9. That is our answer.
Notice the pattern: numbers pile up, and operators consume the top two. This is exactly what a stack does. Numbers get pushed, operators pop two values, compute a result, and push it back. At the end, the stack has exactly one element: the final answer.
The only subtlety is operand order. When we pop two values for subtraction or division, the first popped value is the right operand and the second popped value is the left operand. If the expression is 5 3 -, we want 5 - 3 = 2, not 3 - 5 = -2. Since 3 was pushed last, it gets popped first, so we need: secondPopped - firstPopped.
RPN was designed specifically for stack-based evaluation. Each operator consumes exactly two operands and produces exactly one result. This means the stack grows when we see numbers and shrinks (by one) when we see operators. For a valid RPN expression with k numbers and k-1 operators, the stack will always have exactly one element at the end.
The reason the operand order matters is that subtraction and division are not commutative. In ["5","3","-"], we pushed 5 first, then 3. When we pop, 3 comes out first (it is b), and 5 comes out second (it is a). We want a - b = 5 - 3 = 2, not b - a = 3 - 5 = -2.
Algorithm
- Initialize an empty stack.
- Iterate through each token in the input array.
- If the token is an operator (
+,-,*,/), pop the top two elements from the stack. Call themb(first pop, right operand) anda(second pop, left operand). - Apply the operator: compute
a op b. - Push the result back onto the stack.
- If the token is a number, parse it and push it onto the stack.
- After processing all tokens, the stack contains exactly one element. Return it.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through all n tokens exactly once. Each token involves at most one push and one pop (both O(1) for a stack), plus possibly a constant-time arithmetic operation.
- Space Complexity: O(n). In the worst case, the stack holds about n/2 elements (when all numbers come first, followed by all operators). Since the number of operands is at most (n+1)/2, the space is O(n).
The stack approach is already optimal at O(n) time. But what if we want to avoid the overhead of a stack class? We can simulate the stack with a plain array and a pointer.
Approach 2: Array-Based In-Place Evaluation
Intuition
The stack approach works great, but we can be a bit cleverer about memory. Instead of creating a separate stack, we can use a pointer into an integer array. Since each operator consumes two operands and produces one, the "active" portion of our working space only ever grows by one (for a number) or shrinks by one (for an operator). We can simulate the stack using an array and a top-of-stack index.
This is functionally identical to Approach 1. The difference is purely mechanical: we manage the stack ourselves with an array and an index pointer instead of relying on a stack class. This can be marginally faster in practice because raw array access avoids method call overhead.
Algorithm
- Create an integer array of size
(tokens.length + 1) / 2(the maximum number of operands). - Maintain a
toppointer starting at -1. - For each token:
- If it is an operator, compute
arr[top-1] op arr[top], store the result inarr[top-1], and decrementtop. - If it is a number, increment
topand store the parsed value atarr[top]. - Return
arr[0](the single remaining element).
Example Walkthrough
Code
- Time Complexity: O(n). Same as Approach 1. One pass through all tokens, O(1) work per token.
- Space Complexity: O(n). We allocate an array of size (n+1)/2. This is the same O(n) as the stack approach, but with a tighter constant since we allocate only the space we might need.