#define _GNU_SOURCE
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
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; }
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);
}
typedef enum { NUM, BINOP, PARENTHESIS } asttype;
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
#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;
}