DS - HW#3

#include <iostream>


using namespace std;



class myStack
{
public:
    int top;
    char *stack_array;
    int stack_size;

    myStack(int stack_size)
    {
       this->top = -1;
       this->stack_array = new char[stack_size];
       this->stack_size = stack_size;

    }

    ~myStack()
    {
        delete [] this->stack_array;
    }


    void push(char item)
    {
        if((top+1) >= this->stack_size)
        { cout<<"Stack Overflow\n";
            return;}

        stack_array[++this->top] = item;

    }

    char pop()
    {
        return (stack_array[this->top--]);

    }

    char peek()
    {
        return (stack_array[this->top]);
    }

    bool isEmpty()
    {
        return (this->top < 0);
    }


};



class myStack_float
{
public:
    int top;
    float *stack_array;
    int stack_size;

    myStack_float(int stack_size)
    {
       this->top = -1;
       this->stack_array = new float[stack_size];
       this->stack_size = stack_size;

    }

    ~myStack_float()
    {
        delete [] this->stack_array;
    }


    void push(float item)
    {
        if((top+1) >= this->stack_size)
        { cout<<"Stack Overflow\n";
            return;}

        stack_array[++this->top] = item;

    }

    float pop()
    {
        return (stack_array[this->top--]);

    }

    float peek()
    {
        return (stack_array[this->top]);
    }

    bool isEmpty()
    {
        return (this->top < 0);
    }


};



bool isNumber(char value)
{
    switch(value)
    {
        case '0': case '1': case '2': case '3': case '4':
        case '5': case '6': case '7': case '8': case '9':
        return true;
        break;
        default :
            return false;
    }
}

bool isOperator(char value)
{
    switch(value)
    {
        case '+': case '-': case '*': case '/':
        return true;
        break;
        default :
            return false;
    }
}

int OperatorsWeight(char value)
{
    switch(value)
    {
        case '+': case '-':
        return 1;
        case '*': case '/':
        return 2;
        default:
        return 0;
    }
}



string reverse_exp(string exp)
{
    string temp = exp;


    for(int i=exp.size()-1 , j=0 ; i>=0 ; i-- , j++)
        temp[j] = exp[i];


    return temp;

}


string infix_to_prefix(string exp)
{
    exp = reverse_exp(exp); // inverse of experssion

    myStack postfix(50);
    string temp = "";

    for(int i=0 ; i<exp.size(); i++)
    {
        if(isNumber(exp[i])) // Number
        {
            temp +=exp[i];

        }else if(isOperator(exp[i])) // + - * /
        {
            if(postfix.isEmpty())
            {
                postfix.push(exp[i]);
            }
            else if(OperatorsWeight(exp[i]) >= OperatorsWeight(postfix.peek())) // prefix condition
            {
                postfix.push(exp[i]);
            }
            else
            {
                while(OperatorsWeight(exp[i]) < OperatorsWeight(postfix.peek())) // prefix condition
                    {temp +=postfix.pop();}

                postfix.push(exp[i]);
            }

        }else if(exp[i] == ')') /// )   inverse ( to )
                 {
                     postfix.push(exp[i]);
                 }

         else if(exp[i] == '(') /// ( inverse ) to (
         {
             while(postfix.peek() != ')')
               {temp += postfix.pop();}

               postfix.pop();

         }


    }


    while(!postfix.isEmpty()) /// Pop the rest of stack
        {temp +=postfix.pop();}

        return reverse_exp(temp); /// revere the result
}


int char_to_int(char c)
{
    return int(c) - 48; /// 48 is ASCII Code of 0
}

float prefix_evaluation(string postfix)
{

    myStack_float values(30);

    for(int i=postfix.size()-1 ; i>=0; i--) // reverse the traversing
    {

        if(isNumber(postfix[i]))
        {
            values.push(char_to_int(postfix[i]));
        }
        else if(isOperator(postfix[i]))
        {
            float value1 = values.pop();
            float value2 = values.pop();
           /// here change order ==> value1 (op) value2 instead of value2 (op) value1
            if(postfix[i] == '+') values.push(value1 + value2) ;
            if(postfix[i] == '-') values.push(value1 - value2) ;
            if(postfix[i] == '*') values.push(value1 * value2) ;
            if(postfix[i] == '/') values.push(value1 / value2) ;


        }
    }



    return values.pop();
}



int main()
{


    string exp;


    cout<<"Please Enter Expression ==> ";
    cin>>exp;
    cout<<infix_to_prefix(exp)<<endl;
    cout<<prefix_evaluation(infix_to_prefix(exp));




    return 0;
}