Question

C++ program that can take in EITHER "infix" or "prefix" (NOT POSTFIX) and transforms it into the other one. Should use stack and have infixToPrefix and prefixToInfix functions with a simple main function for execution.

Answer 1

(*Note: Please up-vote. If any doubt, please let me know in the comments)

C++ CODE:

#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;

bool
isOperator (char x)
{
switch (x)
{
case '+':
case '-':
case '/':
case '*':
return true; //return true if character is an operator, false otherwise
}
return false;
}

int
precedence (char C) //To return precedence as an integer
{
if (C == '-' || C == '+')
return 1;
else if (C == '*' || C == '/')
return 2;
else if (C == '^')
return 3;
return 0;
}

string
infixToPrefix (string infix)
{
string prefix;
stack < char >s;
reverse (infix.begin (), infix.end ());

for (int i = 0; i < infix.length (); i++)
{
if (infix[i] == '(')
   {
   infix[i] = ')';
   }
else if (infix[i] == ')')
   {
   infix[i] = '(';
   }
}
for (int i = 0; i < infix.length (); i++)
{
if ((infix[i] >= 'a' && infix[i] <= 'z')
   || (infix[i] >= 'A' && infix[i] <= 'Z'))
   {
   prefix += infix[i];
   }
else if (infix[i] == '(')
   {
   s.push (infix[i]);
   }
else if (infix[i] == ')')
   {
   while ((s.top () != '(') && (!s.empty ()))
   {
   prefix += s.top ();
   s.pop ();
   }

   if (s.top () == '(')
   {
   s.pop ();
   }
   }
else if (isOperator (infix[i]))
   {
   if (s.empty ())
   {
   s.push (infix[i]);
   }
   else
   {
   if (precedence (infix[i]) > precedence (s.top ()))
       {
       s.push (infix[i]);
       }
   else if ((precedence (infix[i]) == precedence (s.top ()))
       && (infix[i] == '^'))
       {
       while ((precedence (infix[i]) == precedence (s.top ()))
           && (infix[i] == '^'))
       {
       prefix += s.top ();
       s.pop ();
       }
       s.push (infix[i]);
       }
   else if (precedence (infix[i]) == precedence (s.top ()))
       {
       s.push (infix[i]);
       }
   else
       {
       while ((!s.empty ())
           && (precedence (infix[i]) < precedence (s.top ())))
       {
       prefix += s.top ();
       s.pop ();
       }
       s.push (infix[i]);
       }
   }
   }
}

while (!s.empty ())
{
prefix += s.top ();
s.pop ();
}

reverse (prefix.begin (), prefix.end ());
return prefix;
}

string
prefixToInfix (string pre_exp)
{
stack < string > s;

  
int length = pre_exp.size ();

  
for (int i = length - 1; i >= 0; i--)
{

  
if (isOperator (pre_exp[i]))
   {

  
   string op1 = s.top ();
   s.pop ();
   string op2 = s.top ();
   s.pop ();

   // concatenate the operands from stack and the currently read operator
   string temp = "(" + op1 + pre_exp[i] + op2 + ")";

   // Push temp to stack
   s.push (temp);
   }

// when symbol is not any operator
else
   {

   // push the operand on stack
   s.push (string (1, pre_exp[i]));
   }
}

return s.top ();
}

int
main ()
{
//string pre = "*+A/BC-/ADE", inf = "(A+B/C)*(A/D-E)";
string pre, inf;
int choice;
cout << "Enter your choice (1 or 2): " << endl;
cout << "1. Convert Infix to Prefix" << endl << "2. Convert Prefix to Infix"
<< endl;
cin >> choice;
switch (choice)
{
case 1:
cout << "Enter an Infix Expression" << endl;
cin >> inf;
cout << "Prefix expression : " << infixToPrefix (inf) << endl;
break;
case 2:
cout << "Enter a Prefix Expression" << endl;
cin >> pre;
cout << "Infix expression : " << prefixToInfix (pre);
break;
}

return 0;
}

OUTPUT SCREENSHOTS: