Evaluate Reverse Polish Notation medium

Problem Statement

Evaluate the value of an arithmetic expression in Reverse Polish Notation (RPN).

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero. The given RPN expression is always valid. That means the expression would always evaluate to a result and there won't be any divide by zero operation.

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)) = 4 + 2 = 6

Steps

1. Use a Stack: We'll use a stack to store operands.
2. Iterate through Tokens: Traverse the input tokens array.
3. Operand: If a token is an operand (number), push it onto the stack.
4. Operator: If a token is an operator (+, -, *, /), pop the top two operands from the stack.
5. Perform Operation: Perform the operation using the two popped operands (order matters!).
6. Push Result: Push the result of the operation back onto the stack.
7. Final Result: After processing all tokens, the final result will be at the top of the stack.

Explanation

The algorithm leverages the properties of Reverse Polish Notation. In RPN, operators follow their operands. By using a stack, we can easily keep track of operands until their corresponding operator is encountered. The stack's LIFO (Last-In, First-Out) nature naturally handles the order of operations implied by the RPN.

For example, in ["2","1","+","3","*"], the stack operations would be:

1. Push "2" -> Stack: [2]
2. Push "1" -> Stack: [2, 1]
3. "+" -> Pop 1 and 2, compute 2+1=3, push 3 -> Stack: [3]
4. Push "3" -> Stack: [3, 3]
5. "" -> Pop 3 and 3, compute 33=9, push 9 -> Stack: [9]

The final result, 9, is at the top of the stack.

Code (Java)

import java.util.Stack;

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (isOperator(token)) {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int result = performOperation(operand1, operand2, token);
                stack.push(result);
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

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

    private int performOperation(int operand1, int operand2, String operator) {
        switch (operator) {
            case "+":
                return operand1 + operand2;
            case "-":
                return operand1 - operand2;
            case "*":
                return operand1 * operand2;
            case "/":
                return operand1 / operand2; // Integer division
            default:
                throw new IllegalArgumentException("Invalid operator: " + operator);
        }
    }
}

Complexity

• Time Complexity: O(n), where n is the number of tokens. We iterate through the tokens once.
• Space Complexity: O(n) in the worst case, as the stack could hold all the operands if the expression is heavily nested. In the average case, it's considerably less than O(n).