Difficulty: MediumStack

Evaluate Reverse Polish Notation

Problem in Plain English

Given an array of tokens forming a valid postfix arithmetic expression with addition, subtraction, multiplication and truncating division, evaluate it and return the resulting integer.

Problem Statement

You are given an array of strings tokens that represents an arithmetic expression in Reverse Polish Notation. Evaluate the expression and return an integer that represents its value.

In postfix form every operator follows its two operands, so ["2","1","+","3","*"] means ((2 + 1) * 3) = 9. The valid operators are +, -, * and /, and division between two integers always truncates toward zero.

Constraints

1 <= tokens.length <= 10^4
tokens[i] is either an operator +, -, * or /, or an integer in the range [-200, 200].
The input is a valid Reverse Polish Notation expression; every operator has two available operands and evaluation ends with one value.
Division by zero never occurs.
The answer and every intermediate calculation fit a signed 32-bit integer.

Examples

Example 1

Input: tokens = ["2","1","+","3","*"]
Output: 9

Basic combination: read 2 and 1, then + replaces them with 3. The next 3 and * compute 3 * 3 = 9, so the expression is ((2 + 1) * 3).

Example 2

Input: tokens = ["4","13","5","/","+"]
Output: 6

The division is a complete right operand: 13 / 5 truncates to 2 before the earlier 4 is added. Thus 4 + 2 = 6; adding 4 and 13 first would change the expression.

Example 3

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22

Nested negative division: 9 + 3 = 12, 12 * -11 = -132, and 6 / -132 truncates to 0. Then 10 * 0 = 0, 0 + 17 = 17, and 17 + 5 = 22. Flooring the negative quotient to -1 would give a wrong answer.

Example 4

Input: tokens = ["18"]
Output: 18

Edge case: one number already forms a valid expression. There is nothing to reduce; the stack contains only 18 and that is returned.

Example 5

Input: tokens = ["-11","2","/"]
Output: -5

Tricky sign case: the first popped value 2 is the divisor and the second -11 is the dividend. -11 / 2 = -5.5 truncates toward zero to -5, whereas Python floor division would produce -6.

Example 6

Input: tokens = ["2","5","-"]
Output: -3

Operand order matters: 2 is the left operand and 5 is the right operand. Evaluate 2 - 5 = -3, even though a stack pops 5 before 2.

Intuition

Postfix notation places an operator after both of its operand expressions, so parentheses are encoded by token order. Think of a stack as a pile of completed values waiting to be used: the newest value is the right operand, and the value beneath it is the left operand. In Example 1, 2 and 1 become 3 at +; that result waits beside the next 3 until * combines them into 9. Repeatedly rewriting the expression works too, but rescanning and moving tokens repeats work.

Approaches

Scan and Reduce

Solution Details

Reveal Scan and Reduce: intuition, complexity, and code

Intuition

Collapse the first operator and its two preceding numbers into one result, then repeat. Before the first operator there are only numbers, so its operands are ready to evaluate. In Example 1, replacing 2 1 + with 3 leaves 3 3 *, which reduces to 9. This direct simulation is useful as a baseline, but each restart and list replacement may revisit or move many tokens.

Step-by-Step Logic

Copy the tokens into a mutable expression list so the input stays unchanged. While more than one token remains, start a scan at index 0. Example 1 starts as [2, 1, +, 3, *].
Scan until the first exact operator token. For Example 1, index 0 is 2 and index 1 is 1; + at index 2 ends the scan. Negative tokens such as -11 are numbers.
Read the number two positions before the operator as a, and the immediately preceding number as b. Evaluate a operator b with truncation toward zero for division; here a = 2, b = 1, giving 3.
Replace those three tokens with the result and restart the scan. Example 1 becomes [3, 3, *]; scan both 3 tokens, then compute 3 * 3 = 9 and replace them with [9].
When exactly one token remains, parse and return it. Example 1 returns 9; a one-token expression skips the loop.

Why It Works

At the first operator, every preceding token is a number, and postfix order makes the immediately preceding two numbers its left and right operands. Replacing that three-token subexpression with its computed value preserves the value and validity of the whole expression. Each replacement removes two tokens, so repeated value-preserving reductions terminate at one token. That remaining value is the original expression result; a single-number input already satisfies the stopping condition.

