#include <iostream>

#define EXPR_NUMBER_WEIGHT    3
#define EXPR_MUL_DIV_WEIGHT   2
#define EXPR_ADD_SUB_WEIGHT   1
#define EXPR_VARIABLE_WEIGHT  3
#define EXPR_BRACKET_WEIGHT   4

using namespace std;

typedef enum DataType {NIL = 0, INTEGER, FLOAT, VARIABLE, OPERATION};

///////////////////////////////////////////////////////////////////////////////

union DataVariant
{
    int    intData;
    float  floatData;
    char * variable;
    char   operation;
    long long longIntData;
};

///////////////////////////////////////////////////////////////////////////////

class UniData
{
    public:

    DataType type;
    unsigned int weight;
    union
    {
        int    intData;
        float  floatData;
        char * variable;
        char   operation;
        long long longIntData;
    };

    public:

    UniData()
    {
        type = NIL;
        weight = 0;
        memset(&intData, 0, sizeof(DataVariant));
    }

    UniData(DataType dt1, int dw1, int dd1)
    {
        type = dt1;
        weight = dw1;
        intData = dd1;
    }

    UniData(DataType dt1, int dw1, float dd1)
    {
        type = dt1;
        weight = dw1;
        floatData = dd1;
    }

    UniData(DataType dt1, int dw1, char od1)
    {
        type = dt1;
        weight = dw1;
        operation = od1;
    }

    UniData(DataType dt1, int dw1, char * dd1)
    {
        type = dt1;
        weight = dw1;
        variable = new char[strlen(dd1)+1];
        strcpy(variable, dd1);
    }

    ~UniData()
    {
        //if (variable && (type == VARIABLE))
        //    delete[] variable;
    }

    bool operator==(UniData & ud1)
    {
        if (type == ud1.type)
        {
            switch (type)
            {
                case INTEGER:
                    return intData == ud1.intData;
                case FLOAT:
                    return floatData == ud1.floatData;
                break;
                case OPERATION:
                    return operation == ud1.operation;
                break;
                case VARIABLE:
                    return !strcmp(variable, ud1.variable);
                break;
                default:
                    return false;
                break;
            }
        }
        else
            return false;
    }

    bool operator==(int id1)
    {
        return ((type == INTEGER) && (intData == id1));
    }

    bool operator==(float fd1)
    {
        return ((type == FLOAT) && (floatData == fd1));
    }

    char * GetAsStr(char * str)
    {
        switch(type)
        {
            case INTEGER:
                 sprintf(str, "%d", intData);
            break;
            case FLOAT:
                sprintf(str, "%.3f", floatData);
            break;
            case OPERATION:
                str[0] = operation;
            break;
            case VARIABLE:
                strcpy(str, variable);
            break;
            default:
            break;
        }
        return str;
    }

};

///////////////////////////////////////////////////////////////////////////////

template <class Type>

class RingLink
{
////////////////////////////////////////////////////////////////////////////////

protected:

    RingLink * next;
    Type value;
    int position;

////////////////////////////////////////////////////////////////////////////////

public:

    RingLink()
    {
        next     = this;
        value    = 0;
        position = 0;
    }

    RingLink(int p1)
    {
        next     = this;
        position = p1;
    }

    RingLink(Type v1, int p1)
    {
        next     = this;
        value    = v1;
        position = p1;
    }

    ////////////////////////////////////////////////////////////////////////////

    Type & GetValue()
    {
        return value;
    }

    void SetValue(Type p1)
    {
        value = p1;
    }

    int GetPos()
    {
        return position;
    }

    void SetPos(int p1)
    {
        position = p1;
    }

    RingLink * GetNext()
    {
        return next;
    }

    RingLink * SetNext(RingLink * p1)
    {
        next = p1;
        return p1;
    }

    RingLink * Add(RingLink * p1)
    {
        p1->next = next;
        next = p1;
        return p1;
    }

    void RemoveNext()
    {
        RingLink * rem = next;
        next = next->next;
        delete rem;
    }

};

////////////////////////////////////////////////////////////////////////////////

template <class Type>

class VirtualArray
{

protected:

    RingLink< Type > * ring;
    int linkCount;
    int maxLinkCount;

    RingLink< Type > * CreateLink(int pos)
    {
        linkCount++;
        return new RingLink< Type >(pos);
    }

    void RemoveNextLink(RingLink< Type > * link)
    {
        linkCount--;
        link->RemoveNext();
    }

public:

    VirtualArray()
    {
        ring = NULL;
        linkCount = 0;
        maxLinkCount = 0;
    }

    int GetLenght()
    {
        return linkCount;
    }

