150. Evaluate Reverse Polish Notation

Hello, reader 👋🏽 ! Welcome to day 77 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 150. Evaluate Reverse Polish Notation.

🤔 Problem Statement

• Evaluate the value of an arithmetic expression in Reverse Polish Notation.

  Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

• Note that division between two integers should truncate toward zero.

  It is guaranteed that the given RPN expression is always valid.

  • That means the expression would always evaluate to a result, and there will not be any division by zero operation.

• E.g.:

  • tokens = ["2","1","+","3","*"] => 9

  • ["4","13","5","/","+"] => 6

  • tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] => 22

💬 Thought Process - Using Stack

• Evaluating expressions in reverse Polish notation is a classic use case of stacks.

• For every input token in the array, it could either be *, /, +, - or any numbers from 0 to 9.

• Since these are binary expressions, we require at least two numbers to process.

• Hence every token that is a number, we will parse it to Integer and add it to a stack.

• Every time the token is an operator, we will pop out the top two numbers are perform secondPopped operator firstPopped. Then we will add this result back to the stack.

• Since it's given that all operations are valid, we can discard cases where there are 0 or 1 number in the stack or cases like division by zero.

👩🏽‍💻 Solution - Using Two Stacks

• Below is the code for the approach for solving this problem using a stack.

class Solution {
    public int evalRPN(String[] tokens) {
        int result;
        Stack<Integer> stack = new Stack();

        for(String token: tokens) {
            if(token.equals("*") || token.equals("+") || 
               token.equals("-") || token.equals("/")) {
                int first = stack.pop();
                int second = stack.pop();

                if(token.equals("*")) {
                    stack.push(first * second);
                }
                else if(token.equals("+")) {
                    stack.push(first + second);
                }
                else if(token.equals("/")) {
                    stack.push(second / first);
                }
                else {
                    stack.push(second - first);
                }
            }
            else {
                stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }
}

Time Complexity: O(n)
Space Complexity: O(n)

• You can find the link to the GitHub repo for this question here: 150. Evaluate Reverse Polish Notation.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!