algorithm - 简化表达式树

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 这样的属性( associativity ) 和 Orderless ( commutativity )。也不要定义 Plus和 Times作为“二元”运算符但作为“多参数”运算符。
所以输入如下:

Plus(x,Plus(y,x))

由于 Flat，在第一步中可以转换(展平)归因于

Plus(x,y,x)

在下一步中，由于 Orderless，它可以被转换(排序)。归因于

Plus(x,x,y)

在您的“评估”步骤中，您现在可以查看参数并将表达式“简化”为:

Plus(Times(2,x),y)

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