aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--parse_lisp_expression.c264
-rw-r--r--parse_lisp_expression.py46
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))"))