Evaluate Reverse Polish Notation

mediumStack28 stepsJava · Python · C++

Evaluate an expression written in postfix, like 2 1 + 3 *. Push numbers; on an operator, pop the right operand, then the left one, apply the operator, and push the result. The last value on the stack is the answer.

▶ Watch the animated trace

Traced input: tokens = ["4", "13", "5", "/", "+"] → 6. Original problem: neetcode.io/problems/evaluate-reverse-polish-notation

Complexity

BestO(n)

AverageO(n)

WorstO(n)

SpaceO(n)

Each token is pushed or popped a constant number of times.

Key idea

Postfix needs no parentheses: an operator always applies to the two most recent values.
Pop b first, then a, and compute a op b; order matters for - and /.
Division truncates toward zero, which is exactly what Java's / does.

Common mistakes

Swapping operands: 4 13 5 / + needs 13 / 5, not 5 / 13.
Checking for operators with token.charAt(0) == '-' breaks on negative numbers like "-11".
Comparing strings with == instead of .equals.

Solution

Java

int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < tokens.length; i++) {
        String t = tokens[i];
        if (t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/")) {
            int b = stack.pop(), a = stack.pop();
            int r = switch (t) {
                case "+" -> a + b;
                case "-" -> a - b;
                case "*" -> a * b;
                default -> a / b;
            };
            stack.push(r);
        } else {
            stack.push(Integer.parseInt(t));
        }
    }
    return stack.pop();
}

Python

def evalRPN(tokens: List[str]) -> int:
    stack = []
    for t in tokens:
        if t in ("+", "-", "*", "/"):
            b, a = stack.pop(), stack.pop()
            if t == "+": r = a + b
            elif t == "-": r = a - b
            elif t == "*": r = a * b
            else: r = int(a / b)  # truncate toward zero
            stack.append(r)
        else:
            stack.append(int(t))
    return stack.pop()

C++

int evalRPN(vector<string>& tokens) {
    stack<int> st;
    for (const string& t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();
            int r;
            if (t == "+") r = a + b;
            else if (t == "-") r = a - b;
            else if (t == "*") r = a * b;
            else r = a / b;
            st.push(r);
        } else {
            st.push(stoi(t));
        }
    }
    return st.top();
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Single number Just pushed and returned.	`tokens = ["42"]`	`42`
Negative numbers "-3" is a number, not the minus operator.	`tokens = ["-3", "4", "*"]`	`-12`
Division truncates toward zero -3.5 truncates to -3, not -4.	`tokens = ["-7", "2", "/"]`	`-3`
Long expression The LeetCode example.	`tokens = ["10", "6", "9", "3", "+", "-11", "", "/", "", "17", "+", "5", "+"]`	`22`