diff options
Diffstat (limited to 'parse_lisp_expression.py')
-rw-r--r-- | parse_lisp_expression.py | 46 |
1 files changed, 46 insertions, 0 deletions
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))")) |