23.Evaluate Reverse Polish Notation

MediumStack · 3/7

Problem

You are given an array of strings tokens describing an arithmetic expression in Reverse Polish Notation (postfix): every operator comes after its two operands. Evaluate the expression and return its integer value.

Valid operators are +, -, * and /.
Each operand is an integer (it may be negative).
Division truncates toward zero.
The input is always a valid expression, there is no division by zero, and every intermediate result fits in a 32-bit integer.

Examples

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

Input:  tokens = ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 4 + 2 = 6

Input:  tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: 9 + 3 = 12; 12 * -11 = -132; 6 / -132 = 0 (truncated);
             10 * 0 = 0; 0 + 17 = 17; 17 + 5 = 22

Constraints

1 <= tokens.length <= 10^4
tokens[i] is an operator ("+", "-", "*", "/") or an integer in [-200, 200].

💡 Key Insight

In postfix notation, an operator always applies to the two most recently produced values. A stack holds exactly those: push numbers; on an operator, pop two values, combine them, and push the result back. Mind the order — the first value popped is the right operand.

Brute Force (Repeated Reduction)

TimeO(n²)SpaceO(n)

Intuition

Find the first operator in the list. The two tokens immediately before it are guaranteed to be numbers (otherwise a previous operator would come first). Replace those three tokens with their result and repeat until a single number remains.

Algorithm

Copy tokens into a mutable list.
While the list has more than one element:
- Find the first index i holding an operator.
- Compute list[i-2] op list[i-1].
- Replace positions i-2..i with the result.
Return the single remaining value.

Visualization

[2, 1, +, 3, *]
       ^ first operator → 2 + 1 = 3
[3, 3, *]
       ^ → 3 * 3 = 9
[9] → answer 9

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        while (list.size() > 1) {
            int i = 0;
            while (!isOperator(list.get(i))) {
                i++; // first operator in the list
            }
            int a = Integer.parseInt(list.get(i - 2));
            int b = Integer.parseInt(list.get(i - 1));
            int result = apply(a, b, list.get(i));
            // replace "a b op" with the result
            list.remove(i);
            list.remove(i - 1);
            list.set(i - 2, String.valueOf(result));
        }
        return Integer.parseInt(list.get(0));
    }

    private boolean isOperator(String t) {
        return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/");
    }

    private int apply(int a, int b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            default:  return a / b; // Java truncates toward zero
        }
    }
}

Complexity

Time: O(n²) — up to n / 2 reductions, each scanning and shifting an ArrayList.
Space: O(n) — the mutable copy.

Recursion from the End

TimeO(n)SpaceO(n)

Intuition

Read the expression backwards: the last token is the root of the expression tree. If it is a number, that is the value. If it is an operator, its right operand is the expression that ends just before it, and its left operand is the expression before that. Recursion naturally consumes tokens in that order.

Algorithm

Keep an index pos starting at the last token.
eval(): take tokens[pos--].
- If it is a number, return it.
- Otherwise right = eval(), then left = eval(), return left op right.
Return eval().

Dry Run

tokens = [2, 1, +, 3, *]

eval: '*' → right = eval → 3
            left  = eval: '+' → right = eval → 1
                                left  = eval → 2
                                → 2 + 1 = 3
      → 3 * 3 = 9

Code

java

class Solution {
    private String[] tokens;
    private int pos;

    public int evalRPN(String[] tokens) {
        this.tokens = tokens;
        this.pos = tokens.length - 1;
        return eval();
    }

    private int eval() {
        String t = tokens[pos--];
        if (!(t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/"))) {
            return Integer.parseInt(t); // leaf: a number
        }
        int right = eval(); // right operand ends just before the operator
        int left = eval();
        switch (t) {
            case "+": return left + right;
            case "-": return left - right;
            case "*": return left * right;
            default:  return left / right;
        }
    }
}

Complexity

Time: O(n) — each token is visited exactly once.
Space: O(n) — recursion depth equals the expression tree height (up to ~n / 2 for a skewed expression).

StackOptimal

TimeO(n)SpaceO(n)

Intuition

Process tokens left to right. Numbers wait on a stack until an operator needs them; an operator pops its two operands, computes, and pushes the result, which may itself become an operand later. At the end exactly one value — the answer — remains.

Algorithm

Create an empty stack.
For each token:
- If it is an operator: b = pop(), a = pop(), push a op b.
- Else push Integer.parseInt(token).
Return pop().

Dry Run

flowchart LR
    A["'4'<br/>stack [4]"] --> B["'13'<br/>stack [4, 13]"]
    B --> C["'5'<br/>stack [4, 13, 5]"]
    C --> D["'/': b=5, a=13<br/>13 / 5 = 2<br/>stack [4, 2]"]
    D --> E["'+': b=2, a=4<br/>4 + 2 = 6<br/>stack [6]"]
    E --> F["return 6"]

Code

java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+" -> stack.push(stack.pop() + stack.pop());
                case "*" -> stack.push(stack.pop() * stack.pop());
                case "-" -> {
                    int b = stack.pop(); // right operand is on top
                    int a = stack.pop();
                    stack.push(a - b);
                }
                case "/" -> {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a / b); // truncates toward zero
                }
                default -> stack.push(Integer.parseInt(t));
            }
        }
        return stack.pop();
    }
}

Complexity

Time: O(n) — each token is pushed/popped a constant number of times.
Space: O(n) — at most about n / 2 + 1 numbers wait on the stack.

Complexity Comparison

Approach	Time	Space
Brute Force (repeated reduction)	O(n²)	O(n)
Recursion from the end	O(n)	O(n)
Stack	O(n)	O(n)

Common Pitfalls

Popping operands in the wrong order for - and /: the first pop is the right operand (a - b, not b - a).
Detecting operators with t.charAt(0) == '-' — negative numbers like "-11" also start with '-'; compare the whole string (or check length 1).
Using Math.floorDiv — the problem wants truncation toward zero, which is what plain / does in Java (-7 / 2 == -3).
Comparing strings with == instead of equals (the switch on String uses equals under the hood).