    Type & operator[](int pos)
    {
        RingLink< Type > * curr = ring, * prev = NULL;

        if (ring)
        {
            do
            {

                if (curr->GetPos() == pos)
                    return curr->GetValue();

                prev = curr;
                curr = curr->GetNext();

                if (curr->GetValue() == 0)
                {
                    if (curr != ring)
                    {
                        RemoveNextLink(prev);
                        curr = prev->GetNext();
                    }
                    else
                    {
                        RemoveNextLink(prev);
                        curr = prev->GetNext();
                        ring = curr;
                    }
                }
            }
            while (curr != ring);

            return ring->Add(CreateLink(pos))->GetValue();
        }
        else
        {
            ring = CreateLink(pos);
            return ring->GetValue();
        }
    }


    void Clear()
    {
        if (ring)
        {
            RingLink< Type > * curr = ring->GetNext(), * prev = NULL;

            while (curr != ring)
            {
                prev = curr;
                curr = (curr->GetNext());
                delete prev;
            }

            linkCount = 0;
            delete ring;
            ring = NULL;
        }
    }

    void Shift(int p1, int m1 = 0)
    {
        RingLink< Type > * curr = ring;
        int sc = 0;

        if (m1 && (m1 < linkCount))
            m1 = linkCount;

        do
        {
            if (m1 && ((curr->GetPos() + p1) >= m1))
                curr->SetPos(sc++);
            else
                curr->SetPos(curr->GetPos() + p1);
            curr = curr->GetNext();
        }
        while (curr != ring);
    }

    void Print()
    {
        RingLink< Type > * curr = NULL;
        if (ring)
        {
            curr = ring->GetNext();
            cout << "[" << ring->GetValue();
            while (curr != ring)
            {
                cout << ", " << curr->GetValue();
                curr = curr->GetNext();
            }
            cout << "]" << endl;
        }
    }
};

///////////////////////////////////////////////////////////////////////////////

template< class Type >
class Node
{
    protected:
public:
    Type data;

    Node * up;
    Node * left;
    Node * right;



    public:

    Node()
    {
        up     = NULL;
        left   = NULL;
        right  = NULL;
    }

    Node(Type d1)
    {
        data   = d1;
        up     = NULL;
        left   = NULL;
        right  = NULL;
    }

    Node(Node & n1)
    {
        data = n1.data;
        up     = NULL;
        left   = NULL;
        right  = NULL;
    }

    Node * Add(Node * nn)
    {
//        char str[16];
//        memset(str, 0, 16);
//        cout << " | " << nn->data.GetAsStr(str) << " | ";
        if (nn->data.weight < data.weight)
        {
            if (up)
                return up->Add(nn);
            else
            {
                nn->Add(this);
                return nn;
            }
        } else
        if (nn->data.weight == data.weight)
        {
            if (up)
                return up->Add(nn);
            else
            {
                unsigned int oldWeight = nn->data.weight;
                nn->data.weight = data.weight-1;
                nn->Add(this);
                nn->data.weight = oldWeight;
                return nn;
            }
        } else
        {
            if (left)
            {
                if (right)
                {
//                    cout << endl;
//                    Top()->Print();

                    right->up = NULL;
                    nn->Add(right);
//                    cout << endl;
////
////                    nn->Top()->Print();
                    right = nn->Top();
                    nn->Top()->up = this;


//                    cout << endl;
//
//                    Top()->Print();
                    return right;
                }
                else
                {
                    nn->up = this;
                    right = nn;
                    return right;
                }
            }
            else
            {
                nn->up = this;
                left = nn;
                return left;
            }
        }
    }

    Node * Top()
    {
        if (up)
            return up->Top();
        else
            return this;
    }

    Node * Delete()
    {
        if (left)
        {
            left->Delete();
            delete left;
            left = NULL;
        }
        if (right)
        {
            right->Delete();
            delete right;
            right = NULL;
        }
        if (up)
        {
            if (up->left == this)
            {
                Node * ln = up->right->left;
                Node * rn = up->right->right;
                * up = * up->right;
                up->left  = ln;
                up->right = rn;
//                    up->left = NULL;
            }
            if (up->right == this)
            {
//                Node * ln = up->left->left;
//                up->right = up->right->right;
//                * up = * up->left;
//                up->left = ln;
                Node * ln = up->left->left;
                Node * rn = up->left->right;
                * up = * up->left;
                up->left  = ln;
                up->right = rn;
            }
            return NULL;

        }
        return this;
    }

//    Node * Cut()
//    {
//        if (up)
//        {
//            Node * son = NULL;
//            son = (left ? left : (right ? right : NULL));
//
//            if (up->left == this)
//            {
//                up->left = son;
//            } else
//            if (up->right == this)
//            {
//                Node * ln = up->left->left;
//                Node * rn = up->right->right
//                * up = * up->left;
//                up->left  = ln;
//                up->right = rn;
//            }
//        }
//        return this;
//    }

