Infix, Prefix and Postfix notations

“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