#include<iostream>
#include<stack>
#include "myStack.h"
#include <string>
#include "Node.h"
#include <cstring>
#include <sstream>
#include <vector>
//#include "valueStack.h"
using namespace std;

class PostfixConverter{
    string infix;
    string 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 == '/')
            return true;
        return false;
    }

    int getOperatorWeight(char c){
        int weight = -1;
        switch(c)
        {
            case '+': weight = 1;
                break;
            case '-': weight = 1;
                break;
            case '*': weight = 2;
                break;
            case '/': weight = 2;
                break;

        }
        return weight;
    }

    bool hasLowerOrEqualPrecedence(char op1, char op2){
        int op1Weight = getOperatorWeight(op1);
        int op2Weight = getOperatorWeight(op2);
        if(op1Weight <= op2Weight){
            return true;
        }
        else
            return false;
    }

    bool isOpeningParanthesis(char c){
        if(c == '(' )
            return true;
        return false;
    }


    bool isClosingParanthesis(char c){
        if(c == ')')
            return true;
        return false;
    }

    void displayPostfix(){
        cout<<"The equivalent postfix expression is: "<<postfix<<endl;
    }
    bool isMatchingParanthesis(char closing, char opening){

        if(opening == '(' && closing == ')') return true;

        return false;
    }


    //
    //
    //
    //    string add(string last, string first)
    //    {
    //        // Before proceeding further, make sure length
    //        // of str2 is larger.
    //        if (last.length() > first.length())
    //            swap(last, first);
    //
    //        // Take an empty string for storing result
    //        string str = "";
    //
    //        // Calculate lenght of both string
    //        int n1 = last.length(), n2 = first.length();
    //        int diff = n2 - n1;
    //
    //        // Initialy take carry zero
    //        int carry = 0;
    //
    //        // Traverse from end of both strings
    //        for (int i=n1-1; i>=0; i--)
    //        {
    //            // Do school mathematics, compute sum of
    //            // current digits and carry
    //            int sum = ((last[i]-'0') +
    //                       (first[i+diff]-'0') +
    //                       carry);
    //            str.push_back(sum%10 + '0');
    //            carry = sum/10;
    //        }
    //
    //        // Add remaining digits of str2[]
    //        for (int i=n2-n1-1; i>=0; i--)
    //        {
    //            int sum = ((first[i]-'0')+carry);
    //            str.push_back(sum%10 + '0');
    //            carry = sum/10;
    //        }
    //
    //        // Add remaining carry
    //        if (carry)
    //            str.push_back(carry+'0');
    //
    //        // reverse resultant string
    //        reverse(str.begin(), str.end());
    //
    //        return str;
    //    }
    //
    //
    //
    //    // Returns true if str1 is smaller than str2,
    //    // else false.
    //    bool isSmaller(string str1, string str2)
    //    {
    //        // Calculate lengths of both string
    //        int n1 = str1.length(), n2 = str2.length();
    //
    //        if (n1 < n2)
    //            return true;
    //        if (n2 > n1)
    //            return false;
    //
    //        for (int i=0; i<n1; i++)
    //        {
    //            if (str1[i] < str2[i])
    //                return true;
    //            else if (str1[i] > str2[i])
    //                return false;
    //        }
    //        return false;
    //    }
    //
    //    // Function for finding difference of larger numbers
    //    string subtract(string str2, string str1)
    //    {
    //        // Before proceeding further, make sure str1
    //        // is not smaller
    //        bool isFirstSmall=false;
    //        if (isSmaller(str1, str2)){
    //            swap(str1, str2);
    //            isFirstSmall=true;
    //
    //        }
    //
    //        // Take an empty string for storing result
    //        string str = "";
    //
    //        // Calculate lengths of both string
    //        int n1 = str1.length(), n2 = str2.length();
    //        int diff = n1 - n2;
    //
    //        // Initially take carry zero
    //        int carry = 0;
    //
    //        // Traverse from end of both strings
    //        for (int i=n2-1; i>=0; i--)
    //        {
    //            // Do school mathematics, compute difference of
    //            // current digits and carry
    //            int sub = ((str1[i+diff]-'0') -
    //                       (str2[i]-'0') -
    //                       carry);
    //            if (sub < 0)
    //            {
    //                sub = sub+10;
    //                carry = 1;
    //            }
    //            else
    //                carry = 0;
    //
    //            str.push_back(sub + '0');
    //        }
    //
    //        // subtract remaining digits of str1[]
    //        for (int i=n1-n2-1; i>=0; i--)
    //        {
    //            if (str1[i]=='0' && carry)
    //            {
    //                str.push_back('9');
    //                continue;
    //            }
    //            int sub = ((str1[i]-'0') - carry);
    //            if (i>0 || sub>0) // remove preceding 0's
    //                str.push_back(sub+'0');
    //            carry = 0;
    //
    //        }
    //
    //        // reverse resultant string
    //        reverse(str.begin(), str.end());
    //
    //        return "-"+str;
    //    }
    //
    //    // Multiplies str1 and str2, and prints result.
    //    string multiply(string num1, string num2)
    //    {
    //        int n1 = num1.size();
    //        int n2 = num2.size();
    //        if (n1 == 0 || n2 == 0)
    //            return "0";
    //
    //        // will keep the result number in vector
    //        // in reverse order
    //        vector<int> result(n1 + n2, 0);
    //
    //        // Below two indexes are used to find positions
    //        // in result.
    //        int i_n1 = 0;
    //        int i_n2 = 0;
    //
    //        // Go from right to left in num1
    //        for (int i=n1-1; i>=0; i--)
    //        {
    //            int carry = 0;
    //            int n1 = num1[i] - '0';
    //
    //            // To shift position to left after every
    //            // multiplication of a digit in num2
    //            i_n2 = 0;
    //
    //            // Go from right to left in num2
    //            for (int j=n2-1; j>=0; j--)
    //            {
    //                // Take current digit of second number
    //                int n2 = num2[j] - '0';
    //
    //                // Multiply with current digit of first number
    //                // and add result to previously stored result
    //                // at current position.
    //                int sum = n1*n2 + result[i_n1 + i_n2] + carry;
    //
    //                // Carry for next iteration
    //                carry = sum/10;
    //
    //                // Store result
    //                result[i_n1 + i_n2] = sum % 10;
    //
    //                i_n2++;
    //            }
    //
    //            // store carry in next cell
    //            if (carry > 0)
    //                result[i_n1 + i_n2] += carry;
    //
    //            // To shift position to left after every
    //            // multiplication of a digit in num1.
    //            i_n1++;
    //        }
    //
    //        // ignore '0's from the right
    //        int i = result.size() - 1;
    //        while (i>=0 && result[i] == 0)
    //            i--;
    //
    //        // If all were '0's - means either both or
    //        // one of num1 or num2 were '0'
    //        if (i == -1)
    //            return "0";
    //
    //        // generate the result string
    //        string s = "";
    //        while (i >= 0)
    //            s += std::to_string(result[i--]);
    //
    //        return s;
    //    }


    string trim(string a)   // for removing leading 0s
    {
        string res="";
        int i=0;

        while(a[i]=='0')
            i++;

        for(;i<a.size();i++)
            res+=a[i];

        return res;
    }

    string convertInt(int number)
    {
        stringstream ss;//create a stringstream
        ss << number;//add number to the stream
        return ss.str();//return a string with the contents of the stream
    }

    string add(string last,string first){
        int a= stoi(trim(first));
        int b= stoi(trim(last));

        int result=a+b;
        return convertInt(result);

    }

    string subtract(string last,string first){
        int a= stoi(trim(first));
        int b= stoi(trim(last));

        int result=a-b;
        return convertInt(result);

    }

    string multiply(string last,string first){
        int a= stoi(trim(first));
        int b= stoi(trim(last));

        int result=a*b;
        return convertInt(result);

    }

    string divide(string last,string first){
        int a= stoi(trim(first));
        int b= stoi(trim(last));

        int result=a/b;
        return convertInt(result);

    }




    bool isParanthesisBalanced(){
        myStack<char> s;

        for(int i=0;i<infix.length();++i){

            if(isOpeningParanthesis(infix[i]))
                s.push(infix[i]);
            else if(isClosingParanthesis(infix[i])){
                if(s.isEmpty() || !isMatchingParanthesis(infix[i],s.peek())){
                    return false;}
                s.pop();
            }
        }
        if(s.isEmpty())
            return true;
        return false;
    }

