diff options
-rw-r--r-- | parse_lisp_expression.c | 264 | ||||
-rw-r--r-- | parse_lisp_expression.py | 46 |
2 files changed, 310 insertions, 0 deletions
diff --git a/parse_lisp_expression.c b/parse_lisp_expression.c new file mode 100644 index 0000000..077420a --- /dev/null +++ b/parse_lisp_expression.c @@ -0,0 +1,264 @@ +// 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 +} diff --git a/parse_lisp_expression.py b/parse_lisp_expression.py new file mode 100644 index 0000000..302ef87 --- /dev/null +++ b/parse_lisp_expression.py @@ -0,0 +1,46 @@ +# 736. Parse Lisp Expression + + +class Solution(object): + def evaluate(self, expression): + """ + :type expression: str + :rtype: int + """ + stk, d, tokens = [], {}, [""] + + def getval(x): + return d.get(x, x) + + def evaluate(tokens): + if tokens[0] in ("add", "mult"): + tmp = map(int, map(getval, tokens[1:])) + return str(tmp[0] + tmp[1] if tokens[0] == "add" else tmp[0] * tmp[1]) + else: + for i in range(1, len(tokens) - 1, 2): + if tokens[i + 1]: + d[tokens[i]] = getval(tokens[i + 1]) + return getval(tokens[-1]) + + for c in expression: + if c == "(": + if tokens[0] == "let": + evaluate(tokens) + stk.append((tokens, dict(d))) + tokens = [""] + elif c == " ": + tokens.append("") + elif c == ")": + val = evaluate(tokens) + tokens, d = stk.pop() + tokens[-1] += val + else: + tokens[-1] += c + return int(tokens[0]) + + +if __name__ == "__main__": + obj = Solution() + print(obj.evaluate(expression="(let x 2 (mult x (let x 3 y 4 (add x y))))")) + print(obj.evaluate(expression="(let x 3 x 2 x)")) + print(obj.evaluate(expression="(let x 1 y 2 x (add x y) (add x y))")) |