C++ | Infix expression to postfix expression

Hello peeps! Lord Hypersonic greets you. I am here with a new c++ program that can convert infix expression to postfix expression. Infix expression is the expression in which operators are between the two operands, like A+B, whereas postfix expressions are those expressions in which operators are written after operands, for e.g., AB+C-.

How this program works?

1. First, it creates a character stack with name "stck" and character stack with name "Y".
2. Then ask the user to input the infix expression. And then it adds "(" at the starting of expression and ")" at the end of the expression.
3. Now it starts the for loop from 0 to length of given infix expression.
4. If "stck" is empty then push ch (i.e., "(" )
5. If "ch" is a character/ operand then it will push ch to stack "Y.
6. After that, it checks the stack stck's top element, i.e., if the element's precedence is higher or equal to that of "ch" element, in this case, it moves the top element of "stck" to "Y" and push the "ch" in "stck".
If precedence if lower than "ch" then it will simply push the "ch" in "stck".
7. After the for loop, it copies top element of "Y" (postfix expression) at the back of the string "o" and after that pop the top elements of "Y" (o.push_back(Y.top() ).
8. Then it reverses the string "o" and obtain the postfix expression and print it.

What is the precedence order?
1. exponential operator (^) has highest precedence order.
2. Multiplication (*) and Division (/) operator has the same precedence order and are lower than the exponential operator.
3. Addition (+) and subtraction (-) operator has same precedence order and are lower than multiplication and division.

Source Code:-

/*

Program: Infix To Postfix

Description: This program can convert any given infix expression and convert it into Postfix expression.

Author: Lord Hypersonic

Website: www.lordhypersonic.blogspot.in

Email: lordhypersonic.522@gmail.com

*/

#include <iostream>
#include <string>
#include <stack>
#include <conio.h>

using namespace std;

int main()
{
stack<char> stck; //creating character stack.c
int len;
string exp;
while(true) //starting infinite loop
{
cout<<"\nEnter Infix expression: "; getline(cin,exp); int yL=exp.length(); //asking for Infix expression
string ex="("+exp+")"; //adding brackets at both the ends of expression.
len=ex.length();
stack<char> Y; char ch,a; //creating character stack Y.
for (int i=0; i<len; i++) //loop till end of the infix expression
{
ch=ex[i]; // value ch is equal to value of ex at index i
if(stck.empty()) // if stack stck is empty then puch ch in stck
{
stck.push(ch);
}
if (ch=='(') // if ch is equal to ( the puch it to stck
{
stck.push(ch);
}
else if((ch>=65 && ch<=90) || (ch>=97 && ch<=122) ||(ch>=48 && ch<=57)) // if ch is character like A,B,C,d,e,f etc. then push it to stack Y.
{
Y.push(ch);
}
else if(ch==')') //if ch is equal to )
{
while(true) //then pop operators from stck and push in Y until stck's top is (
{
if (stck.top()=='(') // if top element of stck is (
{
stck.pop(); //pop ( and end loop
break;
}
else
{
a=stck.top(); // copy value of top element of stck to a
Y.push(a); // then push it to Y
stck.pop(); // then pop the top element of stck
}
}
}
else if(ch=='^') //if ch is an exponential operator (it has highest precedence)
{
stck.push(ch); //then puch it to stck
}
// * and / both have same precedence
else if(ch=='*') //if ch is equal to * then
{
if (stck.top()=='/' || stck.top()=='*' || stck.top()=='^') // check for / * and ^
{
a=stck.top(); // copy top element's value of stack to a
Y.push(a); // push a in Y
stck.pop(); // pop the top element from stack
if (stck.top()=='/' || stck.top()=='*' || stck.top()=='^') // if next elements is from / * or ^ then repeat the above process
{
a=stck.top();
Y.push(a);
stck.pop();
}
}
stck.push(ch); //puch the ch to stck
}
else if (ch=='/') // if ch is equal to / then
{
if (stck.top()=='/' || stck.top()=='*' || stck.top()=='^') //check for top element of stck as / * or ^ then repeate the steps
/*

precedence order is

1. exponential operator (^)

2. Multiplication (*) and Division (/)

3. Addition(+) Subtraction (-)

*/
{
a=stck.top();
Y.push(a);
stck.pop();
if (stck.top()=='/' || stck.top()=='*' || stck.top()=='^')
{
a=stck.top();
Y.push(a);
stck.pop();
}
}
stck.push(ch);
}
else if (ch=='+')
{
if (stck.top()=='^' || stck.top()=='*' || stck.top()=='/' || stck.top()=='+' || stck.top()=='-')
{
a=stck.top();
Y.push(a);
stck.pop();
if (stck.top()=='^' || stck.top()=='*' || stck.top()=='/' || stck.top()=='+' || stck.top()=='-')
{
a=stck.top();
Y.push(a);
stck.pop();
}
}
stck.push(ch);
}
else if (ch=='-')
{
if (stck.top()=='^' || stck.top()=='*' || stck.top()=='/' || stck.top()=='+' || stck.top()=='-')
{
a=stck.top();
Y.push(a);
stck.pop();
if (stck.top()=='^' || stck.top()=='*' || stck.top()=='/' || stck.top()=='+' || stck.top()=='-')
{
a=stck.top();
Y.push(a);
stck.pop();
}
}
stck.push(ch);
}
}
string o;
while(!Y.empty()) // run the loop till Y is not empty
{
o.push_back(Y.top()); // copy top elements of Y to the end of string o
Y.pop(); // pop top element of Y
}
string output;
for(int i=o.length(); i>=0; i--) // loop for reverse the string
{
output.push_back(o[i]);
}
cout<<"\nEquivalent postfix expression is: "<<output; //printing output
cout<<endl;
_getch();
}
return 0;
}

Here is the working of the program:-