150. Evaluate Reverse Polish Notation

Intuition

Reverse Polish Notation (RPN) is a mathematical notation in which every operator follows all of its operands. It eliminates the need for parentheses to define evaluation order. We use a stack to evaluate the expression since it allows us to process operands and operators in the correct sequence.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N)$

Code

public int evalRPN(String[] tokens) {
    Stack<Integer> operandStack = new Stack<>();

    for (int index = 0; index < tokens.length; ++index) {
        String currentToken = tokens[index];

        // If the token is an operator, pop two operands and apply the operation
        if (currentToken.equals("/")) {
            int secondOperand = operandStack.pop();
            int firstOperand = operandStack.pop();
            operandStack.push(firstOperand / secondOperand);
        } else if (currentToken.equals("*")) {
            int secondOperand = operandStack.pop();
            int firstOperand = operandStack.pop();
            operandStack.push(firstOperand * secondOperand);
        } else if (currentToken.equals("+")) {
            int secondOperand = operandStack.pop();
            int firstOperand = operandStack.pop();
            operandStack.push(firstOperand + secondOperand);
        } else if (currentToken.equals("-")) {
            int secondOperand = operandStack.pop();
            int firstOperand = operandStack.pop();
            operandStack.push(firstOperand - secondOperand);
        } else {
            // Token is a number; parse and push onto the stack
            operandStack.push(Integer.parseInt(currentToken));
        }
    }

    // The final result will be the only value left on the stack
    return operandStack.peek();
}