Postfix to Prefix Conversion using Stack in C++

Postfix to Prefix Conversion in C++

 

Prefix, Postfix and Infix are the different ways to write expressions as notations. In infix, they are normal notations as used by mathematical expressions in copies. In Prefix expression, the  operator is prefixed to operands, and in Postfix, or Reverse Polish Notation, the operator comes after the operands. In this article we will know how to perform Post fix expressions to prefix expressions converstion using a stack in C++.

 

Postfix to Prefix using Stack in C++

What is Postfix to Prefix?

Infix: (X + Y)

  • Postfix – The postfix will look like, XY+
  • Prefix: The prefix will look like, +YX

Infix : (X + Y) / (U – V)

  • Postfix – The postfix will look like, XY+UV-/
  • Prefix – The prefix will look like, /+XY-UV

Here we need to use a stack data structure. SInce we have our own inbuilt stack DS in C++ STL, we are going to use it. If you use want to know more about that : Stack in C++ STL 

Follow this algorithm to solve this problem.

There may be  many ways to find the post fix to prefix, here it goes one easy way to imlement an algorithm to do so.

  • Read the expression from left to right.
  • If there is any operand present, push it to a stack.
  • Then if you come accross an operator, pop two of the opearands from the stack and concatinate them like,
    the operator + 2nd top value of the stack + first top value of the stack.
  • Repeat the process.
  • Reverse the string at the end.

Fun fact: This can be interpreted as a binary tree if you can make a binary tree with operators and add the operands at last.

Visual Implementation of the Algorithm :

Suppose the expression in Infix is (X+Y)/(U-V), and in Postfix: XY+UV-/ 

Here all the iterations are shown below.

 

Iteration 1 :

Postfix to Prefix using Stack in C++1

Iteration 2 :

Postfix to Prefix using Stack in C++ 2

Iteration 3 :

Postfix to Prefix using Stack using c++ 3

Iteration 4 :

Postfix to Prefix using Stack in C++ 4

Iteration 5 :

Postfix to Prefix using Stack in C++ 5

Iteration 6 :

Postfix to Prefix using Stack in C++ 6

Iteration 7 :

Postfix to Prefix using Stack in C++ 7

End of the Iteration :

Postfix to Prefix using Stack in C++ 8

Final State :

Postfix to Prefix using Stack in C++ 9

The code to implement this:

#include<bits/stdc++.h>
using namespace std;

int IsOperator(char x)
{
switch (x) {
case '+':
case '-':
case '/':
case '*':
return 1;
}
return 0;
}


int main()
{
string s,c="";
cout<<"Enter the Postfix Expression: "<<endl;
cin>>s;
stack<char> st;
cout<<"The Prefix expression is: "<<endl;
for(int i=s.length()-1;i>=0;i--)
{
if(IsOperator(s[i]))
st.push(s[i]);
else{
c+=s[i];
while(!st.empty() && st.top()=='#')
{
st.pop();
c+=st.top();st.pop();
}
st.push('#');
}
}
reverse(c.begin(),c.end());
cout<<c;
}

Output:

Enter the Postfix Expression: 
XY+UV-/
The Prefix expression is:
/+XY-UV

If you want to see this code in C language: Postfix to Prefix Conversion using Stack in C 

Article is contributed by Rahit Saha