Postfix To Prefix Conversion

Evaluation of Postfix Expression

So far we have seen programs which could translate expressions from infix to postfix to prefix notation to any such combination. The virtue of a postfix notation is that it enables easy evaluation of expressions. To begin with, the need for parentheses is eliminated. Secondly, the priority of the operators is no longer relevant. The expression may be evaluated by making a left to right scan, stacking operands, and evaluating operators using operands from the stack and finally placing the result onto the stack. This evaluation process is much simpler than attempting a direct evaluation of infix notation. The following program implements the postfix expression evaluation algorithm.

#define MAX 25

void push ( int * , int * , int ) ;

int pop ( int *, int * ) ;

main( )

{

char str[MAX], *s ;

int n1, n2, n3, nn ;

int stack[MAX], top = -1 ;

clrscr();

printf ( "\nEnter the postfix expression to be evaluated: " ) ;

gets ( str ) ;

s = str ;

while ( *s )

{

/* skip whitespace, if any */

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

{

s++ ;

continue ;

}

/* if digit is encountered */

if ( *s >= 48 && *s <= 57 )

{

nn = *s - '0' ;

push ( stack, &top, nn ) ;

}

else

{

/* if operator is encountered */

n1 = pop ( stack, &top ) ;

n2 = pop ( stack, &top ) ;

switch ( *s )

{

case '+' :

n3 = n2 + n1 ;break ;

case '-' :

n3 = n2 - n1 ;break ;

case '/' :

n3 = n2 / n1 ;break ;

case '*' :

n3 = n2 * n1 ;break ;

case '%' :

n3 = n2 % n1 ;break ;

default :

printf ( "Unknown operator" ) ;

exit ( 1 ) ;

}

push ( stack, &top, n3 ) ;

}

s++ ;

}

printf ( "Result is : %d", pop ( stack, &top ) ) ;

}

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

{

if ( *sp == MAX )

printf ( "\nStack is full" ) ;

else

{

*sp = *sp + 1 ;

stk[*sp] = item ;

}

}

int pop ( int *stk, int *sp )

{

int item ;

if ( *sp == -1 )

{

printf ( "\nStack is empty" ) ;

return ( -1 ) ;

}

else

{

item = stk[*sp] ;

*sp = *sp - 1 ;

return ( item ) ;

}

}