Prefix/Postfix/Infix Notation

Conversion Of Expressions

When higher level programming languages came into existence one of the major hurdles faced by the computer scientists was to generate machine language instructions which would properly evaluate any arithmetic expression. To convert a complex assignment statement such as:

X = A/B + C * D - F * G/Q

into a correct instruction sequence was a formidable task. That it is no longer considered so formidable is a tribute to the elegant and simple solutions that the computer scientists came out with. As of today this conversion is considered to be one of the minor aspects of compiler writing. To fix the order of evaluation of an expression each language assigns to each operator a priority. Even after assigning priorities how can a compiler accept an expression and produce correct code? The answer is given by reworking the expression into a form we call postfix notation. If e is an expression with operators and operands, the conventional way of writing e is called infix, because the operators come in between the operands (Unary operators precede their operand). The postfix form of an expression calls for each operator to appear after its operands. For example:

infix; A*B/C has a postfix form: AB*C/

If we study the postfix form we see that the multiplication comes immediately after its two operands A and B. Now imagine that A * B is computed and stored in T. Then we have the division operator '/' coming immediately after its two operands T and C.

Notice three features of the postfix expression:

• The operands maintain the same order as in the equivalent infix expression.

• Parentheses are not needed to designate the expression unambiguously.

• While evaluating the postfix expression the priority of the operators is no longer relevant.

Given below is a program which converts an infix expression into its postfix form.

#define MAX 1000

void main( )

{

static char target[MAX], stack[MAX];

char*t, str[MAX], *s, n1, n2, item, nn;

int p1, p2, i, top = -1 ;

printf("\nEnter the infix expression:");

gets(str) ;

s = str ;

t = target ;

while(*s)

{

if (*s == '`' || *s == '\t')

{

s++;

continue;

}

if(isdigit (*s) || isalpha (*s))

{

while (isdigit(*s) || isalpha (*s))

{

*t = *s; t++; s++;

}

}

if(*s == '(')

{

push (stack, &top, *s); s++;

}

if( *s == ')')

{

n1 = pop (stack, &top);

while (n1)!='(' )

{

*t = n1;

t++;

n1 = pop (stack, &top) ;

}

s++;

}

if(*s =='+' || *s =='*' || *s == '/' || *s == '%' )

{

if ( top == -1)

push(stack, &top, *s);

else

{

n1 = pop (stack, &top);

while( priority (n1) >= priority(*s ) )

{

*t = n1;

t++;

n1 = pop (stack, &top) ;

}

push(stack, &top, n1);

push(stack, &top, *s);

}

s++;

}

}

while (top != -1)

{

n1 = pop (stack, &top);

*t = n1; t++;

}

*t = '\0'; t=target;

while(*t)

{

printf("%c", *t);

t++;

}

}

/*checks the priority of the operators*/

int priority(char ele)

{

int pri;

char a, b, c;

if ( ele =='*' || ele == '/'|| ele == '%' )

pri = 2;

else

{

if(ele == '+' || ele == '-')

pri = 1;

else

pri = 0;

}

return pri ;

}

void push(char *stk, int*sp, char item)

{

if (*sp == MAX)

printf("\nStack is full");

else

{

*sp = *sp + 1;

stk[*sp] = item;

}

}

char pop (char *stk, int*sp)

{

int item;

if(*sp == -1)

{

printf("\nStack is empty");

return(-1);

}

else

{

item = stk[*sp];

*sp=*sp - 1;

return (item);

}

}