algoadvance

Leetcode 150. Evaluate Reverse Polish Notation

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:

Example 1:

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

Example 2:

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

Example 3:

Input: ["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

Clarifying Questions

  1. Input Type: Will the input be provided as a list of strings?
    • Yes, the input will be a list of strings where each string is either an operator or an operand.
  2. Operators: Are the only operators present +, -, *, and /?
    • Yes, those are the only operators.
  3. Operands: Are all operands integers?
    • Yes, all operands are integers.
  4. Edge Cases: Are there any edge cases we should be aware of, such as extremely large or small numbers?
    • For the purposes of this problem, we can assume the operands will fit within the bounds of standard integer operations in Java.

Strategy

  1. Stack Data Structure: Use a stack to keep track of operands.
  2. Traversal: Traverse through each element in the list.
    • If the element is an operand, push it onto the stack.
    • If the element is an operator, pop the required number of operands from the stack, apply the operation, and push the result back onto the stack.
  3. Result: The final result will be the only element left in the stack.

Code

import java.util.Stack;

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

    // Example Usage
    public static void main(String[] args) {
        Solution solution = new Solution();
        String[] tokens1 = {"2", "1", "+", "3", "*"};
        System.out.println(solution.evalRPN(tokens1)); // Output: 9

        String[] tokens2 = {"4", "13", "5", "/", "+"};
        System.out.println(solution.evalRPN(tokens2)); // Output: 6

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

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of tokens in the input list. Each token is processed exactly once. The stack operations (push and pop) are O(1), so the overall complexity is linear in terms of the number of tokens.

Space Complexity

The space complexity is also O(n) due to the space used by the stack to store the operands.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI