Java: Evaluate Reverse Polish Notation

Thought Process

To evaluate Reverse Polish Notation (RPN), we use a stack to keep track of operands. When we encounter an operator, we pop the top two elements from the stack, perform the operation, and push the result back onto the stack. For numbers, we simply push them onto the stack. The key is to process tokens sequentially and use the stack to handle operands and operations efficiently. At the end, the final result is the only element left on the stack. 

class Solution {
    public int evalRPN(String[] tokens) {

        // 1. If string is a number then push into stack
        // 2. If string is a operator, take 2 elements from stack. Apply the operation & put it on the stack
        // 3. At the end, return the top of the stack (which will be an answer)
        Stack<Integer> st = new Stack<>();
        for(int i=0;i<tokens.length;i++){

            String str = tokens[i];
            boolean isOperator = false;
            if(str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/"))
                isOperator = true;
            
            if(!isOperator){
                int x = Integer.parseInt(str);
                st.push(x);
            }
            else{
                int a = st.pop();
                int b = st.pop();
                
                if(str.equals("+"))
                    st.push(b+a);
                else if(str.equals("-"))
                    st.push(b-a);
                else if(str.equals("*"))
                    st.push(b*a);
                else if(str.equals("/"))
                    st.push(b/a);
            }
        }
        return st.peek();
    }
}

Code Complexity

Time Complexity: O(n)

The algorithm processes each token once, where 'n' is the number of tokens.

Space Complexity: O(n)

The stack can store up to 'n' elements in the worst case.

Code copied!