Postfix to Prefix Conversion in C++

By Sakshi Gupta

In this tutorial, we will learn Postfix to Prefix Conversion in C++.

Postfix: If the operator appears in the expression after the operands, then it is called a postfix expression. For example-

AB+CD-*

Prefix: If the operator appears in the expression before the operands, then it is called a prefix expression.

*+AB-CD

Infix: It is a normal regular expression with the correct order of operands and operators.

(A+B) * (C-D)

Postfix to Prefix Conversion in c++

We will first convert the expression from postfix to infix and then infix to the prefix. This will be easy to do for us.

Here is the dry run for it:

Here, is the code implementation:

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

  bool isOperator(char x)
   { if(x=='+'||x=='-'||x=='/'||x=='*') 
   return true;
    return false;
     } 

 string postToPre(string post_exp) 
 { stack<string> s;
   int lengthofstring = post_exp.size();
    for (int p = 0; p < lengthofstring; p++) {
     // check if symbol is operator
     if (isOperator(post_exp[p])) {
     // pop two operands from stack 
     string op1 = s.top();
    s.pop();
    string op2 = s.top();
     s.pop();
     // concat the operands and operator
    string temp = post_exp[p] + op2 + op1;
     // Push string temp back to stack
     s.push(temp); }
     // if symbol is an operand
     else { 
          // push the operand to the stack 
     s.push(string(1, post_exp[p])); } } //stack[0] contains the Prefix expression 
     return s.top(); 
} 

int main() 
{ string post_exp = "ABC/-AK/L-*"; 
cout << "Prefix : " << postToPre(post_exp); 
return 0;
 }

Output:

Prefix : *-A/BC-/AKL

Also, refer to:

Count the number of occurrences of an element in a linked list in C++

Thank you! Please comment for suggestions.