Wednesday, 8 June 2011

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*

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
}
}
*/

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