Postfix expression:The expression of the form a b op. When an operator is followed for every pair of operands.
Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
…..3.1 If the precedence of the scanned operator is greater than the precedence of the operator in the stack(or the stack is empty), push it.
…..3.2 Else, Pop the operator from the stack until the precedence of the scanned operator is less-equal to the precedence of the operator residing on the top of the stack. Push the scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop and output from the stack until an ‘(‘ is encountered.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.
Source Code
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#define size 20
char stack[size];
int top=-1;
void push(char x)
{
if(top>=(size-1))
{
printf("stack overflow and exit");
exit(0);
}
else
{
top=top+1;
stack[top]=x;
}
}
char pop()
{
int top_item;
if(top<0)
{
printf("stack underflow and exit");
exit(0);
}
else
{
top_item=stack[top];
top=top-1;
return top_item;
}
}
int check_operator(char x)
{
if(x=='^' || x=='*' || x=='/' || x=='+' || x=='-')
{
return 1;
}
else
{
return 0;
}
}
int precedence_operator(char x)
{
if(x=='^')
return 3;
else if(x=='*'||x=='/')
return 2;
else if(x=='+'||x=='-')
return 1;
else
return 0;
}
void infix_to_postfix(char infix_expn[],char postfix_expn[])
{
int i=0,j=0;
char infix_item,stack_item;
push('(');
strcat(infix_expn,")");
infix_item=infix_expn[i];
while(infix_item!='\0')
{
if(infix_item=='(')
{
push(infix_item);
}
else if((infix_item>='a'&& infix_item<='z')||(infix_item>='A'&& infix_item<='Z')||(infix_item>='0'&& infix_item>='9'))
{
postfix_expn[j]=infix_item;
j++;
}
else if(check_operator(infix_item)==1)
{
stack_item=pop();
while(check_operator(stack_item)==1 && precedence_operator(stack_item)>=precedence_operator(infix_item))
{
postfix_expn[j]=stack_item;
j++;
stack_item=pop();
}
push(stack_item);
push(infix_item);
}
else if(infix_item=')')
{
stack_item=pop();
while(stack_item!='(')
{
postfix_expn[j]=stack_item;
j++;
stack_item=pop();
}
}
else
{
printf("Invalid input ");
getchar();
exit(0);
}
i++;
infix_item=infix_expn[i];
}
if(top>0)
{
printf("Invalid infix expression");
getchar();
exit(0);
}
postfix_expn[j]='\0';
}
int main()
{
char infix[size],postfix[size];
printf("\nEnter infix expression:");
gets(infix);
infix_to_postfix(infix,postfix);
printf("\nPostfix expression :");
puts(postfix);
getch();
return 0;
}
