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:

OK, based on that calculator implementation of solution will be easy:
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 *