判断两个表达式是否等价的算法

Question

给定两个算术表达式e1和e2，判断它们是否等价。 如果两个表达式可以排列成相同的表达式，则它们是等价的 根据数学性质。 如果它们等价则返回 true，否则返回 false。

我只是想不出解决这个问题的算法。 我需要这个算法来解决问题以列出所有解决方案而无需 24游戏.

的复制

例子

例一：

• 输入：e1是“a + (b + c)”，e2是“c + (b + a)”。
• 输出：真

例二：

• 输入：s1是“a * (b + c) + d”，s2是“d + (c + b) * a”。
• 输出：真

例三：

• 输入：s1是“a - (b - c - d)”，s2是“d + c + a - d”。
• 输出：真

例四：

• 输入：s1是“a - b”，s2是“b - a”。
• 输出：如果 a 不等于 b，则为 false。否则为真。

例5：

• 输入：s1是“a / b”，s2是“b / a”。
• 输出：如果 a 不等于 b，则为 false。否则为真。

约束

• 表达式 1 和表达式 2 具有相同数量的操作数。 oprands 的数量是从 4 到 10.
• Opprands 是大于 0 的整数。
• 只能用四种基本的二进制算术运算：

  addition(+), subtraction(-), multiplication(*), division(/)

  .
• Minus(-) 只能用作减法运算符，不能用作一元运算符 计算其操作数的数值否定。
• 可以使用括号。

Answer 1

我将描述一种方法，并指出另一种更复杂但更有效的方法。

如果你不包括除法，那么会有一个简单的方法来做到这一点。也就是说，您将所有内容相乘，得到多项式，按字典顺序写下每个术语（即

a

在

b

之前，等等），然后按字典顺序对术语进行排序（按

a

的幂，按

b

的幂等），然后组合相似的术语。这会将每个表达式转换为规范化形式。当且仅当多项式匹配时，表达式才匹配。

正如@Richard 指出的那样，该算法具有指数复杂度。但是只有 4 个操作数，它的复杂度就可以了。您在编码时必须仔细考虑，但您应该能够成功。

但是..我们有分裂。

有两条路可以走。

最简单的方法是将顶部和底部相乘为

X/Y

形式的多元多项式。如果你想知道是否

X1/Y1 = X2/Y2

你交叉乘法，看看是否

X1*Y2 = X2*Y1

。这需要在每对表达式之间进行成对比较。对于一次性操作，这可能是可以接受的。

如果不是，那么是时候去兔子洞了。我们需要将

X/Y

本身归一化。这需要计算一个 GCD，Syzygies 的 Polynomial GCDs 提供了一个算法。为了完成规范化形式，我们不仅要采用具有

X/Y

的

GCD(X, Y) = 1

形式，而且我们还希望确保

Y

处于具有 positive 前导系数的规范化形式。 （如果系数最终为负，则将 top 和 bottom 乘以

-1

。）

现在所有的表达式都可以归一化了，然后你可以比较（例如对它们进行排序），看看哪些是相同的。

祝你好运！

Answer 2

找到解决这个问题的算法具有挑战性，因为您提出的问题的一个特例是确定多项式是否等价。

多项式身份测试 具有未知的计算复杂性，但众所周知，蛮力解决方案可能需要指数时间。因此，标准方法是使用随机输入并使用 Schwartz-Zippel 引理 测试是否相等。

我希望编写此实现比其他方法更容易，并且性能更好。

请注意，在实现此功能时，您需要注意整数溢出和浮点数问题。对于您的情况，使用无符号 64 位整数或长双精度数可能就足够了。

你可能会担心算法的概率性质。但是考虑一下，我们可以将是否

p=q

的问题转化为是否

p-q=0

的问题。如果

p-q

在其整个范围内为零，则

p=q

。否则，

p-q

是一个

d

次多项式，最多有

d

点等于零。如果我们从大小为

S

的集合

|S|

中选择测试值，那么找到其中一个点的概率是

d/|S|

，它随着

|S|

的增长而变小。如果我们进行多次评估，我们可以将概率推得更低。