    void Print(int lev = 0, unsigned int br0 = 0)
    {
        char str[16];
        memset(str, 0, 16);


        unsigned int br1 = (unsigned int) data.weight / EXPR_BRACKET_WEIGHT;

        if (left && right)
            for (unsigned int j=0; j<br1-br0; j++)
                cout << "(";

        if (left)
            left->Print(lev+1, br1);

        cout << data.GetAsStr(str);// << lev << ": " << endl;


        if (right)
            right->Print(lev+1, br1);

        if (left && right)
            for (unsigned int j=0; j<br1-br0; j++)
                cout << ")";

        //getchar();
        //br0 = br1;
    }

    bool operator==(Node & nn)
    {
//        char str[16];
//        memset(str, 0, 16);
//        cout << endl << data.GetAsStr(str);
//        memset(str, 0, 16);
//        if (left) cout << " | " << left->data.GetAsStr(str);
//        memset(str, 0, 16);
//        if (right) cout << " | " << right->data.GetAsStr(str);

        bool rez = true;
        rez = rez && (data==nn.data);
////        if (!rez) cout << 1 << endl;
        rez = rez && ((left && nn.left) ? (* left)==(* nn.left) : left==nn.left);
//        if (!rez) cout << 2 << endl;
        rez = rez && ((right && nn.right) ? (* right)==(* nn.right) : right==nn.right);
//        if (!rez) cout << 3 << endl;
        return rez;
    }

    Node & operator=(Node & nn)
    {
        data = nn.data;
        return (* this);
    }

    Node * Find(Node * sn)
    {
        if ((* this) == (* sn))
        {
            return this;
        }
        else
        {
            Node * fn = NULL;
            if (left)
                fn = left->Find(sn);
            if (fn)
                return (fn);
            if (right)
                fn = right->Find(sn);
            if (fn)
                return (fn);
        }
        return NULL;
    }

    bool Conversion(Node * rn, Node * * nn)
    {

        if ((data.type == OPERATION) && (data.operation == '*'))
        {
            if (left)
            {
                if (left->Conversion(rn, nn))
                {
                    delete left;
                    left = NULL;
                }
            }
            if (right)
            {
                if (right->Conversion(rn, nn))
                {
                    delete right;
                    right = NULL;
                }
            }

        }
        if (!((data.type == OPERATION) && (data.operation == '*')))
        {
            Node * fn = NULL;
            fn = rn->Find(this);
            if (fn)
            {
                UniData ud1(OPERATION, EXPR_MUL_DIV_WEIGHT, '*');
                * nn =  (new Node(ud1))->Add((* nn)->Top());

                data.weight %= EXPR_BRACKET_WEIGHT;
                * nn = (* nn)->Add(new Node(* this));

                if (fn->Delete())
                    delete fn;

                return Delete()!=NULL;
            }
        }
        return false;
    }

    void AddWeight(unsigned int w1)
    {
        data.weight += w1;
        if (left)
            left->AddWeight(w1);
        if (right)
            right->AddWeight(w1);
    }

    Node * Rehash()
    {
        if ((data.type == OPERATION) && (data.operation == '-') && left && right)
        {
            if ((left->data.type == OPERATION) && (right->data.type == OPERATION) && (left->data.operation == '*') && (right->data.operation == '*'))
            {
                AddWeight(EXPR_BRACKET_WEIGHT);
                Node * np = this;
                if (left->Conversion(right, &np))
                {
                    delete left;
                    left = NULL;
                }
                // data.weight += EXPR_BRACKET_WEIGHT;
                return this;
            }
        }
        return NULL;

//        if (left)
//            left->Rehash();
//        if (right)
//            right->Rehash();
    }

};

///////////////////////////////////////////////////////////////////////////////

typedef enum ParserState { PS_START, PS_NUMBER, PS_OPERATION, PS_STRING };

class Expression
{
    protected:

    VirtualArray< UniData > subjects;
    unsigned int subjQty;
public:
    Node< UniData > * tree;

    public:

    Expression()
    {
        subjQty = 0;
    }

    void AddNumber(char * nstr1, unsigned int nw1)
    {
        float rnum = .0;
        sscanf(nstr1, "%f", &rnum);
        UniData ud1(FLOAT, nw1 + EXPR_NUMBER_WEIGHT, rnum);
        subjects[subjQty++] = ud1;
    }

