判断含相同四操作数的两个算术表达式等价性的算法需求

问题描述 #

给定两个包含完全相同的4个1-10整数操作数的算术表达式e1和e2，判断二者是否等价。等价定义为：可通过加法交换律/结合律、乘法交换律/结合律、减法转加法、除法转乘法等数学性质，转换为结构完全相同的表达式。该算法用于解决24点游戏中的无重复解列举问题。

约束条件 #

• e1和e2的操作数为1-10的整数，且两组操作数完全相同（数量、数值一致）；
• 仅允许使用四种基本二元算术运算：加法(+)、减法(-)、乘法(*)、除法(/)；
• 减号(-)仅作为二元减法运算符，不支持一元取反；
• 可通过括号改变运算优先级。

示例 #

1. 输入：e1 = "6 * (2 + 5 - 3)"，e2 = "(5 - 3 + 2) * 6"
   输出：true
   说明：乘法交换律允许交换左右操作数，括号内的加减通过交换律/结合律可整理为相同逻辑，二者等价。

2. 输入：e1 = "5 - (2 - 7 * 3)"，e2 = "3 * 7 + 5 - 3"
   输出：true
   说明：展开e1得到5 - 2 + 7*3，通过加法交换律调整操作数顺序后，与e2的7*3 +5 -2完全一致。

3. 输入：e1 = "(7 + 5) / (2 / 4)"，e2 = "(7 + 5) * 4 / 2"
   输出：true
   说明：根据除法性质a/(b/c) = a*c/b，两个表达式可转换为相同的乘除结构。

4. 输入：e1 = "(7 + 5) * 4 / 2"，e2 = "(7 + 5) * (4 - 2)"
   输出：false
   说明：虽然二者计算结果均为24，但运算逻辑无法通过数学性质转换为一致结构——前者是乘除组合，后者是乘减组合，因此不等价。

实现思路 #

要高效判断等价性，核心是将表达式转换为标准化的数学表示，再直接对比：

1. 表达式解析：将字符串表达式解析为抽象语法树（AST），或直接拆解为运算节点和操作数的层级结构。
2. 标准化处理：
   • 加法/乘法：利用交换律和结合律，将同级操作数按固定规则排序（如从小到大），同时合并连续的加减/乘除操作。例如a+b-c和b-c+a都可标准化为(a+b)-c（按操作数升序排列）。
   • 减法：转换为“加负数”形式后纳入加法标准化逻辑，注意保留原始操作数的符号关联（因不允许一元负号，需将a-b视为a + (-b)，但-b需作为特殊节点处理）。
   • 除法：转换为“乘倒数”形式后纳入乘法标准化逻辑，例如a/(b/c)转为a*c/b，再按乘法规则排序操作数。
3. 等价对比：将两个表达式经过标准化后的AST或结构字符串进行对比，完全一致则返回true，否则返回false。

替代方案：若对精度要求不高，可生成多组随机的操作数替换值（保持原表达式的运算结构，替换为其他1-10的整数），计算两个表达式的结果，若所有结果都一致则判定等价。此方法适合快速验证，但需注意避免因巧合导致的误判。

内容的提问来源于stack exchange，提问作者aruku7230