Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation.

Evaluate the expression. Return an integer that represents the value of the expression.

Note that:

• The valid operators are '+', '-', '*', and '/'.
• Each operand may be an integer or another expression.
• The division between two integers always truncates toward zero.
• There will not be any division by zero.
• The input represents a valid arithmetic expression in a reverse polish notation.
• The answer and all the intermediate calculations can be represented in a 32-bit integer.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• 1 <= tokens.length <= 104
• tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Approach: Stack (Optimal Solution)

Algorithm

1. Create a stack to store intermediate results
2. Iterate through each token
3. If the token is a number, push it onto the stack
4. If the token is an operator, pop the two top operands, apply the operator, and push the result
5. After processing all tokens, the stack contains the final answer

Key Insight

Reverse Polish Notation places the operator after its operands, so the operands are always the top two elements of the stack when an operator is encountered. The stack naturally handles the nested expression structure.

Time & Space Complexity

• Time Complexity: O(n) - each token is processed once
• Space Complexity: O(n) - stack stores intermediate operands

Java Implementation

import java.util.Stack;

public class EvaluateReversePolishNotation {

    /**
     * Evaluate an arithmetic expression in Reverse Polish Notation.
     * @param tokens Array of strings representing the expression
     * @return Integer value of the expression
     */
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            switch (token) {
                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;
                }
                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); // truncates toward zero in Java
                    break;
                }
                default:
                    stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        String[] tokens1 = {"2", "1", "+", "3", "*"};
        System.out.println("Input: tokens = [\"2\",\"1\",\"+\",\"3\",\"*\"]");
        System.out.println("Output: " + evalRPN(tokens1)); // Expected: 9

        // Test case 2
        String[] tokens2 = {"4", "13", "5", "/", "+"};
        System.out.println("Input: tokens = [\"4\",\"13\",\"5\",\"/\",\"+\"]");
        System.out.println("Output: " + evalRPN(tokens2)); // Expected: 6

        // Test case 3
        String[] tokens3 = {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"};
        System.out.println("Input: tokens = [\"10\",\"6\",\"9\",\"3\",\"+\",\"-11\",\"*\",\"/\",\"*\",\"17\",\"+\",\"5\",\"+\"]");
        System.out.println("Output: " + evalRPN(tokens3)); // Expected: 22
    }
}

Example Walkthrough

For tokens = ["2","1","+","3","*"]:

1. “2”: push 2 → stack=[2]
2. “1”: push 1 → stack=[2,1]
3. ”+”: pop 1, pop 2, push 2+1=3 → stack=[3]
4. “3”: push 3 → stack=[3,3]
5. ”*”: pop 3, pop 3, push 3×3=9 → stack=[9]

Result = 9.

For tokens = ["4","13","5","/","+"]:

1. “4”: push 4 → stack=[4]
2. “13”: push 13 → stack=[4,13]
3. “5”: push 5 → stack=[4,13,5]
4. ”/”: pop 5, pop 13, push 13/5=2 → stack=[4,2]
5. ”+”: pop 2, pop 4, push 4+2=6 → stack=[6]

Result = 6.

Key Insights

1. Operand Order: For subtraction and division, the second popped value is the left operand and the first popped value is the right operand
2. Truncation Toward Zero: Java’s integer division naturally truncates toward zero, matching the requirement
3. Stack Depth: The stack depth grows with nesting but never exceeds the number of unprocessed operands
4. Single Result: After all tokens are processed, exactly one value remains on the stack

The stack-based approach is the optimal solution for evaluating Reverse Polish Notation, providing linear time complexity.