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

Question

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

Как побочный проект, я строю систему компьютерной алгебры в 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». Это похоже на лучшее решение, но как лучше всего «реконструировать» каждый шаг?

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

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

Answer 1

Возможно, вы спрашиваете о деревянных молниях. Проверьте: Functional Pearl: Weaving a Web и посмотрите, относится ли оно к тому, что вы хотите. Из чтения вашего вопроса, я думаю, вы просите сделать рекурсию по древовидной структуре, но сможете при необходимости вернуться к вершине. Молнии действуют как «хлебная крошка», чтобы вы могли вернуться к предкам дерева.

У меня есть одна из них в JavaScript.

Answer 2

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

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