Stack: Prefix to infix conversion

Problem Statement:

Prefix expression: *+AB-CD is a prefix expression.

Infix expression: ((A+B)*(C-D)) is an Infix expression

Solution Explanation:

Traverse the expression from right to left.

If the symbol is operand, push into the stack
If the symbol is operator, pop 2 operand from the stack.

Create a string as “(operand1 + operator + operand2) ” and push into the stack.

Repeat till the end of the prefix expression.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

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

bool check_if_is_Operator(char x) 
{
  switch (x) {
  case '+':
  case '-':
  case '/':
  case '*':
  case '^':
  case '%':
    return true;
  }
  return false;
}

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

  int length = pre_exp.size();

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

    if (check_if_is_Operator(pre_exp[i])) 
    {

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

      string temp = "(" + op1 + pre_exp[i] + op2 + ")";

      s.push(temp);
    }

    else 
    {

      s.push(string(1, pre_exp[i]));
    }
  }

  return s.top();
}

int main() 
{
  string pre_exp = "*+AB-CD";
  cout << "Infix : " << prefixToInfix(pre_exp);
  return 0;
}

Output

Infix : ((A+B)*(C-D))