Conversion of Infix string to Prefix in c++
Have tested this on only some weak test
cases, do tell me if it goes wrong somewhere

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

using namespace std;

bool precedence(string a, string b);
void infixToPrefix(string s);

int main()
{
        string s;
        cin>>s;

        infixToPrefix(s);

        return 0;
}
void infixToPrefix(string s)
{
        stack<string> operator1;        //operator stack
        stack<string> op;               //operand stack

        for(int i=0; i<s.size(); i++){
                string s6="";
                s6+=s[i];

                //token is an operand
                if(s[i]!='+' && s[i]!='-' && s[i]!='*' && s[i]!='/' && s[i]!='(' && s[i]!=')' && s[i]!='$'){
                        string s5;
                        s5=s[i];
                        op.push(s5);
                }else if(s[i]==')'){  //if right parentheses 
                 //continue to pop operator nd operand stack
                 //till left parentheses is found 
                        while(operator1.top()!="("){
                                string a=operator1.top();
                                operator1.pop();
                                string b=op.top();
                                op.pop();
                                string c=op.top();
                                op.pop();
                                string s2;
                                s2=a+c+b;
                                op.push(s2);
                        }
                        //pop the left parentheses
                        operator1.pop();


                }else if(s[i]=='(' || operator1.empty() || (!operator1.empty() && precedence(s6,operator1.top())) ){
                        string s5;
                        s5=s[i];
                        operator1.push(s5);
                }else{
                /*Continue to pop operator and 
                operand stack, building prefix
                expressions until the stack is empty or 
                until an operator at the
                top of the operator stack has a lower precedence
                than that of token */
                        while((!operator1.empty()) && !(precedence(s6, operator1.top()))){
                                string a=operator1.top();
                                operator1.pop();
                                string b=op.top();
                                op.pop();
                                string c=op.top();
                                op.pop();
                                string s2;
                                s2=a+c+b;
                                op.push(s2);
                        }
                        string s5="";
                        s5+=s[i];
                        operator1.push(s5);
                }

        }
        /*If the stack is not empty,
        continue to pop operator and operand stacks building
        prefix expressions until the operator stack is empty.*/
        while(!operator1.empty()){
                string a=operator1.top();
                operator1.pop();
                string b=op.top();
                op.pop();
                string c=op.top();
                op.pop();
                string s2;
                s2=a+c+b;
                op.push(s2);
        }

        while(!op.empty()){
                cout<<op.top()<<" ";
                op.pop();
        }
        cout<<endl;

}

// returns true if precedence of a is more than b
// else return false     
bool precedence(string a, string b)
{
        int aa=0;
        int bb=0;
        if(a=="("){
                return false;
        }else if(b=="("){
                return true;
        }else if(b==")"){
                return true;
        }else if(a==")"){
                printf("undefined operation\n");
                return 0;
        }

        if(a=="+" || a=="-") aa=1;
        if(a=="*" || a=="/") aa=2;
        if(b=="+" || b=="-") bb=1;
        if(b=="*" || b=="/") bb=2;
        if(a=="$") aa=3;
        if(b=="$") bb=3;
        if(aa > bb) return true;

        return false;
}
Advertisements