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

typedef struct node {
    char data;
    struct node *left, *right;
} node;

node* create_node(char data)
{
    node *n = malloc(sizeof(node));
    if (!n)
    {
        printf("Greska pri alokaciji!\n");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->left = NULL;
    n->right = NULL;
    return n;
}

int is_operand(char ch)  { return ch >= '0' && ch <= '9'; }
int is_operator(char ch) { return ch == '+' || ch == '-' || ch == '*' || ch == '/'; }

void free_tree(node **root)
{
    if (root == NULL || *root == NULL) return;
    free_tree(&(*root)->left);
    free_tree(&(*root)->right);
    free(*root);
    *root = NULL;
}

void skip_spaces(char **s)
{
    while (**s == ' ') (*s)++;
}

/* Cita jedan potpuno zagradjen izraz. Vraca NULL ako je izraz neispravan. */
node* parse(char **s)
{
    skip_spaces(s);

    /* cifra -> list */
    if (is_operand(**s))
        return create_node(*(*s)++);

    /* ( izraz operator izraz ) */
    if (**s == '(')
    {
        (*s)++;

        node *left = parse(s);
        if (!left) return NULL;

        skip_spaces(s);
        if (!is_operator(**s))
        {
            free_tree(&left);
            return NULL;
        }
        node *op = create_node(*(*s)++);
        op->left = left;

        op->right = parse(s);
        if (!op->right)
        {
            free_tree(&op);
            return NULL;
        }

        skip_spaces(s);
        if (**s != ')')
        {
            free_tree(&op);
            return NULL;
        }
        (*s)++;
        return op;
    }

    return NULL;
}

/* *error se postavlja na 1 pri deljenju nulom */
double calculate_tree(node *tree, int *error)
{
    if (tree == NULL) { *error = 1; return 0; }

    if (is_operand(tree->data))
        return tree->data - '0';

    double l = calculate_tree(tree->left, error);
    double r = calculate_tree(tree->right, error);

    switch (tree->data)
    {
    case '+': return l + r;
    case '-': return l - r;
    case '*': return l * r;
    case '/':
        if (r == 0) { *error = 1; return 0; }
        return l / r;
    }
    *error = 1;
    return 0;
}

void print_tree(node *tree, int level)
{
    if (tree == NULL) return;
    print_tree(tree->right, level + 1);
    for (int i = 0; i < level; i++) printf("    ");
    printf("%c\n", tree->data);
    print_tree(tree->left, level + 1);
}

int main()
{
    char expression[] = "((3+((9/3)+1))*((8*7)-5))";
    char *p = expression;

    node *tree = parse(&p);
    skip_spaces(&p);

    /* izraz mora biti uspesno procitan do kraja stringa */
    if (tree == NULL || *p != '\0')
    {
        printf("Neispravan izraz!\n");
        free_tree(&tree);
        return EXIT_FAILURE;
    }

    printf("\n");
    print_tree(tree, 0);

    int error = 0;
    double result = calculate_tree(tree, &error);
    if (error)
        printf("Greska pri racunanju (deljenje nulom)!\n");
    else
        printf("Rezultat izraza je: %g\n", result);

    free_tree(&tree);
    return 0;
}