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

#define SIZE_INPUT 1024
#define SIZE_STR 40

typedef struct node{
    char data[SIZE_STR];
    struct node *left;
    struct node *right;
} node;

void check_tree(node* tree);
node* zip_multip(node* tree);
node* add_multip(node* tree);
node* add_node(char* dt, node* l, node* r);
int priority(char c);
node* make_tree(char* expr, int first, int last);
void print_tree(node* tree, int lrc);
node* zip_tree(node* tree);
int check_int(char* str);
void tree_to_expr(node* tree, int priority_node);
void int2str(int n, char* s);
void reverse_t(char* s);
int check_variable(char* str);
int node_coount = 0, int_count = 0;


int zip_array[50];
int zip_count = 0, add_element = 1, entr = 0;

int main(int argc, char* argv[]){
    char input[SIZE_INPUT];
    node* tree;
    node* tree_s;

    printf("Input expression: ");
    fgets(input, SIZE_INPUT-2, stdin);
    input[strlen(input)-1] = 0;
    printf("-----------------------\n");
    tree = make_tree(input, 0, strlen(input)-1);
    print_tree(tree, 0);
    printf("-----------------------\n");
    tree = zip_tree(tree);
    check_tree(tree);
    while (tree != tree_s) {
        tree_s = tree;
        int_count = 0;
        check_tree(tree);
        if (int_count > 0) tree = zip_multip(tree);
    }
    tree = add_multip(tree);
    print_tree(tree, 0);
    printf("-----------------------\n");
    tree_to_expr(tree, 1);
    printf("\n\n");

    return 0;
}

node* add_node(char *dt, node* l, node* r){
    node* add = (node*)malloc(sizeof(node));
    strcpy(add->data, dt);
    add->left = l;
    add->right = r;
    node_coount++;
    printf("%d\n", node_coount);
    return add;
}

int priority(char c){
    switch(c){
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 3;
    }
}

node* make_tree(char* expr, int first, int last){
    int minprt = 3, nest = 0, i, k, prt;
    char temp[SIZE_STR];

    if(first == last){
        temp[0] = expr[first];
        temp[1] = 0;
        return add_node(temp, 0, 0);
    }
    for(i = first; i<=last; i++){
        if(expr[i] == '(') {nest++; continue;}
        if(expr[i] == ')') {nest--; continue;}
        if(nest>0) continue;
        prt = priority(expr[i]);
        if(prt <= minprt) {minprt = prt; k = i;}
    }
    if(minprt == 3){
        if((expr[first] == '(') && (expr[last] == ')'))
            return make_tree(expr, first+1, last-1);
        else {
            k = last-first+1;
            strncpy(temp, expr+first, k);
            temp[k] = 0;
            return add_node(temp, 0, 0);
        }
    }
    temp[0] = expr[k];
    temp[1] = 0;
    return add_node(temp, make_tree(expr, first, k-1), make_tree(expr, k+1, last));
}

void print_tree(node* tree, int lrc){
    static int level = 0;
    int i;

    level++;
    if (tree){
        print_tree(tree->right, 2);
        for (i = 0; i<level; i++) printf("  ");
        if(lrc == 1) printf("\\_%s\n", tree->data);
        else if (lrc == 2) printf("__%s\n", tree->data);
        else printf("_%s\n", tree->data);
        print_tree(tree->left, 1);
    }
    level--;
}

void check_tree(node* tree)
{
    if (tree) {
        if (check_int(tree->data)) {
            int_count++;
        }
        check_tree(tree->left);
        check_tree(tree->right);
    }
}

node* zip_multip(node* tree)
{
    zip_count++;
    entr++;
    printf("zc=%d\n", entr);
    char temp[SIZE_STR];
    if (!strcmp(tree->data, "*") && int_count > 1) {
        if (check_variable(tree->right->data) && check_int(tree->left->data)) {
            add_element *= atoi(tree->left->data);
            printf("tree->left->data = %d, el = %d\n %s\n", atoi(tree->left->data), add_element, tree->right->data);
            zip_multip(tree->left);
           /* zip_multip(tree->right);*/
            tree->left = 0;
            strcpy(tree, tree->right);
            tree->right = 0;

        }
        else if (check_variable(tree->left->data) && check_int(tree->right->data)) {
            add_element *= atoi(tree->right->data);
            printf("tree->right->data = %d, el = %d\n %s\n", atoi(tree->right->data), add_element, tree->left->data);
           /* zip_multip(tree->right);*/
            zip_multip(tree->left);
            tree->right = 0;
            strcpy(tree, tree->left);
            tree->left = 0;

        }
         else if (tree->right) {
            zip_multip(tree->left);

        }
        else if (tree->left) zip_multip(tree->left);
    }
    return tree;
}

node* add_multip(node* tree)
{
    if (zip_count == 1) return tree;
    char temp[SIZE_STR];
    if (!strcmp(tree->data, "*") && check_int(tree->right->data)) {
        printf("add_multip = %d, add-el = %d \n", atoi(tree->right->data), add_element);
        int2str(atoi(tree->right->data)*add_element, temp);
        strcpy(tree->right->data, temp);
        printf("add_multip = %d\n", atoi(tree->right->data));
        return tree;
    }
    else if (!strcmp(tree->data, "*") && check_variable(tree->right->data)) {
        tree = add_multip(tree->left);
    }
    return tree;
}

node* zip_tree(node* tree){
    char temp[SIZE_STR];
    node *zip_node;
    if(tree){
        if(!check_int(tree->data)){
            tree->left = zip_tree(tree->left);
            tree->right = zip_tree(tree->right);
        }
        if(!strcmp(tree->data, "*")){
            if(check_int(tree->left->data) && check_int(tree->right->data)){
                int2str(atoi(tree->left->data)*atoi(tree->right->data), temp); //itoa нет на лаб.компах
                strcpy(tree->data, temp);
                tree->left = 0;
                tree->right = 0;
            }
            /*else if ((check_int(tree->left->data) && check_variable(tree->right->data)) || (check_int(tree->right->data) && check_variable(tree->left->data))) {
                zip_multip(tree);
            }*/
        }
    }
    return tree;
}

int check_int(char* str){
    int i;
    for(i = 0; i<strlen(str); i++) if(!(str[i]>='0' && str[i]<='9')) return 0;
    return 1;
}

int check_variable(char* str)
{
    int i;
    printf("zz\n");
    for(i = 0; i <strlen(str); i++) if(!isalpha(str[i])) return 0;
    printf("xx\n");
    return 1;
}

void tree_to_expr(node* tree, int priority_node){
    if(priority_node == 2) printf("(");
    if(tree->left) {
        if(!tree->left->left && !tree->left->right) tree_to_expr(tree->left, 1);
        else tree_to_expr(tree->left, priority(tree->data[0]));
    }
    printf("%s", tree->data);
    if(tree->right) {
        if(!tree->right->left && !tree->right->right) tree_to_expr(tree->right, 1);
        else tree_to_expr(tree->right, priority(tree->data[0]));
    }
    if(priority_node == 2) printf(")");
}

void int2str(int n, char* s){
    int i, sign;
    if((sign = n) < 0) n = -n;
    i = 0;
    do {
        s[i++] = n % 10 + '0';
    } while ((n /= 10) > 0);
    if (sign < 0) s[i++] = '-';
    s[i] = '\0';
    reverse_t(s);
}

void reverse_t(char* s){
    int i, j;
    char c;
    for (i = 0, j = strlen(s)-1; i<j; i++, j--) {
        c = s[i];
        s[i] = s[j];
        s[j] = c;
    }
}