Conversion of Infix to Postfix Expression Program
in C Plus Plus
In this article we will explore the program of
converting Infix expression to Postfix Expression in the C++ programming
language.
The concept of conversion of Infix to Postfix expression
is related to the subject of data structure. Before we dive to explore the
program to convert infix to postfix expression a kind advice is to first
understand the concept of infix and postfix expression first.
Without the concept of infix and postfix expression,
It will be very difficult for you to understand the working of this program.
How this Program Works
There is no rocket science required to understand this
program.
All we have done is that we have simply transform the
algorithm of conversion of Infix to postfix expression in C++ programming language.
The algorithm to convert infix to postfix expression
is as under.
Algorithm to convert infix to postfix expression
POLISH(Q, P)
Suppose Q is an arithmetic expression written in infix
notation. This algorithm finds the equivalent postfix expression P.
1.
Push “(“ onto STACK, and add “)” to
the end of Q.
2.
Scan Q from left to right and repeat
Steps 3 to 6 for each element of Q until the STACK is empty.
3.
If an operand is encountered, add it
to P.
4.
If a left parenthesis is encountered,
push it onto STACK.
5.
If an operator is encountered, then:
a)
Repeatedly pop from STACK and add to
P each operator (on the top of STACK) which has the same precedence as or
higher precedence then previous operator.
b)
Add operator to STACK.
[End of If structure]
6.
If a right parenthesis is
encountered, then:
a)
Repeatedly pop from STACK and add to
P each operator (on the top of STACK) until a left parenthesis is encountered.
b)
Remove the left parenthesis. [Do not
add the left parenthesis to P.]
[End
of If structure.]
[End of Step 2 loop]
7.
Exit.
How this Program Behave
This program has very simple style of execution it
will ask the user to enter an Infix Expression and then it will process this
expression and will give the result as a postfix expression to the user.
Program to convert infix to postfix expression
//softoset.blogspot.com
#include<iostream>
#include<string.h>
using namespace std;
#define MAX 100
class Conversion{
private:
char
Exp[MAX];
char
Stack[MAX];
char
Post[MAX];
int
Top,stop;
int
i,j;
char
item,sent,ch,x;
public:
void in()
{
cout<<"Enter
the Infix Expression "<<endl;
gets(Exp);
}
void sentinel()
{
cout<<"\nEnter
Sentinel : ) Bracket at the End of
Expression "<<endl;
cin>>sent;
Top=strlen(Exp);
if(Top>=MAX)
{
cout<<"Overflow
"<<endl;
exit(1);
}
else
{
Exp[Top]=sent;
Top=Top+1;
}
cout<<"Now
";
}
void
scan()
{
stack_push('(');
i=0;
j=0;
while(i!=strlen(Exp))
{
ch=Exp[i];
if(ch=='(')
{
stack_push(ch);
}
else
if(isdigit(ch)||isalpha(ch))
{
Post[j]=ch;
j++;
}
else
if(isoperator(ch)==1)
{
x=stack_pop();
while(isoperator(x)==1&&precedence(x)>=precedence(ch))
{
cout<<"x
="<<x<<endl;
Post[j]=x;
j++;
x=stack_pop();
}
stack_push(x);
stack_push(ch);
}
else if(ch==')')
{
x=stack_pop();
while(x!='(')
{
Post[j]=x;
j++;
x=stack_pop();
}
}
i++;
}
}
int
isoperator(char op)
{
if((op=='+')||(op=='-')||(op=='*')||(op=='/')||(op=='^'))
return
1;
else
return
0;
}
int
precedence(char op)
{
if(op=='^')
return
(3);
else
if(op=='*'||op=='/')
return
(2);
else
if(op=='+'||op=='-')
return
(1);
else
return
0;
}
char
stack_pop()
{
if(stop<=0)
{
cout<<"Underflow
"<<endl;
exit(1);
}
else
{
item=Stack[stop];
stop=stop-1;
return
item;
}
}
void
stack_push(int item)
{
if(stop>=MAX)
{
cout<<"Overflow
"<<endl;
exit(1);
}
else
{
stop=stop+1;
Stack[stop]=item;
}
}
void
out()
{
cout<<"Expression
is "<<endl;
Top=strlen(Exp);
for(int
i=0;i<Top;i++)
cout<<Exp[i]<<"
";
}
void
Pout()
{
cout<<"Postfix
Expression is "<<endl;
stop=strlen(Exp);
for(int
i=0;i<stop;i++)
cout<<Post[i]<<"
";
}
};
int main()
{
Conversion
obj;
obj.in();
obj.out();
obj.sentinel();
obj.out();
obj.scan();
obj.Pout();
return
0;
}
Output of
Program to convert infix to postfix expression
And here is the result of this program on execution we
have capture it for you.
You can clearly see that when user entered an infix
expression, this program convert it to the postfix expression.
Thanks you.
Post a Comment
Feel Free to Comment Us