Infix and Postfix Expression in DSA

/*This file contains program to convert Infix expression into
Postfix expression and then to evaluate the Postfix expression.*/

#include<stdio.h>
#include<string.h>
#include<math.h>
#define SIZE 80

union expression
{
   char oper;
   float oprnd;
};

struct token
{
   union expression expr;
   int type;
   struct token *next;
};

union Datatype
{
   char cData;
   float fData;
};

struct stack
{
   union Datatype dType;
   struct stack *next;
};

void Add_Token(struct token **head, float Token, int Type);
void Extract_Token(struct token **infix, char *str);
void Infix_To_Postfix(struct token *infix,struct token **postfix);
long float Postfix_Evaluation(struct token **postfix);

void Push_Char(struct stack **tos, char Token);
char Pop_Char(struct stack **tos);
void Push_Float(struct stack **tos, float Token);
float Pop_Float(struct stack **tos);

int Check_Parenthesis(char *str);
int Check_Priority(char iToken, char sToken);
void Display(struct token *postfix);

void Delete_List(struct token **head);

int main()
{
   char string[SIZE];
   struct token *Infix=NULL;
   struct token *Postfix=NULL;
   int status,ch;
   long float Result;
   clrscr();
   printf("\n\n\n\nOPERATORS ALLOWED IN EXPRESSION:\n\n\t  +   -   *   /");
   printf("\n\n\n\nENTER INFIX EXPRESSION: \n\n\n");
   gets(string);
   status=Check_Parenthesis(string);
   if(status==0)
   {
      clrscr();
      printf("\n\n\n\n\t\t ERROR: PARENTHESIS ARE NOT BALANCED.");
      getch();
   }
   else
   {
      Extract_Token(&Infix,string);
      Infix_To_Postfix(Infix,&Postfix);
      clrscr();
      printf("\n\n\n\n INFIX EXPRESSION IS:\n\n\n");
      printf("%s",string);
      printf("\n\n\n\n POSTFIX EXPRESSION IS:\n\n\n");
      Display(Postfix);
      Result=Postfix_Evaluation(&Postfix);
      printf("\n\n\n\n RESULT OF POSTFIX EVALUATION IS:\n\n\n\t %.3lf",Result);
      getch();
   }
   Delete_List(&Infix);
   Delete_List(&Postfix);
   return(0);
}

/*************************************************************************
** Function to add extracted token into expression.
*************************************************************************/

void Add_Token(struct token **head, float Token, int Type)
{
   struct token *move=*head;
   struct token *newNode=NULL;
   newNode=(struct token *)malloc(sizeof(struct token));
   if(newNode==NULL)
   {
      clrscr();
      printf("\n\n\n\n\t ERROR: INSUFFICIENT MEMORY SPACE.");
      getch();
      exit(1);
   }
   else
   {
      if(Type==0)
newNode->expr.oper=(char)Token;
      else
newNode->expr.oprnd=Token;
      newNode->type=Type;
      newNode->next=NULL;
   }
   if(*head==NULL)
      *head=newNode;
   else
   {
      while(move->next!=NULL)
move=move->next;
      move->next=newNode;
   }
}

/*************************************************************************
** Function to extract tokens from entered expression.
*************************************************************************/

void Extract_Token(struct token **infix, char *str)
{
   int isDot=0,isRPar=0,count=0;
   long int value=0;
   float tokn=0;
   while(*str!=NULL)
   {
      if(*str>='0' && *str<='9')
      {
value=(value*10)+((float)(*str))-48;
if(isDot==1)
   count++;
      }
      else if(*str=='.')
isDot=1;
      else if(*str!='(')
      {
if(isRPar!=1)
{
   if(isDot==1)
   {
      tokn=value/pow(10,count);
      Add_Token(infix,tokn,1);
      isDot=count=0;
   }
   else
   {
      tokn=value;
      Add_Token(infix,tokn,1);
   }
}
tokn=(float)(*str);
Add_Token(infix,tokn,0);
value=0;
if(tokn==')')
   isRPar=1;
else
   isRPar=0;
      }
      else
      {
tokn=(float)(*str);
Add_Token(infix,tokn,0);
      }
      str++;
   }
   str--;
   if(*str!=')')
   {
      if(isDot==1)
      {
tokn=value/pow(10,count);
Add_Token(infix,tokn,1);
      }
      else
      {
tokn=value;
Add_Token(infix,tokn,1);
      }
   }
}

/*************************************************************************
** Function to convert infix expression into postfix expression.
*************************************************************************/

void Infix_To_Postfix(struct token *infix,struct token **postfix)
{
   struct stack *tos=NULL;
   struct token *iMove=infix;
   char Oper;
   int prior=0;
   while(iMove!=NULL)
   {
      if(iMove->type==1)
Add_Token(postfix,iMove->expr.oprnd,1);
      else
      {
if(iMove->expr.oper=='(')
   Push_Char(&tos,iMove->expr.oper);
else if(iMove->expr.oper==')')
{
   Oper=Pop_Char(&tos);
   while(Oper!='(')
   {
      Add_Token(postfix,(float)Oper,0);
      Oper=Pop_Char(&tos);
   }
}
else
{
   prior=Check_Priority(iMove->expr.oper,tos->dType.cData);
   if(prior==1)
      while(tos->dType.cData!='('&&tos!=NULL)
      {
 Oper=Pop_Char(&tos);
 Add_Token(postfix,(float)Oper,0);
      }
   else if(prior==2)
      while((tos->dType.cData=='*'||tos->dType.cData=='/')&&(tos->dType.cData!='(')&&(tos!=NULL))
      {
 Oper=Pop_Char(&tos);
 Add_Token(postfix,(float)Oper,0);
      }
   Push_Char(&tos,iMove->expr.oper);
}
      }
      iMove=iMove->next;
   }
   while(tos!=NULL)
   {
      Oper=Pop_Char(&tos);
      Add_Token(postfix,(float)Oper,0);
   }
   free(tos);
}

