Stack: Postfix and prefix conversion

Postfix expression: AB+CD-*  is an postfix expression

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

Traverse the expression from left to right.

If the symbol operand symbol is an operand, push into the stack.

If the symbol is operator, then pop 2 operand form the stack.

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

Repeat the steps until the end of the expression.

Time Complexity: O(n)

Space Complexity: O(n)

#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 postfixToPrefix(string post_exp)
{
    stack<string> s;

    int length = post_exp.size();

    for (int i = 0; i < length; i++) 
    {

        if (check_if_is_Operator(post_exp[i])) 
        {

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

            string temp = post_exp[i] + op2 + op1;

            s.push(temp);
        }

        else 
        {

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

    string ans = "";

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

int main()
{
    string post_exp = "AB+CD-*";

    // Function call
    cout << "Prefix : " << postfixToPrefix(post_exp);
    return 0;
}

Output

Prefix : *+AB-CD