Рекурсивная работа с древовидной структурой: как получить состояние "всего" дерева?

Во-первых, контекст:

В качестве побочного проекта я строю систему компьютерной алгебры в Python, которая дает шаги, необходимые для решения уравнения.

До сих пор мне удавалось анализировать алгебраические выражения и уравнения в дереве выражений. Это структурировано что-то вроде этого (не фактический код - возможно, не работает):

# Other operators and math functions are based off this.
# Numbers and symbols also have their own classes with 'parent' attributes.
class Operator(object):
    def __init__(self, *args):
        self.children = args            
        for child in self.children:
            child.parent = self

# the parser does something like this:
expr = Add(1, Mult(3, 4), 5)

Помимо этого, у меня есть ряд функций, которые работают рекурсивно, чтобы упростить выражения. Они не являются чисто функциональными, но я стараюсь не полагаться на изменчивость операций, вместо этого возвращая измененную копию узла, с которым я работаю. Каждая функция выглядит примерно так:

def simplify(node):
    for index, child in enumerate(node.children):
        if isinstance(child, Operator):
            node.children[index] = simplify(node)
        else:
            # perform some operations to simplify numbers and symbols
            pass

    return node

Задача заключается в части "шаг за шагом". Я хотел бы, чтобы мои функции "упрощения" были всеми вложенными генераторами, которые "дают" шаги, необходимые для решения чего-либо. Таким образом, в принципе, каждый раз, когда каждая функция выполняет операцию, я хотел бы иметь возможность сделать что-то вроде этого: yield (deepcopy(node), expression, "Combined like terms.") так что все, что полагается на эту библиотеку, может вывести что-то вроде:

5x + 3*4x + 3
5x + 12x + 3                 Simplified product 3*4x into 12x
17x + 3                      Combined like terms 5x + 12x = 17x

Тем не менее, каждая функция имеет только знания о node он работает, но понятия не имеет, что в целом expression похоже.

Итак, это мой вопрос: как лучше всего поддерживать "состояние" всего дерева выражений, чтобы каждый "шаг" знал все выражение?

Вот решения, которые я придумала:

  • Выполняйте каждую операцию на месте и используйте глобальную переменную или переменную экземпляра в классе для хранения указателя на уравнение. Мне это не нравится, потому что юнит-тестирование сложнее, так как теперь я должен сначала настроить класс. Вы также теряете другие преимущества более функционального подхода.
  • Пройдите через корень выражения к каждой функции. Однако это либо означает, что я должен повторять каждую операцию, чтобы также обновить выражение, либо что мне приходится полагаться на изменчивость.
  • Пусть функция верхнего уровня "реконструирует" дерево выражений на основе каждого шага, который я получаю. Например, если я уступаю 5x + 4x = 9x, пусть функция верхнего уровня найдет узел (5x + 4x) и заменит его на '9x'. Это кажется лучшим решением, но как лучше "реконструировать" каждый шаг?

Два последних связанных вопроса: имеет ли это смысл? У меня сейчас много кофеина, и я понятия не имею, насколько я чист.

Я слишком беспокоюсь о изменчивости? Это случай преждевременной оптимизации?

Источник

2 ответа

Решение

Вы можете спросить о молниях дерева. Проверьте: Функциональная жемчужина: плетение в сети и посмотрите, относится ли это к тому, что вы хотите. Прочитав ваш вопрос, я думаю, что вы просите сделать рекурсию по древовидной структуре, но сможете вернуться к вершине по мере необходимости. Молнии действуют как "хлебная крошка", чтобы позволить вам вернуться к предкам дерева.

У меня есть реализация одного в JavaScript.

Источник

Вы используете польскую запись для построения дерева?

Для пошагового упрощения вы можете просто использовать цикл до тех пор, пока в дереве не будет произведено никаких модификаций (операций).

Источник
Другие вопросы по тегам