// 736. Parse Lisp Expression #include "leetcode.h" struct var { int val; int name_size; char *name; struct var *next; }; struct scope { struct var *head; struct scope *up; }; static struct var *scope_local_lookup(struct scope *s, char *var_name, int name_size) { for (struct var *n = s->head; n; n = n->next) { int cmp_size = n->name_size; cmp_size = cmp_size < name_size ? name_size : cmp_size; if (!strncmp(var_name, n->name, cmp_size)) return n; } return NULL; } static struct var *scope_local_define(struct scope *s, char *var_name, int name_size) { struct var **n; int cmp_size; for (n = &s->head; *n; n = &(*n)->next) { cmp_size = (*n)->name_size; cmp_size = cmp_size < name_size ? name_size : cmp_size; if (!strncmp(var_name, (*n)->name, cmp_size)) return *n; } *n = (struct var *)malloc(sizeof(struct var)); if (!(*n)) return NULL; (*n)->name = var_name; (*n)->name_size = name_size; (*n)->next = NULL; return *n; } static struct var *scope_global_lookup(struct scope *s, char *var_name, int name_size) { for (struct scope *n = s; n; n = n->up) { struct var *v = scope_local_lookup(n, var_name, name_size); if (v) return v; } return NULL; } static void scope_free_data(struct scope *s) { for (struct var *n = s->head, *t; n;) { t = n; n = n->next; free(t); } s->head = NULL; } static void scope_free(struct scope *s) { for (struct scope *n = s, *t; n;) { t = n; n = n->up; scope_free_data(t); free(t); } } static struct scope *push_scope(struct scope **s) { struct scope *parent = *s; *s = (struct scope *)malloc(sizeof(struct scope)); if (!(*s)) { *s = parent; return NULL; } (*s)->up = parent; (*s)->head = NULL; return *s; } static struct scope *pop_scope(struct scope **s) { struct scope *parent = (*s)->up; scope_free_data(*s); free(*s); return *s = parent; } enum token_state { END, INT, NAME, SEXP, CLOSE }; struct token { int type; int len; int val; char *str; }; static int token_next(char **s, struct token *dst) { int status = 1, sign; for (; isspace(**s); ++(*s)) ; if (**s == '\0') { dst->len = 0; dst->type = END; return 1; } dst->str = *s; if (isdigit(**s) || **s == '-' || **s == '+') { sign = **s == '-'; if (**s == '-' || **s == '+') ++(*s); dst->type = INT; dst->val = 0; for (; isdigit(**s); ++(*s)) dst->val = dst->val * 10 - (**s - '0'); dst->val = sign ? dst->val : -dst->val; } else if (isalpha(**s)) { dst->type = NAME; for (; isalnum(**s); ++(*s)) ; } else if (**s == '(') { dst->type = SEXP; ++(*s); } else if (**s == ')') { status = 0; dst->type = CLOSE; ++(*s); } dst->len = *s - dst->str; return status; } static int eval(char **s, int *res, struct token *t, struct scope **curr); static int evaluate_command_let(char **s, int *res, struct token *t, struct scope **curr) { struct var *v; char *old_pos, *var_name; int var_name_size, var_val; if (!push_scope(curr)) return 0; for (;;) { old_pos = *s; if (!token_next(s, t)) return 0; if (t->type == NAME) { var_name = t->str; var_name_size = t->len; if (!eval(s, &var_val, t, curr)) { *s = old_pos; break; } v = scope_local_define(*curr, var_name, var_name_size); if (!v) return 0; v->val = var_val; } else { *s = old_pos; break; } } if (!eval(s, res, t, curr)) return 0; if (token_next(s, t)) return 0; pop_scope(curr); return 1; } static int evaluate_command_add(char **s, int *res, struct token *t, struct scope **curr) { int op1, op2; if (!eval(s, &op1, t, curr)) return 0; if (!eval(s, &op2, t, curr)) return 0; *res = op1 + op2; if (token_next(s, t)) return 0; return 1; } static int evaluate_command_mult(char **s, int *res, struct token *t, struct scope **curr) { int op1, op2; if (!eval(s, &op1, t, curr)) return 0; if (!eval(s, &op2, t, curr)) return 0; *res = op1 * op2; if (token_next(s, t)) return 0; return 1; } static int evaluate_command(char **s, int *res, struct token *t, struct scope **curr) { char *cmd = t->str; int cmd_size = t->len; if (!strncmp(cmd, "let", cmd_size)) return evaluate_command_let(s, res, t, curr); if (!strncmp(cmd, "add", cmd_size)) return evaluate_command_add(s, res, t, curr); if (!strncmp(cmd, "mult", cmd_size)) return evaluate_command_mult(s, res, t, curr); } static int evaluate_sexp(char **s, int *res, struct token *t, struct scope **curr) { if (!token_next(s, t)) return 0; if (t->type == NAME) return evaluate_command(s, res, t, curr); return 0; } static int eval(char **s, int *res, struct token *t, struct scope **curr) { struct var *v; if (!token_next(s, t)) return 0; switch (t->type) { case END: *res = 0; return 1; case SEXP: return evaluate_sexp(s, res, t, curr); case INT: *res = t->val; return 1; case NAME: v = scope_global_lookup(*curr, t->str, t->len); if (!v) return 0; *res = v->val; return 1; default: return 0; } } int evaluate(char *expression) { struct scope *curr = NULL; struct token t; char *s = expression; int ans = 0; if (!eval(&s, &ans, &t, &curr)) { scope_free(curr); return -1; } return ans; } int main() { char *e1 = "(let x 2 (mult x (let x 3 y 4 (add x y))))"; char *e2 = "let x 3 x 2 x)"; char *e3 = "(let x 1 y 2 x (add x y) (add x y))"; printf("%d\n", evaluate(e1)); // expect: 14 printf("%d\n", evaluate(e2)); // expect: 2 printf("%d\n", evaluate(e3)); // expect: 5 }