    void AddOperation(char op1, unsigned int nw1)
    {
        unsigned int adw = 0;
        if ((op1 == '+') || (op1 == '-'))
        {
            adw = EXPR_ADD_SUB_WEIGHT;
        } else
        if ((op1 == '*') || (op1 == '/'))
        {
            adw = EXPR_MUL_DIV_WEIGHT;
        }
        UniData ud1(OPERATION, nw1 + adw, op1);
        subjects[subjQty++] = ud1;
    }

    void AddVariable(char * var1, unsigned int nw1)
    {
        UniData ud1(VARIABLE, nw1 + EXPR_VARIABLE_WEIGHT, var1);
        subjects[subjQty++] = ud1;

    }

    void ParseStr(char * estr1)
    {
        unsigned int step = 0;
        ParserState state = PS_START;
        subjects.Clear();
        subjQty = 0;
        char buff[256] = "";
        unsigned int subjlen = 0;
        unsigned int weight = 0;
        char cch = 0;

        do
        {
            cch = estr1[step];

            if (cch == ' ')
            {
                step++;
                continue;
            }

            switch (state)
            {

                case PS_START:

                    if (((cch >= '0') && (cch <= '9')) || (cch == '.'))
                    {
                            state = PS_NUMBER;
                    } else
                    if ((cch == '+') || (cch == '-') || (cch == '*') || (cch == '/'))
                    {
                        state = PS_OPERATION;
                    } else
                    if (((cch >= 'A') && (cch <= 'Z')) || ((cch >= 'a') && (cch <= 'z')) || (cch == '_'))
                    {
                        state = PS_STRING;
                    } else
                    if (cch == '(')
                    {
                        weight += EXPR_BRACKET_WEIGHT;
                        step++;
                    } else
                    if (cch == ')')
                    {
                        weight -= EXPR_BRACKET_WEIGHT;
                        step++;
                    }

                break;

                case PS_NUMBER:

                    if (((cch >= '0') && (cch <= '9')) || (cch == '.'))
                    {
                        buff[subjlen++] = cch;
                        step++;
                    }
                    else
                    {
                        buff[subjlen] = 0;
                        subjlen = 0;
                        AddNumber(buff, weight);
                        state = PS_START;
                    }

                break;

                case PS_OPERATION:

                    AddOperation(cch, weight);
                    state = PS_START;
                    step++;

                break;

                case PS_STRING:

                    if (((cch >= 'A') && (cch <= 'Z')) || ((cch >= 'a') && (cch <= 'z')) || (cch == '_'))
                    {
                        buff[subjlen++] = cch;
                        step++;
                    }
                    else
                    {
                        buff[subjlen] = 0;
                        subjlen = 0;
                        AddVariable(buff, weight);
                        state = PS_START;
                    }

                break;
            }
        }
        while (cch);
    }

    void Print()
    {
        unsigned int br1 = 0, br0 = 0;

        for (unsigned int i=0; i<subjQty; i++)
        {
            br1 = (unsigned int) subjects[i].weight / EXPR_BRACKET_WEIGHT;
            for (unsigned int j=br0; j<br1; j++)
                cout << "(";
            for (unsigned int j=br1; j<br0; j++)
                cout << ")";
            br0 = br1;

            switch (subjects[i].type)
            {
                case INTEGER:
                    cout << subjects[i].intData;
                break;
                case FLOAT:
                    cout << subjects[i].floatData;
                break;
                case OPERATION:
                    cout << subjects[i].operation;
                break;
                case VARIABLE:
                    cout << subjects[i].variable;
                break;
            }
        }
    }

    void MakeTree()
    {
        tree = new Node< UniData >(subjects[0]);
        for (unsigned int i=1; i<subjQty; i++)
        {
            char str[16];
            memset(str, 0, 16);
            tree = tree->Add(new Node< UniData >(subjects[i]));
            tree->Top()->Print();
            cout << endl;
        }
        tree = tree->Top();
    }

    void PrintTree()
    {
        tree->Print();
    }

    bool operator==(Expression & ex1)
    {
        return (* tree) == (* ex1.tree);
    }

};

///////////////////////////////////////////////////////////////////////////////

int main()
{
    char input[] = "(a*f*c*e*h-h*d*a*c)";
    Expression expr1;
    expr1.ParseStr(input);
    expr1.MakeTree();
    cout << "Original expression: " << endl;
    expr1.PrintTree();
    expr1.tree = (expr1.tree->Rehash())->Top();
    cout << endl << "Changed expression: " << endl;
    expr1.PrintTree();
    getchar();
    return 0;
}