tree_formula_simplification

#include <iostream>
using namespace std;

struct TTree
{
    char inf;
    TTree* left;
    TTree* right;
};

struct TStack
{
    TTree* inf;
    TStack* next;
};

bool isEmpty(TStack* s)
{
    return s==NULL;
}

void push(TStack* &s, TTree* newValue)
{
    if(isEmpty(s))
    {
        TStack* newElem = new TStack;
        newElem->inf = newValue;
        newElem->next = s;
        s = newElem;
    }
    else
        if(s->inf!=newValue)
        {
            TStack* newElem = new TStack;
            newElem->inf = newValue;
            newElem->next = s;
            s = newElem;
        }
}

TTree* pop(TStack* &s)
{
    TTree* retValue;
    TStack* prev;
    if(!isEmpty(s))
    {
        retValue = s->inf;
        prev = s;
        s = s->next;
        delete prev;
        return retValue;
    }
    else
        return NULL;
}

bool znak(char c)
{
    return ((c=='-')||(c=='+')||(c=='*')||(c=='/'));
}

int priority(char c)
{
    switch(c)
    {
        case '!':
            return 4;
        case '*':
        case '/':
        case '%':
            return 3;
        case '+':
        case '-':
            return 2;
        case '=':
            return 1;
    }
    return 0;
}

bool opLeftAssoc(char c)
{
    return c!='!';
}

void createTreeFromInfix(TTree* &root, string str)
{
    TStack* stack1 = NULL;
    TStack* stack2 = NULL;
    for(unsigned int i=0;i<str.size();i++)
    {
        TTree* PRoot  = new TTree;
        TTree* PRoot1 = new TTree;
        if(isalnum(str[i]))
        {
            PRoot->inf = str[i];
            PRoot->left = NULL;
            PRoot->right = NULL;
            push(stack1, PRoot);
        }
        if(str[i]=='(')
        {
            PRoot->inf = str[i];
            PRoot->left = NULL;
            PRoot->right = NULL;
            push(stack2, PRoot);
        }
        if(znak(str[i]))
        {
            while(!isEmpty(stack2))
            {
                TTree* PRoot8 = new TTree;
                if(((opLeftAssoc(str[i]))&&(priority(str[i]))<=priority(stack2->inf->inf)))
                {
                    PRoot8->inf   = pop(stack2)->inf;
                    PRoot8->right = pop(stack1);
                    PRoot8->left  = pop(stack1);
                    push(stack1, PRoot8);
                }else
                    break;
            }
            PRoot1->inf = str[i];
            PRoot1->left = NULL;
            PRoot1->right = NULL;
            push(stack2, PRoot1);
        }
        if(str[i]==')')
        {
            while(stack2->inf->inf!='(')
            {
                TTree* PRoot5 = new TTree;
                PRoot5->inf   = pop(stack2)->inf;
                PRoot5->right = pop(stack1);
                PRoot5->left  = pop(stack1);
                push(stack1, PRoot5);
            }
            pop(stack2);
        }
    }
    while(!isEmpty(stack2))
    {
        TTree* PRoot3 = new TTree;
        PRoot3->inf   = pop(stack2)->inf;
        PRoot3->right = pop(stack1);
        PRoot3->left  = pop(stack1);
        push(stack1, PRoot3);
    }
    root = pop(stack1);
}

void printTreeGraph(TTree* root, int level)
{
    if(root)
    {
        printTreeGraph(root->right, level+2);
        for(int i=0;i<level;i++)
            cout<<" ";
        cout<<root->inf<<endl;
        printTreeGraph(root->left, level+2);
    }
}

void printTree(TTree* root)
{
    if(root)
    {
        printTree(root->right);
        printTree(root->left);
        cout<<root->inf<<" ";
    }
}


void Task(TTree* &root)
{
    if(root)//если жерево непусто
        if((root->left)&&(root->right)) //и у него есть потомки
        {
            if(isalnum(root->left->inf)&&(isalnum(root->right->inf)))//проверяем что оба потомка операнды
            {
                if((root->left->inf=='0')||(root->right->inf=='0'))//если один из потомков 0
                {
                    if((root->inf=='-')||(root->inf=='+'))//и оператор + или -
                    {
                        if(root->left->inf=='0')//а зависимости от того с какой стороны 0
                        {
                            root->inf = root->right->inf;//берем ненулевое значение и кладем его вместо оператора
                            delete root->right;//чистим за собой память
                            delete root->left;
                            root->right = NULL;//присваиваем потомка NULL
                            root->left = NULL;
                        }else
                        {
                            root->inf = root->left->inf;
                            delete root->right;
                            delete root->left;
                            root->right = NULL;
                            root->left = NULL;
                        }

                    }else
                        if(root->inf=='*')
                        {
                            root->inf = '0';
                            delete root->left;
                            delete root->right;
                            root->right = NULL;
                            root->left = NULL;
                        }
                }else
                    if((root->left->inf=='1')||(root->right->inf=='1'))
                        if(root->inf=='*')
                        {
                            if(root->left->inf=='1')
                            {
                                root->inf = root->right->inf;
                                delete root->left;
                                delete root->right;
                                root->left = NULL;
                                root->right = NULL;
                            }else
                            {
                                root->inf = root->left->inf;
                                delete root->left;
                                delete root->right;
                                root->left = NULL;
                                root->right = NULL;
                            }
                        }
            }
            Task(root->left);
            Task(root->right);
        }
}

int calculate(TTree* root)
{
    if((root->left)&&(root->right))
    {
        if(root->inf=='+')
            return calculate(root->left)+calculate(root->right);
        if(root->inf=='-')
            return calculate(root->left)-calculate(root->right);
        if(root->inf=='*')
            return calculate(root->left)*calculate(root->right);
        if(root->inf=='/')
            return calculate(root->left)/calculate(root->right);
    }
    return root->inf - '0';
}

int main()
{
    setlocale(0,"Russian");
    string s;
    cin>>s;
    TTree* tree = NULL;
    createTreeFromInfix(tree, s);
    printTreeGraph(tree,1);
    cout<<endl<<endl;
    printTree(tree);
    cout<<endl<<calculate(tree)<<endl;
    Task(tree);
    printTreeGraph(tree,1);
    printTree(tree);
    return 0;
}