找到给定数学表达式的所有可能答案的算法

Question

这个问题困扰我好几天了，我想知道解决这个问题的最简单和最好的方法是什么。决定与 SO 社区讨论它。

问题说明，我们有一个包含一些数字和一些操作(有效操作只有 +、- 和 *)的字符串，现在找到这个数学表达式的所有可能答案在所有可能的地方放置牙套。

例如，如果输入字符串是“1+2-3*4”
答案可以是

(((1+2)-3)*4) = 0
(((1+2)-(3*4)) = -9
(1+((2-3)*4) = -3
(1+(2-(3*4))) = -9
((1+(2-3))*4) = 0

像这样，(我可能遗漏了某些情况或计算错误，但你明白了 :D )，并且假设我们始终以字符串形式输入有效，并且只有 1最初是数字，我们必须打印所有可能的答案组合，什么是最简单和/或最好的算法。

PS: 我不知道这个社区是否适合提出此类问题，但我看到很多类似的问题，所以我发布了这个，如果这个社区不适合提出此类问题，请指导我是哪一个。谢谢。

Answer 1

所以这看起来是一个简单的递归问题，而你的递归步骤应该是(我会把编码留给你):

“在这里打开一对括号并继续”

还有，如果适用(你后面有左括号):

“在这里关闭一对括号并继续”

总结 - 确保在编写代码时考虑表达式的合法性:

1. 您的递归步骤是在每个操作之后而不是在数字之后执行的。
2. 关闭的括号数量与打开的括号数量相同。
3. 如果不合法，则不要关闭一对括号(每一步打开的括号数 >= 关闭的括号数)。

当您到达表达式的末尾时，计算并打印出一个值。

编辑:

伪代码类似于(即时编写，没有考虑极端情况等，但足以让您了解总体思路):

public void Solve(string expression,int positions, int currentPosition, int numberOfOpened,int[] brackets){
如果(当前位置==位置){
//我们完成了，这个方法可以通过使用堆栈来实现
//在 StackOverflow 上可以找到各种解决方案。
PrintSolution(表达式，括号)；
返回;
}
//关闭并继续递归
如果(打开数 > 0){
int[] newBrackets = CloneAndAddClosingBracket(括号);
求解(表达式、位置、currentPosition++、numberOfOpened-1、newBrackets)；
}
//开启并继续递归
int[] newBrackets = CloneAndAddOpeningBracket(括号);
求解(表达式、位置、currentPosition++、numberOfOpened+1、newBrackets)；
}