从给定的数字中获取所有可能的操作组合的算法
我想编写一个给出一组数字的函数，例如: 2，3
它返回+、-、*和/操作的所有组合。
这两个数字的结果是：
2+3
2-3
2*3
2/3 对于数字: 2、3、4将是：
(2+3)+4
(2+3)-4
(2+3)*4
(2+3)/4
(2-3)+4
(2-3)-4
(2-3)*4
(2-3)/4
...
2+(3+4)
2+(3*4)
2+(3-4)
2+(3/4)
...
3+(2+4)
3+(2*4)
3+(2-4)
3+(2/4)
...
and so on操作符的顺序并不重要，关键是从所有可能的操作组合中获得所有的结果。
回答 1
Stack Overflow用户
发布于 2020-01-06 03:08:26
我将通过使用反向波兰表示法来解决这个问题，您只需将运算符和操作数附加到字符串中，同时考虑一些简单的规则。
例如，表达式2 + (3 * 4)将是反向波兰符号中的2 3 4 * +。另一方面，(2 + 3) * 4将是2 3 + 4 *。
如果我们已经有了一个部分表达式，我们可以添加一个操作数或一个运算符。
添加操作数总是可以完成的，并将堆栈的大小增加1。另一方面，添加运算符将堆栈的大小减少1(移除两个最上面的操作数并添加结果)，因此只能在堆栈至少有两个条目时才能完成。最后，要形成一个有效的表达式，堆栈大小必须正好为1。
这激发了具有以下接口的递归函数：
getSubexpressions(remainingOperands, currentStackSize)函数返回一个子表达式列表，这些子表达式可以附加到堆栈大小为currentStackSize的部分表达式中，并使用操作数remainingOperands。
此递归函数的基本情况是，当没有剩余的操作数且堆栈大小为1时：
if remainingOperands = ∅ and currentStackSize = 1
return { "" }在这种情况下，我们只能向表达式中添加空字符串。
在所有其他情况下，我们需要收集一组子表达式。
subexpressions = { } // initialize an empty set如果我们可以添加一个运算符，我们可以简单地附加它：
if currentStackSize >= 2
for each possible operator o
subexpressions.add(o + getSubexpressions(remainingOperands, currentStackSize - 1))符号o + getSubexpressions(remainingOperands, currentStackSize - 1)是将操作数o与调用getSubexpressions()返回的所有子表达式连接起来的缩写。
我们快到了。剩下的最后一位是添加潜在的操作数：
for each o in remainingOperands
subexpressions.add(o + getSubexpressions(remainingOperands \ { o }, currentStackSize + 1))表示法remainingOperands \ { o }表示集差，即没有o的剩余操作数集。
就这样。全文：
getSubexpressions(remainingOperands, currentStackSize)
if remainingOperands = ∅ and currentStackSize = 1
return { "" }
subexpressions = { } // initialize an empty set
if currentStackSize >= 2
for each possible operator o
subexpressions.add(o + getSubexpressions(remainingOperands, currentStackSize - 1))
for each o in remainingOperands
subexpressions.add(o + getSubexpressions(remainingOperands \ { o }, currentStackSize + 1))
return subexpressions这个递归调用通常有重叠的子调用。因此，您可以使用回忆录缓存中间结果，而不是反复计算它们。
这里是一个在C#中没有回忆录的概念实现的证明。特别是，操作数管理可以用更适当的数据结构更有效地设计：
static void Main(string[] args)
{
foreach (var expr in GetSubexpressions(new List<string> { "1", "2", "3" }, 0, new StringBuilder()))
{
Console.WriteLine(expr);
}
}
static char[] operators = { '+', '-', '*', '/' };
static IEnumerable<StringBuilder> GetSubexpressions(IList<string> remainingOperands, int currentStackSize, StringBuilder sb)
{
if (remainingOperands.Count() == 0 && currentStackSize == 1)
{
yield return sb;
yield break;
}
if(currentStackSize >= 2)
{
foreach (var o in operators)
{
sb.Append(o);
foreach (var expr in GetSubexpressions(remainingOperands, currentStackSize - 1, sb))
yield return expr;
sb.Remove(sb.Length - 1, 1);
}
}
for (int i = 0; i < remainingOperands.Count; ++i)
{
var operand = remainingOperands[i];
remainingOperands.RemoveAt(i);
sb.Append(operand);
foreach (var expr in GetSubexpressions(remainingOperands, currentStackSize + 1, sb))
yield return expr;
sb.Remove(sb.Length - operand.Length, operand.Length);
remainingOperands.Insert(i, operand);
}
} 该程序输出以下输出：
12+3+
12-3+
12*3+
12/3+
12+3-
12-3-
12*3-
12/3-
12+3*
12-3*
12*3*
12/3*
12+3/
12-3/
12*3/
12/3/
123++
123-+
123*+
123/+
123+-
123--
123*-
123/-
123+*
123-*
123**
123/*
123+/
123-/
123*/
123//
13+2+
13-2+
13*2+
13/2+
13+2-
13-2-
13*2-
13/2-
13+2*
13-2*
13*2*
13/2*
13+2/
13-2/
13*2/
13/2/
132++
132-+
132*+
132/+
132+-
132--
132*-
132/-
132+*
132-*
132**
132/*
132+/
132-/
132*/
132//
21+3+
21-3+
21*3+
21/3+
21+3-
21-3-
21*3-
21/3-
21+3*
21-3*
21*3*
21/3*
21+3/
21-3/
21*3/
21/3/
213++
213-+
213*+
213/+
213+-
213--
213*-
213/-
213+*
213-*
213**
213/*
213+/
213-/
213*/
213//
23+1+
23-1+
23*1+
23/1+
23+1-
23-1-
23*1-
23/1-
23+1*
23-1*
23*1*
23/1*
23+1/
23-1/
23*1/
23/1/
231++
231-+
231*+
231/+
231+-
231--
231*-
231/-
231+*
231-*
231**
231/*
231+/
231-/
231*/
231//
31+2+
31-2+
31*2+
31/2+
31+2-
31-2-
31*2-
31/2-
31+2*
31-2*
31*2*
31/2*
31+2/
31-2/
31*2/
31/2/
312++
312-+
312*+
312/+
312+-
312--
312*-
312/-
312+*
312-*
312**
312/*
312+/
312-/
312*/
312//
32+1+
32-1+
32*1+
32/1+
32+1-
32-1-
32*1-
32/1-
32+1*
32-1*
32*1*
32/1*
32+1/
32-1/
32*1/
32/1/
321++
321-+
321*+
321/+
321+-
321--
321*-
321/-
321+*
321-*
321**
321/*
321+/
321-/
321*/
321//https://stackoverflow.com/questions/59603526
复制相似问题
腾讯云开发者
