Evaluate Reverse Polish Notation

NeetCode: Evaluate Reverse Polish Notation · LeetCode: 150. Evaluate Reverse Polish Notation · Difficulty: Medium

Evaluate an arithmetic expression in Reverse Polish Notation (operator after its operands). Valid operators are + - * /. Division truncates toward zero. The expression is always valid.

Example

Text

Input:  tokens = ["1", "2", "+", "3", "*", "4", "-"]    Output: 5    ((1 + 2) * 3 - 4)

Brute force: rewrite the list until one value remains

Find the first operator, replace it and the two tokens before it with their result, and repeat until one token remains. list.subList(i - 2, i + 1).clear() removes the three tokens, and Integer.parseInt converts a token to an int. The input is a String[], so a negative number such as "-7" is one token and "-" alone is the operator.

Java

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

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

    public int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(List.of(tokens));
        while (list.size() > 1) {
            int i = 0;
            while (!isOperator(list.get(i))) {
                i++;
            }
            int a = Integer.parseInt(list.get(i - 2));
            int b = Integer.parseInt(list.get(i - 1));
            int value;
            switch (list.get(i)) {
                case "+": value = a + b; break;
                case "-": value = a - b; break;
                case "*": value = a * b; break;
                default:  value = a / b;
            }
            list.subList(i - 2, i + 1).clear();           // remove the three tokens
            list.add(i - 2, String.valueOf(value));       // insert the result
        }
        return Integer.parseInt(list.get(0));
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.evalRPN(new String[]{"1", "2", "+", "3", "*", "4", "-"}));
        System.out.println(sol.evalRPN(new String[]{"4", "13", "5", "/", "+"}));
    }
}

Output

5
6

Time: O(n²), because each rewrite shifts the tail of the list. Space: O(n).

Optimal: one stack

Push numbers. When an operator arrives, pop the right operand and then the left operand (order matters for - and /), apply the operator, and push the result. The one value left at the end is the answer. Java's integer / truncates toward zero, so -7 / 2 is -3, as the problem requires. + and * are commutative, so their operands can be popped in either order. All arithmetic is int arithmetic: a result outside the int range wraps silently, and long or Math.multiplyExact is needed if the inputs can produce one. ArrayDeque is used as the stack through push and pop.

Java

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

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()); break;
                case "*": stack.push(stack.pop() * stack.pop()); break;
                case "-": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a - b);
                    break;
                }
                case "/": {
                    int b = stack.pop();
                    int a = stack.pop();
                    stack.push(a / b);
                    break;
                }
                default: stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.evalRPN(new String[]{"1", "2", "+", "3", "*", "4", "-"}));
        System.out.println(sol.evalRPN(new String[]{"4", "13", "5", "/", "+"}));
        System.out.println(sol.evalRPN(new String[]{"-7", "2", "/"}));
    }
}

Output

5
6
-3

Time: O(n). Space: O(n).