Evaluate Reverse Polish Notation

Medium Problem 36 of 151 Java and Python

Problem

You are given an array of strings tokens that is an arithmetic expression in Reverse Polish Notation, where each operator comes after its two operands. Evaluate it and return the integer result.

Valid operators are +, -, * and /. Division between two integers truncates toward zero. The expression is always valid and there is no division by zero.

Example 1

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

Example 2

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

Constraints

1 ≤ tokens.length ≤ 10⁴
Each token is an operator or an integer in [-200, 200].

Explanation

Each operator applies to the two most recent values that have not been used yet, so keep values on a stack.

When an operator arrives, pop the right operand first, then the left one, compute, and push the result.

Approach 1 · Naive

Reduce the list in place

Time O(n²)
Space O(n)

Find the first operator, replace it and its two preceding numbers with the result, and repeat until one number is left.

Scan the list for the first operator at index i.
Replace tokens[i - 2 .. i] with the computed value.
Repeat until one token remains.

Java

import java.util.*;

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        while (list.size() > 1) {
            int i = 0;
            while (!"+-*/".contains(list.get(i)) || list.get(i).length() != 1) {
                i++;
            }
            int a = Integer.parseInt(list.get(i - 2));
            int b = Integer.parseInt(list.get(i - 1));
            int value = switch (list.get(i)) {
                case "+" -> a + b;
                case "-" -> a - b;
                case "*" -> a * b;
                default -> a / b;
            };
            list.subList(i - 2, i + 1).clear();
            list.add(i - 2, String.valueOf(value));
        }
        return Integer.parseInt(list.get(0));
    }
}

Python

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        tokens = list(tokens)
        while len(tokens) > 1:
            i = next(i for i, t in enumerate(tokens) if t in "+-*/" and len(t) == 1)
            a, b = int(tokens[i - 2]), int(tokens[i - 1])
            op = tokens[i]
            if op == "+":
                value = a + b
            elif op == "-":
                value = a - b
            elif op == "*":
                value = a * b
            else:
                value = int(a / b)
            tokens[i - 2:i + 1] = [str(value)]
        return int(tokens[0])

Approach 2 · Optimal

Operand stack

Time O(n)
Space O(n)

Push numbers; on an operator, pop two numbers, apply it, and push the result.

For each token: if it is a number, push it.
Otherwise pop b, then a, push a op b.
The single value left on the stack is the answer.

Java

import java.util.*;

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            switch (token) {
                case "+" -> stack.push(stack.pop() + stack.pop());
                case "*" -> stack.push(stack.pop() * stack.pop());
                case "-" -> {
                    int b = stack.pop();
                    stack.push(stack.pop() - b);
                }
                case "/" -> {
                    int b = stack.pop();
                    stack.push(stack.pop() / b);
                }
                default -> stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

Python

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

Complexity compared

Approach	Time	Space
Naive Reduce the list in place	O(n²)	O(n)
Optimal Operand stack	O(n)	O(n)

Key takeaways

Pop order matters for - and /: the first pop is the right operand.
In Python, // floors (-7 // 2 = -4); use int(a / b) to truncate toward zero like Java.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem