“Notations are created for easy processing of expressions. Polish and Reverse Polish Notations are popular ones. Normal notation is human readable.”

Introduction

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.

Code

`/*`

`Scan the given prefix expression from right to left`

`for each symbol`

` {`

` if operand then`

` push onto stack`

` if operator then`

` {`

` operand1=pop stack`

` operand2=pop stack`

` compute operand1 operator operand2`

` push result onto stack`

` }`

` }`

`return top of stack as result`

`*/`

`void main()`

{

char* str = "*-5 6 57";

StackList opStack;

` int d, sum = 0;`

` int result=0;`

` int count = 0;`

` char* rstr = str;`

while(*rstr != '\0') rstr++;

rstr--;

` while(rstr > str-1) {`

` if(isdigit(*rstr)) {`

d = *rstr - 48;

` if(count == 0) sum = d;`

sum += d*count*10;

count++;

` } else {`

` if(sum != 0) {`

opStack.push(sum);

sum = 0;

count = 0;

}

` switch(*rstr)`

{

case '+':

opStack.push(opStack.pop() + opStack.pop());

` break;`

case '*':

opStack.push(opStack.pop() * opStack.pop());

` break;`

case '-':

opStack.push(opStack.pop() - opStack.pop());

` break;`

case '/':

opStack.push(opStack.pop() / opStack.pop());

` break;`

}

}

rstr--;

}

cout<<opStack.pop();

}

- 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