Stack: Convert Infix to Postfix Expression

Infix expression: a + b is a infix expression.

Postfix expression: ab+ is an postfix expression

A * (B + C)/D

ABC+*D/

We use stack DS to solve the problem

Traverse the expression from left to right

1. If character is an operand, put in the postfix expression.

2. Else

If the precedence of the current operator is higher than the precedence of the operator on top of the stack or the stack is empty or stack has “(” then push the operator onto the stack.

Else

pop all the operator from the stack that has a precedence heigher or equal to that of the current operator.

3. If the scanned character is “(” push into the stack

4. If the scanned character is “)” pop the stack until a “(” is encountered and discard both the parameters.

5. Repeat 1 to 4 till the infix is scadded.

6. Once the scanning is over, pop the stack and add the operators and print the postfix expression

Time Complexity: O(n)

Space Complexity: O(n)

#include <iostream>
using namespace std;

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

string infixToPostfix(string s) 
{
    stack<char> st;
    string res;

    for (int i = 0; i < s.length(); i++) 
    {
        char c = s[i];

        if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || (c >= '0' && c <= '9'))
            res += c;

        else if (c == '(')
            st.push('(');

        else if (c == ')') 
        {
            while (st.top() != '(') 
            {
                res += st.top();
                st.pop();
            }
            st.pop(); 
        }

        else 
        {
            while (!st.empty() && precedence(c) <= precedence(st.top())) {
                res += st.top();
                st.pop();
            }
            st.push(c);
        }
    }

    while (!st.empty()) 
    {
        res += st.top();
        st.pop();
    }

    return res;
}

int main() 
{
    string exp = "A*(B+C)/D";
    cout << infixToPostfix(exp);
    return 0;
}

Output

ABC+*D/