NeetCode 150: Evaluate Reverse Polish Notation

Table of contents

The Problem

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.

The Approach

The goal is to use a Stack to handle the order the operators are applied on the elements in tokens. For Reverse Polish Notation, the immediate previous two elements are applied with the operand. As such, the Stack maintains this priority (LIFO). The final element at the end would be the value of the expression.

My Solution

class Solution {
    private String validOperands = "+-*/";

    public int evalRPN(String[] tokens) {
        Stack<Integer> numbersTracker = new Stack<Integer>();
        
        // For Reverse Polish Notation, the immediate previous two 
        // elements are applied with the operand. As such, the 
        // stack maintains the priority (LIFO).
        for (int i = 0; i < tokens.length; i++) {
            String currentElement = tokens[i];

             // Checks if currentElement is not an operand & pushes it
            // to numbersTracker.
            if (!(validOperands.contains(currentElement))) {
                numbersTracker.push(Integer.parseInt(currentElement));
            } else {
                int num1 = numbersTracker.pop();
                int num2 = numbersTracker.pop();

                // Pops the two top-most elements & applies the operand,
                // this result is then pushed back to numbersTracker.
                switch (currentElement) {
                    case ("+"):
                        numbersTracker.push(num2 + num1);
                        break;
                    
                    case ("-"):
                        numbersTracker.push(num2 - num1);                       
                        break;      

                    case ("*"):
                        numbersTracker.push(num2 * num1);                     
                        break;
                    
                    case ("/"):
                        numbersTracker.push(num2 / num1);
                        break;
                }
            }
        }
        return numbersTracker.pop();
    }
}

Firstly, we initialize numbersTracker.

We then loop over all the elements in tokens. If it is a number, we add it to the stack. Else, we pop the two top-most elements in the Stack & apply the respective operand. The outcome of this is then pushed back to numbersTracker.

At the end of the loop, the element remaining in numbersTracker is the value of the expression.