Leetcode 150: Evaluate Reverse Polish Notation

Leetcode 150: Evaluate Reverse Polish Notation

Edit Evaluate Reverse Polish Notation on GitHub

First you should know the definition of Reverse Polish Notation, it is quite interesting, postfix, stack-based, 😀

The definition from WIKI is as follows:

Reverse Polish notation (RPN) is a mathematical notation in which every operator follows all of its operands, in contrast to Polish notation, which puts the operator in the prefix position. It is also known as postfix notation and is parenthesis-free as long as operator arities are fixed.

Here are some examples:

["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Now even if I didn’t mention RPN is stack-based, you must have thought about it the moment you saw the example:

1. If receive number, push into stack.

2. If receive operator, pop two number in stack and push the calculated result back.

3. The result will be the last element inside the stack, just pop it after no input.

Here comes the easiest part :

public class Solution {
    public int evalRPN(String[] tokens) {
        int returnValue = 0;
        String operators = "+-*/";
        Stack<String> stack = new Stack<String>();
        
        for(String t:tokens){
            if(!operators.contains(t)){
                stack.push(t);
            }else{
                int a=Integer.valueOf(stack.pop());
                int b=Integer.valueOf(stack.pop());
                int index = operators.indexOf(t);
                switch(index){
                    case 0:
                        stack.push(String.valueOf(a+b));
                        break;
                    case 1:
                        stack.push(String.valueOf(b-a));
                        break;
                    case 2:
                        stack.push(String.valueOf(a*b));
                        break;
                    case 3:
                        stack.push(String.valueOf(b/a));
                        break;
                    }
                }
            }
        returnValue = Integer.valueOf(stack.pop());
        return returnValue;
        }
}

There are some missing parts in the code though. If you consider the possibility that the RPN expression might be invalid, then you should validate the value after no input by:

1. Check if the stack has only one element,

2. Check if the element is number.

If you consider there might be invalid characters inside the RPN expression, you should also include validation for that too.