Решить S-выражение с помощью двоичного дерева поиска

У меня есть строка, которая анализируется в читателе, который помещает ее в массив, как показано:

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

Я хочу найти значение этого выражения Y Было предложено использовать двоичное дерево поиска и проходить через узлы. Я просто не знаю, как это сделать. Обратите внимание, мне нужно, чтобы это работало как общая подпрограмма, чтобы она работала для любой строки, например '(mul (add 1 2) (log 8))

Всего 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

Есть идеи?

10000