#define _GNU_SOURCE
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>

/*****************************
 ******** STREAM / LEXER
 *****************************/

typedef enum { OPERATOR, NUMBER, END } tokentype;

typedef enum { PLUS, MINUS, MUL, DIV } operator;

typedef struct {
    tokentype type;
    union {
        int as_int;
        operator as_op;
    } val;
} token;

typedef struct {
    const char* cur;
    const char* e;
    int char_idx;
    token tok;
} stream;

stream build_stream(const char* data, size_t sz) {
    stream s;
    s.cur = data;
    s.e = data + sz;
    s.char_idx = 0;
    return s;
}

char stream_peek(stream* s) {
    if (s->cur == s->e) {
        return 0;
    }
    return *s->cur;
}

char stream_getc(stream* s) {
    if (s->cur == s->e) {
        return 0;
    }

    char c = *s->cur;
    ++s->cur;
    ++s->char_idx;
    return c;
}

int stream_is_eof(const stream* s) { return !*s->cur || s->cur == s->e; }

/***********************************
 ******** TOKEN *************
 **********************************/

int is_operator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; }

token lex_op(stream* s) {
    char c = stream_getc(s);
    token t;
    t.type = OPERATOR;
    switch (c) {
        case '+':
            t.val.as_op = PLUS;
            return t;
        case '-':
            t.val.as_op = MINUS;
            return t;
        case '*':
            t.val.as_op = MUL;
            return t;
        case '/':
            t.val.as_op = DIV;
            return t;
        default:
            assert(0);
    }
}

token lex_int(stream* s) {
    int i = 0;
    char c = stream_peek(s);

    while (isdigit(c)) {
        i = i * 10 + c - '0';
        stream_getc(s);
        c = stream_peek(s);
    }
    token t;
    t.type = NUMBER;
    t.val.as_int = i;
    return t;
}

token lex(stream* s) {
    char c = stream_peek(s);

    while (isspace(c)) {
        stream_getc(s);
        c = stream_peek(s);
    }

    if (isdigit(c)) {
        s->tok = lex_int(s);
        return s->tok;
    } else if (is_operator(c)) {
        s->tok = lex_op(s);
        return s->tok;
    } else if (stream_is_eof(s)) {
        token t;
        t.type = END;
        s->tok = t;
        return t;
    }
    assert(0);
}

/********************* PARSING *******************/
typedef enum { NUM, BINOP, PARENTHESIS } asttype;

// fwd decl
typedef struct bite ast;

typedef struct { int value; } astnum;

typedef struct {
    ast* lhs;
    operator op;
    ast* rhs;
} astbinop;

typedef struct { ast* in_parenthesis; } astparenth;

struct bite {
    asttype type;
    union {
        astnum as_num;
        astbinop as_binop;
        astparenth as_parenthesis;
    } val;
};

#if 0
expr :: add
add :: nbr {"+"|"-" nbr}
mul :: add {"*"|"/" add}
nbr :: NUMBER | "(" expr ")"
#endif

ast* parse_nbr(stream* s) {
    ast* nbr = malloc(sizeof(*nbr));
    nbr->type = NUM;
    token t = lex(s);
    if (t.type != NUMBER) {
        return NULL;
    }
    nbr->val.as_num.value = t.val.as_int;
    lex(s);
    return nbr;
}

ast* parse_mul(stream* s) {
    ast* mul = malloc(sizeof(*mul));
    ast* root = mul;

    mul->type = BINOP;

    mul->val.as_binop.lhs = parse_nbr(s);
    if (!mul->val.as_binop.lhs) {
        return NULL;
    }

    mul->val.as_binop.rhs = NULL;
    token t = s->tok;
    while (t.type == OPERATOR && (t.val.as_op == DIV || t.val.as_op == MUL)) {
        mul->val.as_binop.op = t.val.as_op;
        ast* mul_rhs = malloc(sizeof(*mul));
        mul->val.as_binop.rhs = mul_rhs;
        mul_rhs->type = BINOP;
        mul_rhs->val.as_binop.lhs = parse_nbr(s);
        mul_rhs->val.as_binop.rhs = NULL;

        t = s->tok;
        mul = mul_rhs;
    }
    return root;
}

ast* parse_add(stream* s) {
    ast* add = malloc(sizeof(*add));
    add->type = BINOP;

    add->val.as_binop.lhs = parse_mul(s);
    if (!add->val.as_binop.lhs) {
        return NULL;
    }

    add->val.as_binop.rhs = NULL;
    token t = s->tok;
    if (t.type == OPERATOR && (t.val.as_op == PLUS || t.val.as_op == MINUS)) {
        add->val.as_binop.op = t.val.as_op;
        add->val.as_binop.rhs = parse_add(s);
        if (!add->val.as_binop.rhs) {
            return NULL;
        }
    }
    return add;
}
ast* parse(stream* s) { return parse_add(s); }

void ast_print(const ast*);

void ast_print_num(const ast* a) { printf("%d", a->val.as_num.value); }

void ast_print_binop(const ast* a) {
    printf("(");
    ast_print(a->val.as_binop.lhs);
    printf(")");
    if (!a->val.as_binop.rhs) {
        return;
    }

    switch (a->val.as_binop.op) {
        case PLUS:
            printf(" + (");
            break;
        case MINUS:
            printf(" - (");
            break;
        case DIV:
            printf(" / (");
            break;
        case MUL:
            printf(" * (");
            break;
    }
    ast_print(a->val.as_binop.rhs);
    printf(")");
}

void ast_print_parenthesis(const ast* a) {
    printf("(");
    ast_print(a->val.as_parenthesis.in_parenthesis);
    printf(")");
}

void ast_print(const ast* a) {
    switch (a->type) {
        case NUM:
            ast_print_num(a);
            return;
        case BINOP:
            ast_print_binop(a);
            return;
        case PARENTHESIS:
            ast_print_parenthesis(a);
            return;
    }
}

int ast_eval(const ast*);

int ast_eval_num(const ast* a) { return a->val.as_num.value; }

int ast_eval_binop(const ast* a) {
    int lhs = ast_eval(a->val.as_binop.lhs);
    if (!a->val.as_binop.rhs) {
        return lhs;
    }

    int rhs = ast_eval(a->val.as_binop.rhs);
    switch (a->val.as_binop.op) {
        case PLUS:
            return lhs + rhs;
        case MINUS:
            return lhs - rhs;
        case DIV:
            return lhs / rhs;
        case MUL:
            return lhs * rhs;
        default:
            assert(0);
    }
}

int ast_eval_parenthesis(const ast* a) {
    return ast_eval(a->val.as_parenthesis.in_parenthesis);
}

int ast_eval(const ast* a) {
    switch (a->type) {
        case NUM:
            return ast_eval_num(a);
        case BINOP:
            return ast_eval_binop(a);
        case PARENTHESIS:
            return ast_eval_parenthesis(a);
        default:
            assert(0);
    }
}

int main() {
    char* line = NULL;
    size_t sz = 0;
    getline(&line, &sz, stdin);

    stream s = build_stream(line, sz);
    ast* a = parse(&s);
    ast_print(a);
    printf("\nres=%d\n", ast_eval(a));
    return 0;
}