#include "expr.h"
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdio.h>

#define ISPMO(x) (((x) == '+') || ((x) == '-'))
#define ISMDO(x) (((x) == '*') || ((x) == '/'))
#define ISO(x)   (ISPMO(x) || ISMDO (x))
#define ISDIG(x) (isdigit(x) || ((x) == '.'))

extern int global_scale;

char *substr(const char *source, int start, int end)
{
    char *res = malloc(sizeof(char) * (end - start + 1));
    for (int i = 0; i < end - start; ++i) {
        res[i] = source[i + start];
    }
    res[end - start] = '\0';
    return res;
}

void pre_process(char *source)
{
    for (int i = 0; i < strlen(source); ++i) {
        if (source[i] == ' ' || source[i] == '\t') {
            for (int j = i; j < strlen(source); ++j) {
                source[j] = source[j + 1];
            }
            --i;
        }
    }
}

expr_node *parse_expr(const char *source)
{
    expr_node *head;
    int brackets = 0;
    int allnums = 1;
    int occur1 = -1, occur2 = -1;
    int out_of_bracket_once = 0;
    for (int i = (int)strlen(source) - 1; i >= 0; --i) {
        if (!ISDIG(source[i])) {
            if (i != 0 || (i == 0 && !ISPMO(source[i]))) {
                allnums = 0;
            }
            if (ISPMO(source[i]) && !brackets) {
                if (i != 0 && ISO(source[i - 1])) {
                    continue;
                } else {
                    occur1 = i;
                    break;
                }
            } else if (ISMDO(source[i]) && !brackets && occur2 == -1) {
                occur2 = i;
            } else if (source[i] == ')') {
                ++brackets;
            } else if (source[i] == '(') {
                --brackets;
            }
        }
        if ((i < (int)strlen(source) - 1) && (i > 0) && !brackets) {
            out_of_bracket_once = 1;
        }
    }

    if (!out_of_bracket_once && occur1 == -1 && !allnums) {
        char *middle = substr(source, 1, (int)strlen(source) - 1);
        head = parse_expr(middle);
        free(middle);
        return head;
    }

    char *left;
    char *right;
    if (allnums) {
        head = malloc(sizeof(expr_node));
        head -> type = EXPR_NUMBER;
        head -> left_child = NULL;
        head -> right_child = NULL;
        head -> value = atoreal((const char*)source);
    } else if (occur1 > 0) {
        head = malloc(sizeof(expr_node));
        head -> type = source[occur1] == '+' ? EXPR_PLUS : EXPR_MINUS;
        left = substr(source, 0, occur1);
        right = substr(source, occur1 + 1, (int)strlen(source));
        head -> left_child = parse_expr((const char*)left);
        head -> right_child = parse_expr((const char*)right);
        free(left);
        free(right);
    } else if (occur2 > 0) {
        head = malloc(sizeof(expr_node));
        head -> type = source[occur2] == '*' ? EXPR_MUL : EXPR_DIV;
        left = substr(source, 0, occur2);
        right = substr(source, occur2 + 1, (int)strlen(source));
        head -> left_child = parse_expr((const char*)left);
        head -> right_child = parse_expr((const char*)right);
        free(left);
        free(right);
    }

    return head;
}

lrealn cal_expr(expr_node *source)
{
    switch (source -> type) {
        case EXPR_NUMBER:
            return source -> value;
        case EXPR_PLUS:
            return add_real(cal_expr(source -> left_child), cal_expr(source -> right_child));
        case EXPR_MINUS:
            return minus_real(cal_expr(source -> left_child), cal_expr(source -> right_child));
        case EXPR_MUL:
            return multi_real(cal_expr(source -> left_child), cal_expr(source -> right_child));
        case EXPR_DIV:
            return div_real(cal_expr(source -> left_child), cal_expr(source -> right_child));
        default:
            return zeroreal();
            break;
    }
}

void delete_expr_tree(expr_node *item)
{
    if (item == NULL) {
        return;
    } else if (item -> type == EXPR_NUMBER) {
        free(item);
    } else {
        delete_expr_tree(item -> left_child);
        delete_expr_tree(item -> right_child);
        free(item);
    }
}

lrealn add_real(lrealn v1, lrealn v2)
{
    lrealn res;
    if (v1.scale == v2.scale) {
        res.scale = v1.scale;
        res.value = v1.value + v2.value;
    } else if (v1.scale > v2.scale) {
        while (v1.scale > v2.scale) {
            ++v2.scale;
            v2.value *= 10;
        }
        res.scale = v1.scale;
        res.value = v1.value + v2.value;
    } else {
        while (v1.scale < v2.scale) {
            ++v1.scale;
            v1.value *= 10;
        }
        res.scale = v1.scale;
        res.value = v1.value + v2.value;
    }

    while (res.value % 10 == 0 && res.value != 0) {
        res.value /= 10;
        --res.scale;
    }

    return res;
}

lrealn minus_real(lrealn v1, lrealn v2)
{
    v2.value = -v2.value;
    return add_real(v1, v2);
}

lrealn multi_real(lrealn v1, lrealn v2)
{
    lrealn res;
    res.value = v1.value * v2.value;
    res.scale = v1.scale + v2.scale;

    while (res.value % 10 == 0 && res.value != 0) {
        res.value /= 10;
        --res.scale;
    }

    return res;
}

lrealn div_real(lrealn v1, lrealn v2)
{
    lrealn res;
    if (v1.scale == v2.scale) {
        res.scale = v1.scale;
        res.value = v1.value / v2.value;
    } else if (v1.scale > v2.scale) {
        while (v1.scale > v2.scale) {
            ++v2.scale;
            v2.value *= 10;
        }
    } else {
        while (v1.scale < v2.scale) {
            ++v1.scale;
            v1.value *= 10;
        }
    }

    while (v1.scale < global_scale + v2.scale) {
        v1.value *= 10;
        ++v1.scale;
    }
    res.scale = global_scale;
    res.value = v1.value / v2.value;

    while (res.value % 10 == 0 && res.value != 0) {
        res.value /= 10;
        --res.scale;
    }

    return res;
}

lrealn createreal(long long val, int sca)
{
    lrealn res;
    res.value = val;
    res.scale = sca;
    return res;
}

lrealn atoreal(const char *source)
{
    lrealn res;
    res.value = 0;
    res.scale = 0;
    int exponent = 1;
    for (int i = (int)strlen(source) - 1; i >= 0; --i) {
        if (isdigit(source[i])) {
            res.value += ((source[i] - '0') * exponent);
            exponent *= 10;
        } else if (source[i] == '.') {
            res.scale = (int)strlen(source) - i - 1;
        }
    }
    if (source[0] == '-') {
        res.value *= -1;
    }
    return res;
}

lrealn zeroreal()
{
    lrealn res;
    res.value = 0;
    res.scale = 0;
    return res;
}

void print_real(lrealn source)
{
    long long intpart = source.value;
    long long times = 1;
    int length = vallen(source.value);
    for (int i = 0; i < source.scale; ++i) {
        intpart /= 10;
        times *= 10;
    }
    if (length > source.scale) {
        if (source.scale > 0 && source.value != 0) {
            printf("%lld.%lld\n", intpart, source.value - intpart * times);
        } else {
            printf("%lld\n", source.value);
        }
    } else {
        printf("0.");
        for (int i = 0; i < source.scale - length; ++i) {
            putchar('0');
        }
        printf("%lld\n", source.value);
    }
}

int vallen(long long source)
{
    int length = 0;
    while (source != 0) {
        source /= 10;
        ++length;
    }
    return length;
}