Find Your Solution Here

Data Structure

Infix expression to prefix notation conversion in c/c++ using queue

Description:

Given an infix expression with +,-, *, /, [] and (), convert it into prefix notation.

Solution:

#include<bits/stdc++.h>

using namespace std;
bool IsOperand(char C)
{
    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 == '/' )
        return true;

    return false;
}
int GetOperatorPrecedence(char op)
{
    if(op=='+'||op=='-')
        return 1;
    if(op=='*'||op=='/')
        return 2;
}

bool Precedence(char op1, char op2)
{
    if(GetOperatorPrecedence(op1)>=GetOperatorPrecedence(op2))
        return true;
    return false;
}


void prefix(char P[])
{
    stack<char> st;
    char Q[100];
    int j=0;
    for(int i = strlen(P); i>=0; i--)
    {
        if(IsOperator(P[i]))
        {
            while(!st.empty() && st.top() != ')' && Precedence(st.top(),P[i]))
            {
                if(st.top()!=')')
                Q[j++]= st.top();
                st.pop();
            }
            st.push(P[i]);
        }
        else if(IsOperand(P[i]))
        {
            Q[j++]=P[i];
        }

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

        else if(P[i] == ')')
        {
            while(st.top() !=  ')')
            {
                Q[j++]= st.top();
                st.pop();
            }
            st.pop();
        }
    }

    while(!st.empty())
    {
        if(st.top()!=')')
        Q[j++]= st.top();
        st.pop();
    }
    for(int i=strlen(Q);i>=0;i--){
        cout<<Q[i];
    }
    cout<<endl;

}


int main()
{
    char P[100];
    cin>>P;
    prefix(P);

Leave a Reply