Stack Infix to Postfix Notation

ALGORITHM : Infix to Postfix 

• 
  

  STEP 1 : Read the given infix expression into string called infix.

• 
  

  
  

  STEP 2 : Read one character at a time and perform the following operations :
• If the character is an operand, then add the operand to the postfix string.

• If the character is not an operand, then check, 
  If the stack is not empty and precedence of the top of the 
  stack operator is higher than the read operator,
  then pop the operator from stack and add this 
  operator to the postfix string.
  Else push the operator onto the stack.

• 
  

  STEP 4 : If stack is not empty, then pop the operator from stack and add this operator to the postfix string.

• 
  

  
  

  STEP 5 : Repeat STEP 4 till all the operators are popped from the stack.

• 
  

  
  

  STEP 6 : Display the result of given infix expression or resultant postfix expression stored in a string called postfix from this algorithm.

Source code:-

1:  #include <stdio.h>  
2:  #include <dos.h>  
3:  #include <string.h>  
4:  #define operand(x) (x>='a'&&x<='z'||x>='A'&& x<='Z'||x>='0'&& x<='9')  
5:  char infix[30];  
6:  char postfix[30];  
7:  char stack[30];  
8:  int top,i=0;  
9:  void init()  
10:  {  
11:   top=-1;  
12:  }  
13:  void push(char x)  
14:  {  
15:   stack[++top]=x;  
16:  }  
17:  char pop()  
18:  {  
19:   return (stack[top--]);  
20:  }  
21:  int isp(char x)  
22:  {  
23:       int y;  
24:   y=(x=='('?0:x=='^'?4:x=='*'?2:x=='/'?2:x=='+'?1:x=='-'?1:x==')'?6:-1);  
25:       return y;  
26:  }  
27:  int icp(char x)  
28:  {  
29:       int y;  
30:       y=(x=='('?4:x=='^'?4:x=='*'?2:x=='/'?2:x=='+'?1:x=='-'?1:x==')'?6:-1);  
31:       return y;  
32:  }  
33:  void infixtopostfix()  
34:  {  
35:   int j,l=0;  
36:   char x,y;  
37:   stack[++top]='\0';  
38:   for(j=0; (x=infix[i++])!='\0'; j--)  
39:   {  
40:     if(operand(x))  
41:        postfix[l++]=x;  
42:     else  
43:     {  
44:       if(x==')')  
45:      {  
46:        while((y=pop())!='(')  
47:         postfix[l++]=y;  
48:      }  
49:       else  
50:       {  
51:        while (isp(stack[top])>=icp(x))  
52:         postfix[l++]=pop();  
53:        push(x);  
54:       }  
55:     }  
56:    }  
57:    while(top>=0)  
58:     postfix[l++]=pop();  
59:  }  
60:  int main()  
61:  {  
62:    init();  
63:    printf("Enter an infix Expression:");  
64:    scanf("%s",infix);  
65:    infixtopostfix();  
66:    printf("The Resulting postfix exp is:%s",postfix);  
67:    return 0;  
68:  }