Convert an infix expression to prefix expression

Input : A bracketed or unbracketed infix expression.

Output:A prefix expression

Detail steps:

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

2.Read the infix expression.

3.Process the expression from first symbol till getting ''. For each current symbol(current token) do

i.If current token is an opening bracket then push it in opt_stk

ii.If current token is a closing bracket then

while opt_stk top is not an opening bracket do

begin

     pop an operator from opt_stk and store its string form in opt

     pop an operand from opd_stk and store it in opd2

     pop an operand from opd_stk and store it in opd1

     join above values in following format

     ans=opt opd1 opd2

     push the resultant string in opd_stk

end

#include
#include
#define max 50
void main()
{
          char exp[100],opt_stk[max],ch,opd_stk[max][80];
          int opt_top,opd_top,i;
          char opt[80],opd1[80],opd2[80],temp[80];
          clrscr();
          opt_top=opd_top=-1;//....init opt and opd stacks
          printf("nEnter an infix exp n");
          gets(exp);
          //...process the expression by taking one symbol(token) at a time
	  for(i=0;exp[i] !='';i++)
	  {
		     if(exp[i]=='(')
			       push_opd(opt_stk,&opt_top,&exp[i]);
		     else if(exp[i]==')')
		     {
				while (opt_stk[opt_top] !='(')
				{
					 pop_opd(opt_stk,&opt_top,&ch);
					 opt[0]=ch; opt[1]=''; // convert opt into string
					 pop_opd(opd_stk,&opd_top,opd2);
					 pop_opd(opd_stk,&opd_top,opd1);
					 strcpy(temp,opt);
					 strcat(temp,opd1);
					 strcat(temp,opd2);
					 push_opd(opd_stk,&opd_top,temp);
				}
				pop_opd(opt_stk,&opt_top,&ch); // pop (
		     }
		     else
		     if( chk_opt(exp[i])==0) //....current token is an operand
		     {
			      temp[0]=exp[i];
			      temp[1]= '';
			      push_opd(opd_stk,&opd_top,temp);
		     }
		     else //....current token is an operator
		     {
				if(opt_top == -1)//....opt stack is empty
					   push_opd(opt_stk,&opt_top,&exp[i]);
				else
				if (priority( exp[i]) > priority(opt_stk[opt_top]))
					    push_opd(opt_stk,&opt_top,&exp[i]);
				else
				{
					    while (priority(exp[i]) < =priority(opt_stk[opt_top]))
					    {
						       if( opt_top == -1 )
								   break;
						       pop_opd(opt_stk,&opt_top,&ch);
						       opt[0] = ch;opt[1] = '';
						       pop_opd(opd_stk,&opd_top,opd2);
						       pop_opd(opd_stk,&opd_top,opd1);
						       strcpy(temp,opt);
						       strcat(temp,opd1);
						       strcat(temp,opd2);
						       push_opd(opd_stk,&opd_top,temp);
					    } //while
					    push_opd(opt_stk,&opt_top,&exp[i]);
				} //else
		      }//else
	   } // for
	   //....while opt stack is not empty do the following
	   while ( opt_top != -1 )
	   {
		     pop_opd(opt_stk,&opt_top,&ch);
		     opt[0] = ch; opt[1] = '';
		     pop_opd(opd_stk,&opd_top,opd2);
		     pop_opd(opd_stk,&opd_top,opd1);
		     strcpy(temp,opt);
		     strcat(temp,opd1);
		     strcat(temp,opd2);
		     push_opd(opd_stk,&opd_top,temp);
	    } //while
	    printf("nPrefix form is n %s",opd_stk[opd_top]);
} // main
//....push an operand in string from into opd stack
int push_opd( char opd_stk[max][80],int *opd_top, char temp[80])
{
	 if( *opd_top == max -1 )
		    return(-1);
	 else
	 {
		    (*opd_top) ++;
		    strcpy(opd_stk[*opd_top],temp);
		    return(1);
	 }
}
//....pop an operand from opd stack in string form
int pop_opd( char opd_stk[max][80],int *opd_top, char temp[80])
{
	 if( *opd_top == -1 )
		    return(-1);
	 else
	 {
		    strcpy(temp,opd_stk[*opd_top]);
		    (*opd_top)--;
		    return(1);
	 }
}
int priority(char opt)
{
	switch(opt)
	{
		case '^': return(4);
		case '*':
		case '/':
		case '%':return(3);
		case '+':
		case '-':return(2);
		case '(':return(1);
		default:return(0);
	}
}
int chk_opt(char ch)
{
	switch(ch)
	{
		case '^':
		case '*':
		case '/':
		case '%':
		case '+':
		case '-':return(1);
		default:return(0);
	}
}