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!

Bharati Subramanian