Infix to postfix

Algorithm : Infix to Postfix


Infix_to_Postfix(P[1,2,...,N],S[1,2,...,N],E[1,2,..,N],top)
{
  Let us also consider a infix expression 'E'. We have to convert this
  expression 'E' into postfix expression 'P'.
  A stack 'S' with top ‘t’ of capacity of holding N elements is used to  
  perform the Operation.Push and Pop operation is done on top.

1. Insert a symbol ')' at the end of E.
2. Push the symbol '(' into stack S.
3. while(S≠empty)                        //until S becomes empty 
   {                                                       
   item=read a symbol from E.
   if(item=operand)
 add item at the end of P
   else if(item='(')
 push(item)
   else if(item=')')
 {
 x=pop()
 while(x≠'(')
  {
  add x at the end of P
  x=pop()
  }
 }
   else if(item=operator)
 {
 x=pop()
 while(isop(x)=1 and pre(x)≥pre(item))
  {       
  add x at the end of P
  x=pop()
  }
 push(x)
 push(item)
 }
   }
4. print P
5. End
}


//Here isop() is a function which returns 1 if it gets an operator as argument, else
it returns 0.

//pre() is also a function which returns the precedence value or priority
value of an operator.




C Program For Infix to postfix

Source Code:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>

char a[10];
int top=-1;


void push(char item)
{

 if(top==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     top=top+1;
     a[top]=item;
   }
}

char pop()
{
  char item;
  if(top==-1)
   {
     printf("\nStack Underflow");

   }
  else
   {
     item=a[top];
     top=top-1;
   }
  return item;
}

int isop(char y)
{
  switch(y)
   {
     case '+':
     case '-':
     case '*':
     case '/':
     case '%':
     case '^':
       return 1;
       break;
     case '{':
     case '[':
     case '(':
     case ')':
     case '}':
     case ']':
       return 2;
       break;
     default:
      return 0;
      break;
   }
}

int pre(char op)
{
  switch(op)
   {
     case '+':
     case '-':
       return 1;
       break;
     case '*':
     case '/':
     case '%':
       return 2;
       break;
     case '^':
       return 3;
       break;
     default:
      return 0;
      break;
   }
}

main()
{
  int j,k=0,l,i;
  char e[15],p[15],x,y,m;
  clrscr();
  printf("\nEnter an infix expression: ");
  gets(e);
  l=strlen(e);
  strcat(e,")");
  m='(';
  push(m);
  i=0;
  while(top!=-1)
   {
      x=e[i];
      if(isop(x)==0)
       {
  p[k]=x;
  k=k+1;
       }

      else if(x=='(')
       {
  push(x);
       }

      else if(x==')')
       {
  y=pop();
  while(y!='(')
   {
     p[k]=y;
     k=k+1;
     y=pop();
   }
       }

      else if(isop(x)==1)
       {
  y=pop();
  while(isop(y)==1 && pre(y)>=pre(x))
   {
     p[k]=y;
     k=k+1;
     y=pop();
   }
  push(y);
  push(x);
       }
     i++;
   }
  p[k]='\0';
  printf("\nThe postfix expression is :  ");
  puts(p);
  getch();
}




OUTPUT:

Enter an infix expression: (a+b^d)/(e-f)+g

The postfix expression is :  abd^+ef-/g+