Stack: Prefix to postfix conversion

Problem Statement:

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

Postfix expression: AB+CD-*

Solution Explanation:

Read the prefix expression from right to left.

If the symbol is operand, push into the stack

If the symbol is operator, then pop 2 operands and create a string with “operand1 + operand2 + operator ” and push back to the stack.

Repeat the steps till the end of the 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 '*':
        return true;
    }
    return false;
}

string prefixToPostfix(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 + op2 + pre_exp[i];

            s.push(temp);
        }

        else 
        {

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

    return s.top();
}

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

Output

Postfix : AB+CD-*