algorithm - 使用树结构，检查两个给定表达式是否相等

Question

问题

我有两个表达式。

只使用了两个运算符:+ 和 *。 (示例:(a + b)、(a * b) 是有效的表达式)。

我应该编写一个程序来确定这两个表达式是否相等。

示例:

1. 表达式 1:(a + b)c = ac + b*c;
2. 表达式 2:c*(a + b) = ca + cb = ac + bc;

结论:表达式 1 和 2 相等。

---

注意事项:

我有以下指示:

将这两个表达式以“乘积之和”的形式，对和的项进行排序，然后检查表达式是否相等。我应该使用树结构来完成这个任务:

1. 创建 Expression Tree对于两个表达式中的每一个
2. 对于两个结果的每棵树(从第 1 点开始)创建另一棵树，这将表示相应表达式的“乘积之和”形式。

---

我已经知道的

我已经编写了创建 Expression Trees 的程序.我有处理树木的经验。

---

问题

能否请您向我推荐一个可以解决此问题的算法？提前谢谢你。

Answer 1

您需要首先搜索在加法节点上方有乘法节点的情况。当你找到替换那里的结构时，添加在最上面。这样做直到您不再发现任何此类情况。

现在您的树应该看起来像产品的总和。取每个产品并左右翻转 child ，使他们排序。确切的标准并不重要，但是对于像 abc 这样的乘积项，您应该始终获得相同的结构(请注意，还应该将项与节点进行比较，并且可能旋转项，以便可以将 (ab)c 和 a(bc) 固定为相同的结构)。完成后，对上面的添加执行相同的操作。

对两个表达式树都执行此操作，完成后只需比较是否得到完全相同的树。