如何高效生成结果为指定值的算术表达式？

有一款数字填运算符的游戏：给出若干空位（用_表示），部分已填数字，需要填入+、-、*、/等数学运算符，让整个表达式的计算结果等于指定值。例如：

• 9 _ 1 = 10 → 填入+得到9+1=10
• 5 _ 2 = 10 → 填入*得到5*2=10
• 3 _ 2 _ 2 = 10 → 填入*和+得到3*2+2=10

现在需要实现一个函数GenerateExpressions(operatorsCount, result)，动态生成所有满足条件的表达式，而非手动编写：

• 传入operatorsCount=3、result=42时，返回形如N o N o N o N的表达式列表（o为运算符，N是1-9的数字），且表达式计算结果为42；
• 传入operatorsCount=4、result=10时，返回形如N o N o N o N o N的表达式列表，计算结果为10。

最初用嵌套循环暴力枚举所有可能等式并校验，出现内存溢出；改成递归后不再溢出，但效率极低，目前用DataTable.Compute计算表达式结果。现有递归代码如下：

public static List<string> GenerateExpressions(int count)
{
    List<string> expressions = new List<string>();
    List<string> numbers = new List<string> { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
    List<string> operators = new List<string> { "+", "-", "*", "/" };

    for (int i = 0; i < numbers.Count; i++)
    {
        GenerateExpressionsHelper(expressions, numbers, operators, count, numbers[i]);
    }
    return expressions;
}

static void GenerateExpressionsHelper(List<string> expressions, List<string> numbers, List<string> operators, int count, string currentExpression)
{
    if (count == 0)
    {
        // 如果用完所有运算符，将表达式加入列表
        expressions.Add(currentExpression);
        return;
    }

    for (int i = 0; i < operators.Count; i++)
    {
        for (int j = 0; j < numbers.Count; j++)
        {
            // 递归调用，减少一个运算符配额，拼接当前运算符和数字
            GenerateExpressionsHelper(expressions, numbers, operators, count - 1, currentExpression + operators[i] + numbers[j]);
        }
    }
}

请问如何优化该方案，高效生成符合要求的表达式？

1. 递归过程中同步计算中间结果，避免无效表达式生成 #

当前代码是先生成所有表达式再校验，属于纯暴力枚举。可以在递归时同步计算中间结果，一旦发现后续无论怎么组合都无法达到目标值，直接终止该递归分支（剪枝）。

核心思路是维护两个关键变量：

• total：当前表达式的总结果（已处理完优先级运算后的结果）
• term：当前最后一个可参与乘除运算的项（因为乘除优先级高于加减，需要单独维护）

每一步递归根据运算符更新这两个变量，同时判断是否还有可能达到目标值，避免无意义的递归。

2. 替换DataTable.Compute为自定义运算逻辑 #

DataTable.Compute是为数据库查询设计的，解析字符串的开销极大。改用递归时同步计算的方式，完全不需要生成字符串后再解析，能节省大量性能开销。

3. 剪枝优化，减少无效分支 #

根据目标值和当前中间结果，提前终止不可能的分支：

• 计算剩余步骤能达到的最大/最小可能值，如果目标值不在这个范围内，直接跳过该分支；
• 除法操作提前过滤除数为0、无法整除的情况（如果要求结果为整数）。

4. 减少字符串拼接开销 #

递归中频繁的字符串拼接会产生大量临时对象，改用StringBuilder拼接，或仅在满足条件时生成最终表达式字符串。

public static List<string> GenerateExpressions(int operatorsCount, int result)
{
    List<string> expressions = new List<string>();
    List<char> operators = new List<char> { '+', '-', '*', '/' };
    
    // 从第一个1-9的数字开始递归
    for (int num = 1; num <= 9; num++)
    {
        GenerateHelper(operatorsCount - 1, result, num, num, num.ToString(), operators, expressions);
    }
    return expressions;
}

static void GenerateHelper(int remainingOps, int target, int total, int term, string currentExpr, List<char> operators, List<string> result)
{
    if (remainingOps == 0)
    {
        if (total == target)
        {
            result.Add(currentExpr);
        }
        return;
    }

    foreach (char op in operators)
    {
        for (int num = 1; num <= 9; num++)
        {
            int newTotal = total;
            int newTerm = term;
            bool isValid = true;

            // 根据运算符更新总结果和当前项
            switch (op)
            {
                case '+':
                    newTotal += newTerm;
                    newTerm = num;
                    break;
                case '-':
                    newTotal += newTerm;
                    newTerm = -num;
                    break;
                case '*':
                    newTerm *= num;
                    break;
                case '/':
                    // 过滤除数为0、无法整数整除的情况
                    if (num == 0 || term % num != 0)
                    {
                        isValid = false;
                        break;
                    }
                    newTerm /= num;
                    break;
            }

            if (!isValid)
                continue;

            // 剪枝：计算剩余步骤的最大/最小可能值，判断目标值是否在范围内
            int remainingSteps = remainingOps - 1;
            int maxPerStep = (int)Math.Pow(9, remainingSteps);
            int minPossible = newTotal + newTerm - maxPerStep;
            int maxPossible = newTotal + newTerm + maxPerStep;

            if (target < minPossible || target > maxPossible)
                continue;

            // 递归进入下一层
            GenerateHelper(remainingOps - 1, target, newTotal, newTerm, $"{currentExpr}{op}{num}", operators, result);
        }
    }
}

额外说明 #

• 如果游戏允许浮点数结果，可去掉除法中的term % num != 0判断，改用浮点数类型计算total和term；
• 剪枝逻辑可根据实际需求调整，比如更精准地计算上下限，进一步减少无效分支；
• 该代码生成的表达式均为唯一组合，无需额外去重。

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