Evaluate REverSe Polish Notation

73.Evaluate Reverse Polish Notation

Stack

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.

Example:

Input:

["2", "1", "+", "3", "*"]

→

Output:

9

Explanation: ((2 + 1) * 3) = 9.

Algorithm:

1. Initialize a stack to store operands during evaluation.
2. Iterate through the tokens in the input array.
3. For each token:
   • If it is an operator (+, -, *, /), pop two numbers from the stack, perform the operation, and push the result back.
   • If it is a number, parse it and push it onto the stack.
4. At the end, the top of the stack is the result.

public int evalRPN(String[] tokens) {
    // Stack to hold operands
    Stack<Integer> s = new Stack();
        
    // Iterate through the tokens
    for (String token : tokens) {
        // Handle addition
        if (token.equals("+")) 
            s.push(s.pop() + s.pop());
        // Handle multiplication
        else if (token.equals("*")) 
            s.push(s.pop() * s.pop());
        // Handle subtraction
        else if (token.equals("-")) {
            int first = s.pop();
            int second = s.pop();
            s.push(second - first);   
        }
        // Handle division
        else if (token.equals("/")) {
            int first = s.pop();
            int second = s.pop();
            s.push(second / first);
        }
        // Handle numbers
        else {
            s.push(Integer.parseInt(token));
        }
    }
        
    // The result is at the top of the stack
    return s.peek();
}

Complexity:

Time: O(n) | Space: O(n)