Program to convert an infix expression to postfix expression

This program shows how to convert an infix expression to postfix expression. Before proceeding to program, first understand what is difference between infix expression and postfix expression. Infix notation: X + Y. Operators are written in-between their operands. Postfix notation (also known as “Reverse Polish notation”) : X Y + . Operators are written after their operands.

An infix expression is accepted as input.The expression is pushed into the stack character by character.While pushing the expression,it is pushed as per the priority of the operands.Finally,when the expression is popped out of the stack,it gets converted into post fix expression.An algorithm to convert an infix expression to postfix expression.

Input: A bracket or unbracketed infix expression.

Output: A postfix expression.

Data structure : character type operator stack (opt_stk),

character type operand stck(opd_stk),

character type exp array to store an expression

Detail steps :

1. Initialize the stacks(set opd_top and opt_top to -1)

2. Read an infix expression into exp array.

3. Start processing given expression from first symbol till getting ‘\0? by using one symbol at a time. For each symbol (current token) do the following :

i) If current token is ‘(‘ then push it in opt_stk.

ii)If the current token is ‘)’ then

while opt_stk top operator is not an opening bracket do

begin

pop an operator from opt_stk and print it

end

pop an opening bracket from opt_stk.

iii) If current token is an operand then push it in opd_stk.

iv) If current token is an operand then

a) If an opt_stk is empty, push a current token in opt_stk

b) If a priority of current_token > a priority of opt_stk top operator then push a current token in opt_stk

c) While priority current token <= priority opt_stk top operator do

begin

pop an operator from opt_stk and print it

end

push a current token in opt_stk

4. While opt_stk is not empty do

begin

pop an operator from opt_stk and print it

end

include< stdio.h >
#include< conio.h >

#define max 50

void main()

{

char exp[100],opt_stk[max],ch;

int opt_top,i;

clrscr();

opt_top=-1;

printf(“\nEnter an infix exp \n”);

gets(exp);

//Process the expression by taking one token(symbol) at a time

for(i=0;exp[i]!=’\0′;i++)

{

if (exp[i]=='(‘)

{

push_opt(opt_stk,&opt_top,&exp[i]);

}

else if (exp[i]==’)’)

{

//while opt stk top operator is not an openeing

//bracket pop an operator and print it on screen

while(opt_stk[opt_top]!= ‘(‘)

{

pop_opt(opt_stk,&opt_top,&ch);

printf(“%c”,ch);

}

pop_opt(opt_stk,&opt_top,&ch); //skip ‘(‘

}

else

if (chk_opt(exp[i])==0) //current token is an operand

printf(“%c”,exp[i]);

else //current token is an operator

{

if(opt_top==-1) //opt stack is empty

{

push_opt(opt_stk,&opt_top,&exp[i]);

}

else

if (priority(exp[i]) > priority(opt_stk[opt_top]))

{

push_opt(opt_stk,&opt_top,&exp[i]);

}

else

{

while (priority (exp[i])<=priority(opt_stk[opt_top]))

{

if (opt_top == -1)

break;

pop_opt(opt_stk,&opt_top,&ch);

printf(“%c”,ch);

}//while

push_opt(opt_stk,&opt_top,&exp[i]);

}//else

}//else

}//for

while(opt_top!=-1)

{

pop_opt(opt_stk,&opt_top,&ch);

printf(“%c”,ch);

}//while

}//main

//check whether given character is an operator or not

//Return 1 if an operator else return 0

int chk_opt(char ch)

{

switch(ch)

{

case ‘^’:

case ‘*’:

case ‘/’:

case ‘%’:

case ‘+’:

case ‘-‘: return(1);

default : return(0);

}//switch

}//chk_opt

//Return a priority of specific operator if a valid operator elese return 0

int priority (char opt)

{

switch(opt)

{

case ‘^’ : return(4);

case ‘*’ :

case ‘/’ :

case ‘%’ : return(3);

case ‘+’ :

case ‘-‘ :return(2);

case ‘(‘ : return(1);

default : return (0);

}//switch

}//priority

//Push an operator(ch) in opt_stack

int push_opt(char opt_stk[max],int *opt_top,char *ch)

{

if(*opt_top==max-1)

{

return(-1);

}

else

{

(*opt_top)++;

opt_stk[*opt_top]=*ch;

return(1);

}

}

//Pop an operator(ch) in opt_stack

int pop_opt(char opt_stk[max],int *opt_top,char *ch)

{

if (*opt_top==-1)

{

return(-1);

}

else

{

*ch=opt_stk[*opt_top];

(*opt_top)–;

return(1);

}