algorithm - 测试两个代数表达式等价的算法

Question

我必须编写一个程序来测试两个代数表达式是否等价。它应该遵循 MDAS 优先级和括号分组。为了解决优先级问题，我想我应该为这些表达式实现一个中缀到后缀符号转换器。但是通过这样做，我无法得出它们的等价性。

程序应如下所示： 用户输入：a*(a+b) = a*a + a*b 输出：等效

对于这个问题，我不允许使用计算机代数系统或任何外部库。如果你有，请不要发布实际代码，我只需要一个想法来解决这个问题。

Answer 1

如果不允许对表达式求值，则必须将它们解析为表达式树。

之后，我将通过乘/除所有成员来去掉所有括号，这样 a(b - c) 就变成了 a*b - a*c。

然后将所有表达式转换回字符串，确保所有成员按字母顺序排序（a*b，而不是 b*a），删除所有空格并比较字符串。

Answer 2

这是一个想法：
您需要首先实现构建表达式树，因为它是表达式的非常自然的表示。
然后，也许您需要使用关联或分配代数属性通过开括号等来简化它。
然后你必须比较树木。这并不明显，因为您需要处理交换操作等中的所有分支排列。例如，您可以对它们进行排序（我的意思是分支），然后比较是否相等。您还需要记住可能的参数重命名，即a + b 需要等于x + y。