#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef enum { _none, _plus, _minus, _mul, _dig, _lt, _gt, _pow, _end } Lexem;

Lexem currentLexem;
int currentPos;
char *expr;

typedef struct pNode
{
        char sign[5];
        Lexem operator;
        struct pNode* left;
        struct pNode* right;
} Node;

void print_lexem(Lexem l)
{
        switch(l)
        {
                case _lt: printf("("); break;
                case _gt: printf(")"); break;
                case _plus: printf("+"); break;
                case _minus: printf("-"); break;
                case _mul: printf("*"); break;
                case _pow: printf("^"); break;
                case _end: printf("\n"); break;
        }
}

Node* expression();
Node* sum();
Node* mul_pow();
Node* mul();

void next_lexem()
{
        currentPos++;
        switch(expr[currentPos])
        {
                case '(': currentLexem = _lt; break;
                case ')': currentLexem = _gt; break;
                case '+': currentLexem = _plus; break;
                case '-': currentLexem = _minus; break;
                case '*': currentLexem = _mul; break;
                case '^': currentLexem = _pow; break;
                case '\0': currentLexem = _end; break;
                default: currentLexem = _dig; break;
        }
}


Node* expression()
{
        Node* child = sum();
        Node* res;
        if(currentLexem == _plus || currentLexem == _minus)
        {
                res = malloc(sizeof(Node));
                res->left = child;
                res->operator = currentLexem;
                next_lexem();
                res->right = expression();
        }
        else
        {
                res = child;
        }
        return res;
}

Node* sum()
{
        Node* child = mul_pow();
        Node* res;
        if(currentLexem == _mul)
        {
                res = malloc(sizeof(Node));
                res->left = child;
                res->operator = currentLexem;
                next_lexem();
                res->right = sum();
        }
        else
        {
                res = child;
        }
        return res;
}

Node* mul_pow()
{
        Node* child = mul();
        Node* res;
        if(currentLexem == _pow)
        {
                res = malloc(sizeof(Node));
                res->left = child;
                res->operator = currentLexem;
                next_lexem();
                res->right = mul();
        }
        else
        {
                res = child;
        }
        return res;
}

Node* mul()
{
        Node* res;
        if(currentLexem == _lt)
        {
                next_lexem();
                res = expression();
                next_lexem();
        }
        else
        {
                if(currentLexem == _dig)
                {
                        res = malloc(sizeof(Node));
                        res->operator = currentLexem;
                        int i = 0;
                        while(currentLexem == _dig)
                        {
                                res->sign[i++] = expr[currentPos];
                                next_lexem();
                        }
                        res->sign[i] = '\0';
                }
        }
        return res;
}

void parse_tree(Node *n)
{
        if(n->operator == _pow &&
                n->left->operator == _minus &&
                n->right->operator == _dig &&
                !strcmp(n->right->sign,"2"))
        {
                Node *n1 = malloc(sizeof(Node));
                Node *n2 = malloc(sizeof(Node));
                Node *n3 = malloc(sizeof(Node));
                Node *n4 = malloc(sizeof(Node));
                Node *n5 = malloc(sizeof(Node));
                Node *n6 = malloc(sizeof(Node));

                Node *a = n->left->left;
                Node *b = n->left->right;

                n1->sign[0] = '2'; n1->sign[1] =  '\0'; n1->operator = _dig;
                n2->left = a; n2->right = n1; n2->operator = _pow;
                n3->left = n1; n3->right = a; n3->operator = _mul;
                n4->left = n3; n4->right = b; n4->operator = _mul;
                n5->left = n2; n5->right = n4; n5->operator = _minus;
                n6->left = b; n6->right = n1; n6->operator = _pow;
                n->left = n5; n->right = n6; n->operator = _plus;
        }
        if(n->operator != _dig)
        {
                parse_tree(n->left);
                parse_tree(n->right);
        }
}

void print_tree(Node *n)
{
        if(n->operator == _dig)
        {
                printf("%s", n->sign);
        }
        else
        {
                if(n->left->operator != _dig) print_lexem(_lt);
                print_tree(n->left);
                if(n->left->operator != _dig) print_lexem(_gt);
                print_lexem(n->operator);
                if(n->right->operator != _dig) print_lexem(_lt);
                print_tree(n->right);
                if(n->right->operator != _dig) print_lexem(_gt);
        }
}

int main()
{
        expr = "2";
        currentPos = -1;
        next_lexem();
        Node *root, *new_root;
        root = expression();
        parse_tree(root);
        print_tree(root);
        printf("\n");
        return 0;
}