Evaluate Reverse Polish Notation Algorithm

I’ve solved a few tasks from http://leetcode.com/ and going to publish my solutions,

So, first task is

Evaluate Reverse Polish Notation

The task description is :

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

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

Some examples:

  [“2”, “1”, “+”, “3”, “*”] -> ((2 + 1) * 3) -> 9

  [“4”, “13”, “5”, “/”, “+”] -> (4 + (13 / 5)) -> 6

Stop and think

What do we have ? I can see some  list of the numbers and operations, so, it looks like you or me added all items in LIFO style, like  {2->1->+-> and so on}. OK, good, we can try to find data structure implemented that style. Each of us knows about Stack … OK, good, try to use that data structure in our implementation …

Firstly I’ve added calculator:

enum Operation{
            PLUS("+"){
                int calculate(int left, int right){
                    return left+right;
                }
            },MINUS("-"){
                int calculate(int left, int right){
                    return left-right;
                }
            },MULTIPLY("*"){
                int calculate(int left, int right){
                    return left*right;
                }
            },DIVIDE("/"){
                int calculate(int left, int right){
                    return left/right;
                }
            };
            String operation;
            Operation(String op){
                operation = op;
            }
            String getName(){
                return operation;
            }
            abstract int calculate(int left, int right);
            static Operation get(String val){
                Operation[] operations = values();
                for(Operation operation: operations){
                    if(operation.getName().equals(val))
                        return operation;
                }
                return null;
            }
        }
OK, based on that calculator implementation of solution will be easy:
public class Solution {
     public int evalRPN(String[] tokens) {
            Stack<Integer> result = new Stack<Integer>();
            for (String token : tokens) {
                Operation operation;
                if(!isNum(token)){
                    operation  = Operation.get(token);
                    int secondValue = result.pop();
                    result.push(operation.calculate(result.pop(),secondValue));
                }else {
                    result.push( Integer.valueOf(token));
                }
            }
            return result.pop();
        }
 
        boolean isNum(String data){
            boolean isNum = true;
            try{
                Integer.parseInt(data);
            }catch(Exception e){
                isNum = false;
            }
            return isNum;
        }
}
So, you can see I am using Stack to store numbers and result of calculations,  after all calculations last value in Stack will be our result…
That is easy and perfect 🙂
Cheers !

Leave a Reply

Your email address will not be published. Required fields are marked *