# Conversion of an Infix Expression into a Postfix Expression

Let I be an algebraic expression written in infix notation. I may contain parentheses, operands, and operators. For simplicity of the algorithm we will use only +, –, *, /, % operators. The precedence of these operators can be given as follows:

Higher priority *, /, %
Lower priority +, –

No doubt, the order of evaluation of these operators can be changed by making use of parentheses. For example, if we have an expression A + B * C, then first B * C will be done and the result will be added to A. But the same expression if written as, (A + B) * C, will evaluate A + B first and then the result will be multiplied with C

The algorithm uses a stack to temporarily hold operators. The postfix expression is obtained from left-to-right using the operands from the infix expression and the operators which are removed from the stack. The first step in this algorithm is to push a left parenthesis on the stack and to add a corresponding right parenthesis at the end of the infix expression. The algorithm is repeated until the stack is empty

## Program to convert an infix expression into its equivalent postfix notation using C

```#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
char st[MAX];
int top=–1;
void push(char st[], char);
char pop(char st[]);
void InfixtoPostfix(char source[], char target[]);
int getPriority(char);
int main()
{
char infix[100], postfix[100];
clrscr();
printf("\n Enter any infix expression : ");
gets(infix);
strcpy(postfix, "");
InfixtoPostfix(infix, postfix);
printf("\n The corresponding postfix expression is : ");
puts(postfix);
getch();
return 0;
}
void InfixtoPostfix(char source[], char target[])
{
int i=0, j=0;
char temp;
strcpy(target, "");
while(source[i]!='\0')
{
if(source[i]=='(')
{
push(st, source[i]);
i++;
}
else if(source[i] == ')')
{
while((top!=–1) && (st[top]!='('))
{
target[j] = pop(st);
j++;
}
if(top==–1)
{
printf("\n INCORRECT EXPRESSION");
exit(1);
}
temp = pop(st);//remove left parenthesis
i++;
}
else if(isdigit(source[i]) || isalpha(source[i]))
{
target[j] = source[i];
j++;
i++;
}
else if (source[i] == '+' || source[i] == '–' || source[i] == '*' ||
source[i] == '/' || source[i] == '%')
{
while( (top!=–1) && (st[top]!= '(') && (getPriority(st[top])
> getPriority(source[i])))
{
target[j] = pop(st);
j++;
}
push(st, source[i]);
i++;
}
else
{
printf("\n INCORRECT ELEMENT IN EXPRESSION");
exit(1);
}
}
while((top!=–1) && (st[top]!='('))
{
target[j] = pop(st);
j++;
}
target[j]='\0';
}
int getPriority(char op)
{
if(op=='/' || op == '*' || op=='%')
return 1;
else if(op=='+' || op=='–')
return 0;
}
void push(char st[], char val)
{
if(top==MAX–1)
printf("\n STACK OVERFLOW");
else
{
top++;
st[top]=val;
}
}
char pop(char st[])
{
char val=' ';
if(top==–1)
printf("\n STACK UNDERFLOW");
else
{
val=st[top];
top––;
}
return val;
}
```

## Output

Enter any infix expression : A+B–CD

The corresponding postfix expression is : AB+CD