Given two operands
and 
and an operator 
, the infix notation implies that O will be placed in between a and b i.e 
. When the operator is placed after both operands i.e 
, it is called postfix notation. And when the operator is placed before the operands i.e 
, the expression in prefix notation.
Algorithm:
Step 1. Push “)” onto STACK, and add “(“ to end of the A
Step 2. mScan A from right to left and repeat
step 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 right parenthesis is encountered push it onto STACK
Step 5. If an operator is encountered then:
a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same or higher precedence than the operator.
b. Add operator to STACK
Step 6. If left parenthesis is encontered then
a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left parenthesis is encounterd)
b. Remove the left parenthesis
Step 7. Exit
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_prefix(char infix_expn[],char prefix_expn[])
{
int i=0,j=0;
char infix_item,stack_item;
push(')');
strrev(infix_expn);
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'))
{
prefix_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))
{
prefix_expn[j]=stack_item;
j++;
stack_item=pop();
}
push(stack_item);
push(infix_item);
}
else if(infix_item='(')
{
stack_item=pop();
while(stack_item!=')')
{
prefix_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);
}
prefix_expn[j]='\0';
}
int main()
{
char infix[size],prefix[size];
printf("\nEnter infix expression:");
gets(infix);
infix_to_prefix(infix,prefix);
strrev(prefix);
printf("\nPostfix expression :");
puts(prefix);
getch();
return 0;
}