Dry Run

Scan and Reduce: variable states at each step
Pass / scan index	Token / expression before	Action and operand order	Expression after
Start	[2, 1, +, 3, *]	copy input, length 5	[2, 1, +, 3, *]
1 / 0	2	number: advance scan	unchanged
1 / 1	1	number: advance scan	unchanged
1 / 2	+	a = 2, b = 1; replace 2 1 + with 3	[3, 3, *]
2 / 0	3	number: advance scan	unchanged
2 / 1	3	number: advance scan	unchanged
2 / 2	*	a = 3, b = 3; replace 3 3 * with 9	[9]
Return	[9]	length 1: parse remaining token	9

Complexity Analysis

Time Complexity

O(n^2)

Space Complexity

O(n)

Let n be the token count. There are (n - 1)/2 reductions, each potentially scanning and shifting or rebuilding O(n) tokens. A valid expression with many numbers followed by operators repeatedly scans long prefixes, giving O(n^2) worst-case time. The copied expression uses O(n) space; Python slicing creates temporary lists of O(n) total size at each reduction, so peak auxiliary space remains O(n). Tokens and intermediate integers have bounded length under the stated constraints.

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3import java.util.Arrays;4
5class Solution {6    public int evalRPN(String[] tokens) {7        List<String> expr = new ArrayList<>(Arrays.asList(tokens));8        while (expr.size() > 1) {9            int op = 0;10            while (!isOperator(expr.get(op))) {11                op++;12            }13            int b = Integer.parseInt(expr.get(op - 1));14            int a = Integer.parseInt(expr.get(op - 2));15            int value = apply(a, b, expr.get(op));16            expr.set(op - 2, String.valueOf(value));17            expr.remove(op - 1);18            expr.remove(op - 1);19        }20        return Integer.parseInt(expr.get(0));21    }22
23    private boolean isOperator(String token) {24        return token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/");25    }26
27    private int apply(int a, int b, String op) {28        if (op.equals("+")) {29            return a + b;30        } else if (op.equals("-")) {31            return a - b;32        } else if (op.equals("*")) {33            return a * b;34        }35        return a / b;36    }37}

Hints

Hint 1

Read the tokens left to right: numbers have nowhere to go yet, but an operator always applies to the two most recent unfinished values.

Hint 2

A stack of numbers models "most recent unfinished" exactly: push numbers, and on an operator pop twice, combine, and push the result.

Hint 3

Order matters for - and /: the first pop is the right operand and the second pop is the left operand.

Edge Cases

A single number such as [18] is already the answer; no operator fires.
Negative division [-11, 2, /] yields -5, while [11, -2, /] also yields -5 and [-11, -2, /] yields 5.
A negative quotient with magnitude below one truncates to zero: [6, -132, /] yields 0.
Noncommutative operators need left-to-right order: [2, 5, -] yields -3 and [2, 5, /] yields 0.
All numbers before all operators maximize stack occupancy; a long left-associated expression keeps the stack small but still requires scanning every token.
Intermediate values may exceed the input token range [-200, 200]; do not clamp them. The guarantee is signed 32-bit representability, not the token range.

Common Mistakes and Interview Tips

Swapping operands after two pops: b is popped first, then a, so evaluate a - b or a / b.
Using Python a // b directly floors negative quotients. Divide abs(a) by abs(b), then negate exactly when their signs differ to implement truncation using integers.
Recognizing an operator by the first character misclassifies -11. Match exactly one of +, -, *, /.
Applying standard infix precedence changes the expression: postfix token order already encodes which operand expressions combine.
Using JavaScript bitwise tricks to truncate silently coerces numbers to signed 32-bit values. Math.trunc expresses the required rule directly.
For Scan and Reduce, removing the operand at op - 1 shifts the operator into that same index; remove that index again, not op.
Interview tip: state the stack invariant and walk 2 5 - and -11 2 / before coding. Explain the valid-input and 32-bit guarantees, then contrast one pass with repeated scanning.

Key Takeaway

When each operation consumes the most recently seen unfinished values, a stack turns nested evaluation into a single left-to-right pass.