“Notations are created for easy processing of expressions. Polish and Reverse Polish Notations are popular ones. Normal notation is human readable.”
There are 3 kinds of expression notations: infix, prefix and postfix.
- Infix: is human readable. (2+3)*4
- Prefix: is readable with stack. Expressions first, values next. *+234
- Postfix: Values first, expressions next. 23+4*
Read more about the prefix notation here: http://en.wikipedia.org/wiki/Polish_notation
Prefix & postfix doesn’t need to use brackets and can be easily represented using stack or tree.
The main advantage is that we don’t need to care much about the precedence as in Infix notation.
- We need to come in reverse and push into stack the integers
- When we see a operator, we need to operate the top 2 elements in the stack.
- Note that, we use space as the delimiter between 2 digits. For operators, we don’t need that
- In the stack we will have the only element which is the processed output of the expression