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{
                int calculate(int left, int right){
                    return left+right;
                int calculate(int left, int right){
                    return left-right;
                int calculate(int left, int right){
                    return left*right;
                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){
                        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;
                    operation  = Operation.get(token);
                    int secondValue = result.pop();
                }else {
                    result.push( Integer.valueOf(token));
            return result.pop();
        boolean isNum(String data){
            boolean isNum = true;
            }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.