Data Structures - Infix to Postfix Conversion - Cpp

In this post we convert an infix expression to postfix expression using stack data structure .

Generally an infix expression is a normal expression where operators are present in between the operands ex : A + B * C and  its postfix  notation is represented as ABC*+

An infix expression is converted into its postfix notation as follows : Create an empty Stack for pushing and poping operators and a string for storing result First scan the infix exppression from left to right if there is no exponential operator , if there is an exponential operator scan the infix expression from right to left. If an operand is encountered add it to the result string If a left parenthesis is encountered push it to the stack If a right parenthesis is encountered pop the stack until its corresponding left parenthesis is removed and append each operator to the result string   If an operator is encountered push it to the stack if the encountered operator is of lower precedence that the stack top element and pop all elements with higher or equal precedence and add to result string. Check if there are any elements in the stack and pop them out and add to the result string.

Download code

PROGRAM :

    #include<iostream>
    #include<stack>
    #include<string>

    using namespace std;
    string InfixToPostfix(string expression);
    int HasHigherPrecedence(char operator1, char operator2);
    bool IsOperator(char C);
    bool IsOperand(char C);

    int main()
    {
        string expression;
        cout<<"Enter Infix Expression: \t";
        getline(cin,expression);
        string postfix = InfixToPostfix(expression);
        cout<<"Postfix expression = \t"<<postfix<<"\n";
        return 0;
    }
    string InfixToPostfix(string expression)
    {

        stack<char> S;
        string postfix = "";
        for(int i = 0; i< expression.length(); i++)
        {
        if(expression[i] == ' ' || expression[i] == ',')
            continue;
        else if(IsOperator(expression[i]))
        {
            while(!S.empty() && S.top() != '(' && HasHigherPrecedence(S.top(),expression[i]))
            {
                postfix+= S.top();
                S.pop();
            }
            S.push(expression[i]);
        }
        else if(IsOperand(expression[i]))
        {
            postfix +=expression[i];
        }

        else if (expression[i] == '(')
        {
            S.push(expression[i]);
        }

        else if(expression[i] == ')')
        {
            while(!S.empty() && S.top() !=  '(')
            {
                postfix += S.top();
                S.pop();
            }
            S.pop();
        }
        }

        while(!S.empty())
        {
        postfix += S.top();
        S.pop();
        }

        return postfix;
    }
    bool IsOperand(char C)
    {
        if(C >= '0' && C <= '9') return true;
        if(C >= 'a' && C <= 'z') return true;
        if(C >= 'A' && C <= 'Z') return true;
        return false;
    }
    bool IsOperator(char C)
    {
        if(C == '+' || C == '-' || C == '*' || C == '/' || C== '^')
        return true;
        return false;
    }
    int IsRightAssociative(char op)
    {
        if(op == '^')
        return true;
        return false;
    }
    bool IsLeftParenthesis(char ch)
    {
        if (ch == '(')
        return true;
        return false;
    }
    bool IsRightParenthesis(char ch)
    {
        if (ch == ')')
        return true;
        return false;
    }
    int GetOperatorWeight(char op)
    {
        int weight = -1;
        switch(op)
        {
        case '+':
        case '-':
        weight = 1;
        break;
        case '*':
        case '/':
        weight = 2;
        break;
        case '^':
        weight = 3;
        break;
        }
        return weight;
    }
    int HasHigherPrecedence(char op1, char op2)
    {
        int op1Weight = GetOperatorWeight(op1);
        int op2Weight = GetOperatorWeight(op2);
        if(op1Weight == op2Weight)
        {
        if(IsRightAssociative(op1))
            return false;
        else
            return true;
        }
        return op1Weight > op2Weight ?  true: false;
    }

Download code

OUTPUT :

Cpp - Data Structures - Infix to Postfix 

Cpp - Data Structures - Infix to Postfix 

Cpp - Data Structures - Infix to Postfix