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 *.

RPN needs no parentheses. The order of operations is determined entirely by the position of operators relative to operands. Each operator applies to the two most recent operands, and that "last in, first out" access pattern maps directly to a stack.

Key Constraints:

Values in the range [-200, 200] and the problem's guarantee that every intermediate result fits in a 32-bit integer mean a plain int works in every language. No overflow handling needed.
Division truncates toward zero. In Java, C++, C#, Go, and Rust, integer division already truncates toward zero. In Python, // floors toward negative infinity, so int(a / b) is required. In JavaScript and TypeScript, / produces a float, so Math.trunc is required.
The input is always a valid expression, so there is no need to handle malformed tokens or mismatched operator and operand counts.

Approach: Stack-Based Evaluation

Intuition

Consider the expression ["2","1","+","3","*"], which represents (2 + 1) * 3. As we scan from left to right:

We see 2, then 1. These are numbers, so we hold on to them.
We see +. This adds the last two numbers, giving 2 + 1 = 3. We replace 2 and 1 with that single result, 3.
We see 3, another number, which we hold alongside the running result 3.
We see *. We multiply the last two numbers, 3 * 3 = 9, which is the answer.

Numbers accumulate, and each operator consumes the top two. A stack matches this directly: numbers get pushed, operators pop two values, compute a result, and push it back. After processing every token, the stack holds exactly one element, the final answer.

The one detail to get right 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. For 5 3 -, we want 5 - 3 = 2, not 3 - 5 = -2. Since 3 was pushed last, it pops first, so the computation is secondPopped - firstPopped.

Correctness

Each operator consumes two operands and produces one result, so the stack grows by one for every number and shrinks by one for every operator. A valid RPN expression with k numbers has exactly k-1 operators, so the stack ends with one element. Every operator also finds at least two values waiting, because validity guarantees each operand was produced before the operator that uses it.

Operand order matters because subtraction and division are not commutative. In ["5","3","-"], we push 5 then 3, so 3 pops first as b and 5 pops second as a. The computation a - b = 5 - 3 = 2 is correct, while b - a = 3 - 5 = -2 is not.

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 them b (first pop, right operand) and a (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

tokens

1Start: push numbers onto the stack as we scan left to right

-11

stack

1Stack is empty, ready to process tokens

1/7

Code

Complexity Analysis

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).

Evaluate Reverse Polish Notation