5.Infix And Prefix and Postfix Conversions

Infix to Postfix

Given an infix expression in the form of string str. Convert this infix expression to postfix expression.

• Infix expression: The expression of the form a op b. When an operator is in-between every pair of operands.

• Postfix expression: The expression of the form a b op. When an operator is followed for every pair of operands. Note: The order of precedence is: ^ greater than * equals to / greater than + equals to -.

Example 1:

Input: str = "a+b*(c^d-e)^(f+g*h)-i"
Output: abcd^e-fgh*+^*+i-
Explanation :
After converting the infix expression 
into postfix expression, the resultant 
expression will be abcd^e-fgh*+^*+i-

Example 2:

Input: str = "A*(B+C)/D"
Output : ABC+*D/
Explanation :
After converting the infix expression 
into postfix expression, the resultant 
expression will be ABC+*D/
 

Solution:

int prec(char ch)
{
    if (ch == '^')
    {
        return 3;
    }
    else if (ch == '*' || ch == '/')
    {
        return 2;
    }
    else if (ch == '-' || ch == '+')
    {
        return 1;
    }

    return -1;
}

string infixToPostfix(string s)
{
    // Your code here
    string res = "";
    stack<char> st;

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

        if (s[i] == '(' || s[i] == ')')
        {
            if (s[i] == '(')
            {
                st.push(s[i]);
            }
            else
            {

                while (!st.empty() && st.top() != '(')
                {
                    res += st.top();
                    st.pop();
                }
                
                st.pop();
            }
        }
        else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/' || s[i] == '^')
        {

            while (!st.empty() && prec(s[i]) <= prec(st.top()))
            {
                res += st.top();
                st.pop();
            }

            st.push(s[i]);
        }
        else
        {
            res += s[i];
        }
        
        
        
    }
    
    
    while(!st.empty()){
        res += st.top();
        st.pop();
    }

    return res;
}