c++ - 在 C++ 中检测相同表达式的好方法

Question

我正在编写一个解决这个益智游戏的程序:给出了一些数字和一个目标数字，你使用 n 个数字和运算符 +、-、*、/和 () 来计算目标数字。例如，给定 2,3,5,7 和目标编号 10，解决方案是 (2+3)*(7-5)=10, 3*5-(7 -2)=10，以此类推。

要注意的是，如果我天真地实现它，我会得到一堆相同的解决方案，比如 (2+3)*(7-5)=10 和 (3+ 2)*(7-5)=10, 3*5-(7-2)=10 and 5*3-(7-2)=10 和 3*5-7+2=10 和 3*5+2-7=10 等等。所以我想检测那些相同的解决方案并修剪它们。

我目前使用随机生成的双数来检测相同的解决方案。我所做的基本上是将这些随机数替换为解决方案，并检查是否有任何一对随机数计算出相同的数字。我必须在我搜索的每个节点执行检测，所以它必须很快，我现在使用 hashset。

现在的问题是计算带来的错误。因为即使是相同的解决方案也不会计算出完全相同的值，所以我目前在将计算值存储在哈希集中时将其四舍五入到一个精度。但是，这似乎效果不佳，并且每次针对同一问题给出不同数量的解决方案。有时随机数不好，会修剪一些完全不同的解决方案。有时计算值位于舍入函数的边缘，它会输出两个(或多个)相同的解。有更好的方法吗？

编辑:“相同”是指两个或多个解决方案(f(w,x,y,z,...) 和 g(w,x,y,z,...))计算出相同的数字，无论原始数字是多少数字(w，x，y，z ...)是。对于更多示例，4/3*1/2 和 1*4/3/2 以及 (1/2)/(3/4) 是相同的，但是 4/3/1/2 和 4/(3*1)/2 不是因为如果您将 1 更改为其他数字，它们将不会产生相同的结果。

Answer 1

如果在比较表达式之前“规范化”它们会更容易。一种方法是在操作可交换时进行排序，因此 3+2 变为 2+3 而 2+3 保持原样。当然，您还需要为带括号的组建立排序，例如 3+(2*1)...是否变为 (1*2)+3还是 3+(1*2)？顺序是什么不一定重要，只要它是总顺序即可。