简化表达式树

Question

我正在尝试编写一个简化数学表达式的程序。

我已经编写了一个将字符串转换为二叉树的解析器。例如 (1+2)*x 将变为

    *
   / \
  +   x
 / \
1   2

我简化此类树的想法如下：您存储一组树及其简化版本例如

    *                       +
   / \                     / \
  a   +        and        *   *
     / \                 / \ / \
    b   c               a  b a  c

（其中 a、b、c 可以是任何子树）然后，如果我找到与存储的树之一匹配的子树，我将用其简化版本替换它。

如果有必要，我会重复这个过程，直到树完全简化。

这种方法的问题在于，在某些情况下它无法“组合同类项”。例如，如果我尝试存储树：

      +                *
     / \      and     / \
    x   x            2   x

然后，当我尝试使用以下树简化表达式 x+y+x 时：

    +
   / \
  x   +
     / \
    y   x  

不会简化为2x+y，因为子树

      +     
     / \     
    x   x      

不包含在树中，因此树不会被简化。

我尝试编写一个显式算法来组合类似的项，但需要考虑的情况太多。

谁能帮我找到解决这个问题的方法吗？

Answer 1

这是计算机代数系统中使用的基本思想之一。

对于Plus(+) 和Times(*) 等运算符，您可以定义Flat(结合性) 和Orderless(交换性) 等属性。也不要将Plusand定义Times为“二元”运算符，而是定义为“多参数”运算符。

所以输入如下：

Plus(x,Plus(y,x))

在第一步中可以被转换（扁平化），因为Flat属性

Plus(x,y,x)

在下一步中，由于Orderless属性，它可以被转换（排序）

Plus(x,x,y)

在“评估”步骤中，您现在可以遍历参数并将表达式“简化”为：

Plus(Times(2,x),y)

这种方法的优点是“结构相等”的表达式以相同的“规范形式”存储，并且例如可以更容易地与所使用的编程语言中的“对象相等”进行比较。