public:
    PostfixConverter(string infix){
        this->infix = infix;
        postfix = "";
    }

    void convert(){
        if(!isParanthesisBalanced()){
            cout<<"Typo! Paranthesis is not balanced in the infix expression"<<endl;
            return;
        }



        //stack<char> ops;
        myStack<char> ops;
        myStack<string> valueStack;
        myStack<char> operationStack;

        string operand;

        for(int i=0;i<infix.length();++i){
            // cout<<valueStack.peek()<<"\t"<<operationStack.peek()<<endl;


            if (!operationStack.isEmpty()) {
                if (operationStack.peek()=='+') {
                    valueStack.push(add(valueStack.pop()->val, valueStack.pop()->val));
                }
                else if (operationStack.peek()=='-'){
                    valueStack.push(subtract(valueStack.pop()->val, valueStack.pop()->val));
                }
                else if (operationStack.peek()=='*'){
                    valueStack.push(multiply(valueStack.pop()->val, valueStack.pop()->val));
                }

                operationStack.pop();
            }
            if(IsOperator(infix[i])){

                //                if (operand!="") {
                //                    postfix+=operand;
                //                    valueStack.push(operand);
                //
                //                    operand="";
                //
                //                }

                while(!ops.isEmpty() &&  !isOpeningParanthesis(ops.peek()) && hasLowerOrEqualPrecedence(infix[i],ops.peek())){
                    postfix+= ops.peek();
                    operationStack.push(ops.peek());
                    ops.pop();
                }
                ops.push(infix[i]);
            }
            else if(isOperand(infix[i])){
                postfix+=infix[i];
                valueStack.push(infix.substr(i,1));

                //operand+=infix.substr(i,1);

            }
            else if(isOpeningParanthesis(infix[i])){

                //                if (operand!="") {
                //                    postfix+=operand;
                //                    valueStack.push(operand);
                //
                //                    operand="";
                //
                //                }
                if (IsOperator(infix[i+1])) {
                    operand+=infix[i+1];

                }

                ops.push(infix[i]);
                i++;
            }

            else if(isClosingParanthesis(infix[i])){
                //                if (operand!="") {
                //                    postfix+=operand;
                //                    valueStack.push(operand);
                //
                //                    operand="";
                //
                //                }
                //
                while(!isOpeningParanthesis(ops.peek())){
                    postfix+= ops.peek();
                    operationStack.push(ops.peek());
                    ops.pop();
                }
                ops.pop();
            }
        }

        //        if (operand!="") {
        //            postfix+=operand;
        //            valueStack.push(operand);
        //            operand="";
        //        }

        while(!ops.isEmpty()){
            if (!operationStack.isEmpty()) {
                if (operationStack.peek()=='+') {
                    valueStack.push(add(valueStack.pop()->val, valueStack.pop()->val));
                }
                else if (operationStack.peek()=='-'){
                    valueStack.push(subtract(valueStack.pop()->val, valueStack.pop()->val));
                }
                else if (operationStack.peek()=='*'){
                    valueStack.push(multiply(valueStack.pop()->val, valueStack.pop()->val));
                }
                operationStack.pop();
            }


            postfix+=ops.peek();
            operationStack.push(ops.peek());
            ops.pop();


        }

        if (!operationStack.isEmpty()) {
            if (operationStack.peek()=='+') {
                valueStack.push(add(valueStack.pop()->val, valueStack.pop()->val));
            }
            else if (operationStack.peek()=='-'){
                valueStack.push(subtract(valueStack.pop()->val, valueStack.pop()->val));
            }
            else if (operationStack.peek()=='*'){
                valueStack.push(multiply(valueStack.pop()->val, valueStack.pop()->val));
            }
            operationStack.pop();
        }



        cout<<endl<<"Final Value Stack   "<<valueStack.pop()->val<<endl;
        //        cout<<endl<<"Operation Stack"<<endl;
        //
        //        while (!operationStack.isEmpty()) {
        //            cout<<operationStack.pop()->val<<"\t";
        //        }
        //
        //        cout<<endl<<"Value Stack"<<endl;
        //
        //        while (!valueStack.isEmpty()) {
        //            cout<<valueStack.pop()->val<<"\t";
        //        }


        displayPostfix();
    }
};

int main(){
    string expression;
    cout<<"Enter the infix expression: ";
    getline(cin,expression);
    PostfixConverter* postfixConverter = new PostfixConverter(expression);
    postfixConverter->convert();
    return 0;
}