题解 | #S-expression#

使用 python 比较方便。先将输入的表达式转化为一个嵌套的 list，然后递归地求解每个子表达式的值即可。以下为代码中函数、全局变量的作用

• expr2ls(s)：输入一个 S-expression，将其转化为嵌套列表。例如：表达式“( let ( x 4 ) ( if true x y ) )”会转化为 ['let', ['x', 4], ['if', 'true', 'x', 'y']]
• evaluate(e)：输入一个表达式（列表/数字/字符串），返回它的值。按照题意处理即可
• variables：字典，记录目前被 let 语句赋值过的变量名
• solve()：解决一个测试 testcase

【吐槽一下，发帖有bug，下方代码块没法把我的代码全粘贴进来，无论如何都只有29行。可以自行在排行-Python3 中查看完整代码】

from collections import defaultdict
def expr2ls(s):
    t = ""
    for atom in s.split():
        if atom == '(':
            t += '['
        elif atom == ')':
            t += '],'
        elif atom.isdigit():
            t += atom + ','
        else:
            t += f"'{atom}',"
    return eval(t[:-1])
variables = defaultdict(list)
def evaluate(e):
    if type(e) == list:
        if e[0] in "+-*/<>=":
            e1, e2 = evaluate(e[1]), evaluate(e[2])
            if type(e1) != int or type(e2) != int:
                raise TypeError
            if e[0] == '/' and e2 == 0:
                raise ZeroDivisionError
            return (e1+e2, e1-e2, e1*e2, e1//e2, e1<e2, e1>e2, e1==e2)["+-*/<>=".find(e[0])]
        elif e[0] == "if":
            e1 = evaluate(e[1])
            if type(e1) != bool:
                raise TypeError
            return evaluate(e[2]) if e1 else evaluate(e[3])
        elif e[0] == "let":

多说一句，本题中，关于 let 语句的作用域是有歧义的。题干中没有提到，本题的后台数据中也没有出现这种情况，因此不考虑这一点也能AC。

考虑如下的表达式：

( let ( x 1 ) ( + ( let ( x 2 ) x ) x ) )

按理说，内层的 x 值应该为2，外层的 x 值应该为1。因此返回值应该为 3，而不是 4、2或者“Unbound Identifier”。要想实现作用域，需要把字典的值设为一个堆栈。变量赋值时入栈；表达式运行时取栈顶；let 表达式运行结束后将弹出。