Infix to Postfix conversion
//A C++ program to convert an infix expression to postfix expression by Abhi Agarwal
#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<process.h>
char infix[50]; //It will store the infix expression the user enters
char stack[100]; //For storing intermediate results
char exp[50]; //It will store the postfix expression.
int top_stack,top_exp; //top_stack holds the index of the top of the stack[] and //top_exp holds the index of the top of exp[].
void accept()
{
int i;
cout<<"Expression can contain +,-,/,%,*,()";
cout<<"Enter the infix expression...";
cin>>infix;
i=strlen(infix);
*(infix+i)='#';
cout<<infix;
}
int precedence(char s)//function to find the precedence of operators
{
switch(s)
{
case '+':
return 2;
case '-':
return 2;
case '*':
return 1;
case '/':
return 1;
case '%':
return 1;
default:
return 0;
}
}
void postfix()
{
int i=0,n,k;
top_stack++;
*(stack+top_stack)='(';
while(1)
{
if(*(infix+i)=='(')
{
top_stack++;
*(stack+top_stack)='(';
}
else if(*(infix+i)=='+'||*(infix+i)=='-'||*(infix+i)=='/'||*(infix+i)=='*'||*(infix+i)=='%')
{
n=precedence(*(infix+i));
k=precedence(*(stack+top_stack));
if(k<n)
{
top_stack++;
*(stack+top_stack)=*(infix+i);
}
else
{
while(n<k)
{
top_exp++;
*(exp+top_exp)=*(stack+top_stack);
top_stack--;
k=precedence(*(stack+top_stack));
}
if(n==k||n>k)
{
top_stack++;
*(stack+top_stack)=*(infix+i);
}
}
}
else if(*(infix+i)==')')
{
while(*(stack+top_stack)!='(')
{
top_exp++;
*(exp+top_exp)=*(stack+top_stack);
top_stack--;
}
top_stack--;
}
else if(*(infix+i)=='#')
{
while(*(stack+top_stack)!='(')
{
top_exp++;
*(exp+top_exp)=*(stack+top_stack);
top_stack--;
}
break;
}
else
{
top_exp++;
*(exp+top_exp)=*(infix+i);
}
i++;
}
}
void display()
{
cout<<"Postfix expresion is....\n";
cout<<exp;
}
void main()
{
clrscr();//used to clear the screen
top_stack=-1;
top_exp=-1;
accept();//function call to accept the infix expression
postfix();//function to convert the infix into postfix expression
display();//display the postfix expression
getch();//function to hold the output screen
}
Comments
Post a Comment
If you have any Advice/Comments/Suggestion. Please let me know.