用二进制搜索树解决S表达式

Question

我有一个解析为阅读器的字符串，该字符串将其放入数组，如下所示：

X = '(mul 5 (add 5 5))'
Y = parser(X)
y = ['mul', 5, ['add', 5, 5]]

我想查找此表达式Y的值。建议使用二叉搜索树并遍历节点。我只是不知道该怎么做。请注意，我需要将其用作常规例程，以便它适用于任何字符串，例如'(mul (add 1 2) (log 8))

Answer 1

您需要的是递归以逐步浏览已经给出的树，并通过每个节点上的函数汇总来自树叶子的值。

这里是一个简化的示例。一个完整的示例将需要处理更多的功能，并且还需要进行错误检查（域，例如sqrt的肯定性，参数个数，...）。

import math

def get_value(expr):
    res = 0
    if type(expr) is list:
        if len(expr) > 0:  # check for empty list
            # recursively find the value of each argument
            arguments = [get_value(arg) for arg in expr[1:]]

            if expr[0] == 'mul':
                res = 1
                for arg in arguments:
                    res *= arg
            elif expr[0] == 'add':
                res = 0
                for arg in arguments:
                    res += arg
            elif expr[0] == 'log':
                if len(arguments) == 1:
                    res = math.log(arguments[0])
                elif len(arguments) == 2:
                    res = math.log(arguments[0], arguments[1])
    elif type(expr) is str:
        if expr == 'pi':
            res = math.pi
        elif expr == 'e':
            res = math.e
    elif type(expr) in [int, float]:
        res = expr
    return res


y = ['mul', 5, ['add', 5, 5]]
print(get_value(y)) # 50

print(get_value(['log', 10])) # 2.302585092994046
print(get_value(['log', 10, 10])) # 1.0
print(get_value(['mul', ['add', 1, 2], ['log', 8]])) # 6.238324625039507