0

首先，上下文：

作为一个附带项目，我正在用 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样子。

所以这是我的问题：保持整个表达式树的“状态”以使每个“步骤”都了解整个表达式的最佳方法是什么？

以下是我提出的解决方案：

  • 在适当的位置执行每个操作，并使用全局变量或类中的实例变量来存储指向等式的指针。我不喜欢这样，因为单元测试更难，因为现在我必须先设置类。您还失去了功能更强大的方法的其他优势。
  • 将表达式的根传递给每个函数。但是，这要么意味着我必须重复每个操作来更新表达式，要么我必须依赖可变性。
  • 让顶层函数根据我产生的每一步“重建”表达式树。例如，如果我 yield 5x + 4x = 9x，让顶级函数找到 (5x + 4x) 节点并将其替换为“9x”。这似乎是最好的解决方案，但如何最好地“重建”每一步呢？

最后两个相关的问题：这是否有意义？我现在有很多咖啡因在我的系统中，不知道我是否清楚。

我是否过于担心可变性？这是过早优化的情况吗？

4

2 回答 2

1

您可能会问有关树拉链的问题。检查：功能明珠：编织网络，看看它是否适用于您想要的。通过阅读您的问题，我认为您要求对树结构进行递归，但能够根据需要导航回顶部。拉链充当“面包屑”，让您回到树的祖先。

我在JavaScript中有一个实现。

于 2013-11-27T19:57:42.367 回答
0

您是否使用波兰符号来构建树？

对于逐步简化，您可以只使用一个循环，直到不能在树中进行任何修改（操作）。

于 2013-12-13T20:06:47.230 回答