Evaluate Reverse Polish Notation

MediumStack · Expression Evaluation🧩 Stack LeetCode #150 ↗Updated Oct 30, 2026

Problem

An arithmetic expression is given as a token array tokens in postfix (Reverse Polish) order: every operator comes after its two operands. Tokens are integers or one of + - * /. Return the value of the expression; division truncates toward zero, the input is always valid, there is no division by zero, and every value fits in a 32-bit int.

Input["2","1","+","3","*"]Output9 ((2 + 1) * 3)

Input["4","13","5","/","+"]Output6 (4 + 13 / 5)

Input["7","-2","/"]Output-3

1 ≤ tokens.length ≤ 10⁴ · each token is an operator or an integer in [-200, 200] · expression is valid

Try it yourself

Java

class Solution {
    public int evalRPN(String[] tokens) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

In postfix, an operator always applies to the two most recent unconsumed values — exactly what a stack's top two elements are. Push numbers, and on an operator pop two, combine, push the result.

PatternStack

Instinct Things resolve in reverse order of arrival (brackets, adjacent pairs, nested expressions) - push now, pop when its partner shows up.

Memory hack Last in, first out - like a pile of plates, you only ever touch the one on top; every closer pops its opener.

Open the Stack guide →

Approaches

Brute ForceRepeatedly Reduce the Leftmost Operator

Time O(n²)Space O(n)

Copy the tokens into a list. The leftmost operator is always preceded by its two operands, so replace that triple a b op by its value and repeat until one token remains. Each step rescans and shifts the list, giving quadratic time.

Java

public int evalRPN(String[] tokens) {
    List<String> list = new ArrayList<>(Arrays.asList(tokens));
    while (list.size() > 1) {
        int i = 0;
        while (!isOp(list.get(i))) i++; // leftmost operator
        int a = Integer.parseInt(list.get(i - 2));
        int b = Integer.parseInt(list.get(i - 1));
        list.set(i - 2, String.valueOf(apply(a, b, list.get(i).charAt(0))));
        list.remove(i);     // operator
        list.remove(i - 1); // right operand
    }
    return Integer.parseInt(list.get(0));
}

private boolean isOp(String t) {
    return t.length() == 1 && "+-*/".indexOf(t.charAt(0)) >= 0;
}

private int apply(int a, int b, char op) {
    switch (op) {
        case '+': return a + b;
        case '-': return a - b;
        case '*': return a * b;
        default:  return a / b;
    }
}

Correct and intuitive, but rescanning after every reduction is O(n²).

BetterRecursion from the Right End

Time O(n)Space O(n)

Read postfix backwards and it becomes prefix: the last token is the root. If it is an operator, recursively evaluate its right operand (the tokens just before it) and then its left operand. A shared index moves leftwards, so each token is visited once.

Java

private int idx;

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

private int eval(String[] tokens) {
    String t = tokens[idx--];
    if (t.length() == 1 && "+-*/".indexOf(t.charAt(0)) >= 0) {
        int right = eval(tokens); // right operand sits closer to the operator
        int left = eval(tokens);
        switch (t.charAt(0)) {
            case '+': return left + right;
            case '-': return left - right;
            case '*': return left * right;
            default:  return left / right;
        }
    }
    return Integer.parseInt(t);
}

Linear, but recursion depth can reach n — risky for deep, lopsided trees.

OptimalOperand Stack (Array-backed)

Time O(n)Space O(n)

Scan left to right with an int[] used as a stack. Numbers are pushed; an operator pops b (top) then a, pushes a op b. A valid expression leaves exactly one value. Iterative, so no recursion-depth risk, and no boxing overhead.

Java

public int evalRPN(String[] tokens) {
    int[] stack = new int[tokens.length];
    int top = 0; // number of values on the stack
    for (String t : tokens) {
        if (t.length() == 1 && "+-*/".indexOf(t.charAt(0)) >= 0) {
            int b = stack[--top], a = stack[--top]; // order matters for - and /
            switch (t.charAt(0)) {
                case '+': stack[top++] = a + b; break;
                case '-': stack[top++] = a - b; break;
                case '*': stack[top++] = a * b; break;
                default:  stack[top++] = a / b;
            }
        } else {
            stack[top++] = Integer.parseInt(t);
        }
    }
    return stack[0];
}

Dry run["4","13","5","/","+"] (arr = stack)

t top changed

'4'
4
t
·

·

push 4
'13'
4

13
t
·

push 13
'5'
4

13

5
t
push 5
'/'
4

2
t
·

13/5 = 2
'+'
6
t
·

·

4+2 = 6 ✔

One pass, iterative and allocation-light — the textbook solution.

Pro tip

Detect operators by length 1 plus symbol — "-3" starts with - but is a number.

At a glance

Level	Approach	Time	Space
Brute Force	Repeatedly Reduce the Leftmost Operator	`O(n²)`	`O(n)`
Better	Recursion from the Right End	`O(n)`	`O(n)`
Optimal	Operand Stack (Array-backed)	`O(n)`	`O(n)`

Common pitfalls

Popping operands in the wrong order — a - b and a / b flip sign/value.
Treating negative numbers like "-11" as the minus operator.
Using floor division (e.g. Math.floorDiv) — the problem wants truncation.

Interview tips

Say why a stack fits: each operator consumes the two latest values.
Mention the array-as-stack: capacity n is enough and avoids boxing.
Walk through a subtraction/division example to prove operand order.

Pattern

Operand stack → evaluate postfix expressions or any “combine the two most recent items” process.

My notes saved in this browser