/*************************************************************************
** Function to evaluate postfix expression.
*************************************************************************/

long float Postfix_Evaluation(struct token **postfix)
{
  struct stack *tos=NULL;
  struct token *move=*postfix;
  float oprnd1,oprnd2;
  long float result;
  char Oper;
  while(move!=NULL)
  {
     if(move->type==1)
Push_Float(&tos,move->expr.oprnd);
     else
     {
Oper=move->expr.oper;
switch(Oper)
{
case '+':
oprnd2=Pop_Float(&tos);
oprnd1=Pop_Float(&tos);
result=oprnd1+oprnd2;
Push_Float(&tos,result);
break;
case '-':
oprnd2=Pop_Float(&tos);
oprnd1=Pop_Float(&tos);
result=oprnd1-oprnd2;
Push_Float(&tos,result);
break;
case '*':
oprnd2=Pop_Float(&tos);
oprnd1=Pop_Float(&tos);
result=oprnd1*oprnd2;
Push_Float(&tos,result);
break;
case '/':
oprnd2=Pop_Float(&tos);
oprnd1=Pop_Float(&tos);
result=oprnd1/oprnd2;
Push_Float(&tos,result);
break;
}
     }
     move=move->next;
  }
  result=Pop_Float(&tos);
  free(tos);
  return(result);
}

/*************************************************************************
** Function to push a character element on stack.
*************************************************************************/

void Push_Char(struct stack **tos, char Token)
{
   struct stack *newNode=NULL;
   newNode=(struct stack *)malloc(sizeof(struct stack));
   if(newNode==NULL)
   {
      clrscr();
      printf("\n\n\t ERROR: INSUFFICIENT MEMORY SPACE.");
      getch();
      exit(1);
   }
   else
   {
      newNode->dType.cData=Token;
      newNode->next=NULL;
   }
   if(*tos==NULL)
      *tos=newNode;
   else
   {
      newNode->next=*tos;
      *tos=newNode;
   }
}

/*************************************************************************
** Function to pop a character element from stack.
*************************************************************************/

char Pop_Char(struct stack **tos)
{
   struct stack *temp=*tos;
   char data=(*tos)->dType.cData;
   *tos=(*tos)->next;
   free(temp);
   return(data);
}

/*************************************************************************
** Function to push a float element on stack.
*************************************************************************/

void Push_Float(struct stack **tos, float Token)
{
   struct stack *newNode=NULL;
   newNode=(struct stack *)malloc(sizeof(struct stack));
   if(newNode==NULL)
   {
      clrscr();
      printf("\n\n\t ERROR: INSUFFICIENT MEMORY SPACE.");
      getch();
      exit(1);
   }
   else
   {
      newNode->dType.fData=Token;
      newNode->next=NULL;
   }
   if(*tos==NULL)
      *tos=newNode;
   else
   {
      newNode->next=*tos;
      *tos=newNode;
   }
}

/*************************************************************************
** Function to pop a float element from stack.
*************************************************************************/

float Pop_Float(struct stack **tos)
{
   struct stack *temp=*tos;
   float data=(*tos)->dType.fData;
   *tos=(*tos)->next;
   free(temp);
   return(data);
}

/*************************************************************************
** Function to check balancing of paranthesis in entered expression.
*************************************************************************/

int Check_Parenthesis(char *str)
{
   int count=0;
   while(*str!=NULL)
   {
      if(*str=='(')
count++;
      else if(*str==')')
count--;
      str++;
   }
   if(count==0)
      return(1);
   else
      return(0);
}

/*************************************************************************
** Function to check priority of infix expression's operator & TOS element.
*************************************************************************/

int Check_Priority(char iToken, char sToken)
{
   if(sToken=='(')
      return(0);
   else if(iToken=='+'||iToken=='-')
      return(1);
   else if( (iToken=='*'||iToken=='/') && (sToken=='*'||sToken=='/') )
      return(2);
   else
      return(0);
}

/*************************************************************************
** Function to display an expression.
*************************************************************************/

void Display(struct token *head)
{
   struct token *move=head;
   while(move!=NULL)
   {
      if(move->type==0)
printf(" %c",move->expr.oper);
      else
printf("% .2f",move->expr.oprnd);
      move=move->next;
   }
}

/*************************************************************************
** Function to delete linked list.
*************************************************************************/

void Delete_List(struct token **head)
{
   struct token *temp=NULL;
   while(*head!=NULL)
   {
      temp=*head;
      *head=(*head)->next;
      free(temp);
   }
}


/*output of the prorgam*/

 INFIX EXPRESSION IS:
1+2-3*8

 POSTFIX EXPRESSION IS:
 1.00 2.00 + 3.00 8.00 * -

 RESULT OF POSTFIX EVALUATION IS:
         -21.000



for more codes you can visit http://codesofprogramming.blogspot.in/