简化表达式树

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

我已经编写了一个将字符串转换为二叉树的解析器。 例如 (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      

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

我尝试编写一个显式算法来组合类似的术语，但是有太多 需要考虑的案例。

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

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

对于像这样的运营商Plus(+) 和Times(*) 您可以定义如下属性Flat (关联性 https://en.wikipedia.org/wiki/Associative_property) and Orderless (交换律 https://en.wikipedia.org/wiki/Commutative_property）。也不要定义Plus and Times作为“二元”运算符，但作为“多参数”运算符。

所以输入如下：

Plus(x,Plus(y,x))

第一步中可以进行变换（扁平化），因为Flat归因于

Plus(x,y,x)

在下一步中可以对其进行转换（排序），因为Orderless归因于

Plus(x,x,y)

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

Plus(Times(2,x),y)

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