Challenge24 Solver实现背后的理论

Question

作为Java和android开发的介绍，我决定编写一个Challenge24(给定4个数字，必须加、乘、除或减才能创建乘积24)求解应用程序，它实现了一种详尽的技术来求解任何和所有可能的解。目前它是这样工作的(a，b，c，d是4个输入数)

((a+b)+c)+d
((a+b)+c)-d
((a+b)+c)*d
((a+b)+c)/d
((a+b)-c)+d
...
...
((a/b)/c)/d
((a+b)+d)+c
((a+b)+d)-c

以此类推。

我发现这在绝大多数情况下都有效，但是像8,3,8,3这样的情况在测试中没有找到解决方案，但是解决方案8/(3-8/3)=24是正确的。所以我猜最后的问题是相当模糊的，但是如何实现这一点来解释括号对于找到解决方案至关重要的情况？

Answer 1

将变量a、b、c、d视为输入，将+、-、*、/视为运算符

您将始终拥有三个运算符

a op b op c op d

现在我们来看一下下面的括号组合

1 group of 2
(a op b) op c op d
a op (b op c) op d
a op b op (c op d)

1 group of 3
(a op b op c) op d
a op (b op c op d)

each 3 can be comprised 
(x op y op z) as above example
(x op (y op z))
((x op y) op z)

Also, 2 groups of 2
(a op b) op (c op d)

现在，您必须使用每组操作测试上面的每种组合：

 Haha silly code parser, you think these are comments in here... tsk tsk
 +++, ++-, ++*, ++/, +-+, +--, +-*, +-/,
 +*+, +*-, +**, +*/, +/+, +/-, +/*, +//,
 -++, -+-, -+*, -+/, --+, ---, --*, --/,
 -*+, -*-, -**, -*/, -/+, -/-, -/*, -//,
 *++, *+-, *+*, *+/, *-+, *--, *-*, *-/,
 **+, **-, ***, **/, */+, */-, */*, *//,
 /++, /+-, /+*, /+/, /-+, /--, /-*, /-/,
 /*+, /*-, /**, /*/, //+, //-, //*, ///

因此，使用这些操作测试每组两个，每组三个(包括简单版本和嵌套版本)，一个具有两组两个。

据我估计，总共有640次测试。

这可以在逻辑上减少，例如，如果为op1 == op2 == op3，则括号不重要。你还可以做其他的减少。

编辑:然后，您需要遍历a、b、c、d的每个排列，这将使总数达到15,360 (当然，如果有重复的话会更少)。

Answer 2

如果您想继续详尽无遗，请为每种可能的括号组合创建条件。

Answer 3

我会通过枚举前缀或后缀表示法中可能的运算符/操作数组合，或者构建表达式树来实现这一点。这应该会使在循环和/或函数中表达它们变得更容易。然后，您可以将解决方案转换为用于输出的中缀；如果您不关心多余的括号，这将非常简单。

也许你可以通过这种方式对搜索顺序进行优化，但问题空间很小，我不会费心去做。