InFixTo PostFix Conversion in C

Infix to postfix conversion

Infix Expression : Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.
Postfix Expression : The Postfix(Postorder) form of the above expression is "23*45/-".

Infix to Postfix Conversion :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :
  1. Scan the Infix string from left to right. Initialise an empty stack. 
  2. If the scannned character is an operand, add it to the Postfix string. If the scanned character is an operator and if the stack is empty Push the character to stack. 
  3. If the scanned character is an Operand and the stack is not empty, compare the precedence of the character with the element on top of the stack (topStack). If topStack has higher precedence over the scanned character Pop the stack else Push the scanned character to stack. Repeat this step as long as stack is not empty and topStack has precedence over the character. Repeat this step till all the characters are scanned. 
  4. (After all characters are scanned, we have to add any character that the stack may have to the Postfix string.) If stack is not empty add topStack to Postfix string and Pop the stack. Repeat this step as long as stack is not empty. 
  5. Return the Postfix string.

Example of Infix to Postfix :

Let us see how the above algorithm will be implemented using an example.

Infix String : a+b*c-d

Initially the Stack is empty and our Postfix string has no characters. Now, the first character scanned is 'a'. 'a' is added to the Postfix string. The next character scanned is '+'. It being an operator, it is pushed to the stack. 



Stack



Postfix String

Next character scanned is 'b' which will be placed in the Postfix string. Next character is '*' which is an operator. Now, the top element of the stack is '+' which has lower precedence than '*', so '*' will be pushed to the stack. 



Stack



Postfix String

The next character is 'c' which is placed in the Postfix string. Next character scanned is '-'. The topmost character in the stack is '*' which has a higher precedence than '-'. Thus '*' will be popped out from the stack and added to the Postfix string. Even now the stack is not empty. Now the topmost element of the stack is '+' which has equal priority to '-'. So pop the '+' from the stack and add it to the Postfix string. The '-' will be pushed to the stack. 



Stack



Postfix String

Next character is 'd' which is added to Postfix string. Now all characters have been scanned so we must pop the remaining elements from the stack and add it to the Postfix string. At this stage we have only a '-' in the stack. It is popped out and added to the Postfix string. So, after all characters are scanned, this is how the stack and Postfix string will be :



Stack



Postfix String

End result :

Infix String : a+b*c-d
Postfix String : abc*+d-



Infix to Postfix Conversion Algorithm :

The algorithm transforms the infix expression A into equivalent postfix B. The algorithm uses stack to temporirly hold opertors and left parenthesis. The postfix expression B will be constructed left to right using operands from A and operators which are removed from STACK. We begin by pushing left parenthesis onto STACK and adding a right parenthesis at the end of A. The algorithm is finished when STACK is empty.

Step 1. Push Left Parenthesis “(“ onto stack and add right parenthesis “)” to end of the A

Step 2. Scan A from left to right and repeat steps 3 to 6 for each element of A until the stack is empty
Step 3. If an operand is encountered, add it to B
Step 4. If a left parenthesis is encountered push it onto the stack

Step 5. If an operator is encountered then

a. Repeatedly pop from the STACK and add to B each operator (on the top of the stack) which has the same precedence as or higher precedence than operator
b. Add operator to STACK

Step 6. If a right parenthesis is encountered, then
a. Repeatedly pop from the STACK and add to B each operator (on the top of STACK) until a left parenthesis is encountered
b. Remove the left parenthesis. (Do not add left parenthesis to B)

Step 7. Exit

Infix to Postfix Conversion Program :


#include<stdio.h>
#include<conio.h>
#define MAX 50 
char post[MAX],in[MAX],stack[MAX];
int top=-1,toper=-1; void insertpostfix(char x);
void insertstack(char x);
void popstack(char x); int checkprec(char x);
void pop_all();
void main()
{
 int i,j,chk,chk2;
 clrscr();
 printf("\nInsert an infix notation :: ");
 gets(in);
 stack[++toper]='('; in[strlen(in)]=')';
 printf("\nCharacter\tStack\tPostfix\n");
 for(i=0;i<strlen(in);i++) 
 {
  if(in[i]>='a' && in[i]<='z' || in[i]>='A' && in[i]<='Z' || in[i]>='0' && in[i]<='9')
  {
   insertpostfix(in[i]);
  }
  else if(in[i]=='(') 
  {
   insertstack(in[i]);
  }
  else if(in[i]=='+' || in[i]=='-' || in[i]=='/' || in[i]=='*' || in[i]=='^') 
  {
   chk=checkprec(in[i]); chk2=checkprec(stack[toper]); 
   if(chk>chk2) 
   {
    insertstack(in[i]); 
   }
   else 
   {
    popstack(in[i]);
   }
  }
  else if(in[i]==')') { pop_all(); 
  }
  printf("\n%c\t\t",in[i]); 
  printf("%s",stack);
  printf("\t%s",post); 
 }
 printf("\n\nFinal Postfix Notation :: %s",post); getch(); 
}
 
void insertpostfix(char x)
{
 top++; post[top] = x;
}
void insertstack(char x) 
{
 toper++; stack[toper] = x; 
}
void popstack(char x) 
{
 top++;
 post[top] = stack[toper];
 stack[toper] = x;
}
void pop_all() 
{
 while (stack[toper] != '(') 
 {
  top++; post[top] = stack[toper]; 
  stack[toper] = '\0'; toper--; 
 }
 stack[toper] = '\0'; toper--; 
}
int checkprec(char x)
{
 switch (x) 
 {
 case '+':
 case '-':
  return 1;
 case '*':
 case '/':
  return 2;
 case '^':
  return 3;
 case '(':
  return 0;
 defaultreturn 0; 
 }
}



Check out Evaluation of Postfix Expression here

Post a Comment