C语言递归实现数字串插运算符凑目标数的结果打印问题

现有代码核心问题梳理 #

• 递归逻辑仅支持二元运算，无法覆盖多运算符、多位数拼接的全场景
• 未设计运算路径存储结构，无法回溯生成可打印的表达式字符串
• 直接修改目标值的递归计算逻辑没有考虑乘法优先级，会导致运算结果计算错误
• 使用pow()计算整数位数存在浮点数精度误差，容易出现数字转换错误

完整实现代码 #

#include <stdio.h>
#include <string.h>
#define MAX_STR_LEN 11
#define MAX_EXP_LEN 50

// 全局变量统计匹配到的表达式数量，用来最后判断是否输出None
int match_count = 0;

/**
 * 递归函数
 * @param s 原始数字字符串
 * @param target 目标结果
 * @param start 当前处理的起始下标
 * @param current_exp 当前已经拼接好的表达式字符串
 * @param current_val 当前已经计算得到的总结果
 * @param last_val 上一个参与运算的数值，用来处理乘法优先级
 */
void dfs(char *s, int target, int start, char *current_exp, long long current_val, long long last_val) {
    int len = strlen(s);
    // 递归终止条件：已经遍历完所有数字
    if (start == len) {
        if (current_val == target) {
            printf("%s\n", current_exp);
            match_count++;
        }
        return;
    }
    long long num = 0;
    char num_str[20] = {0};
    char new_exp[MAX_EXP_LEN] = {0};
    // 从start开始，拼接1位到剩余所有位的数字
    for (int i = start; i < len; i++) {
        // 处理前导零的情况，如果第一位是0，后面不能再接数字，比如012是不合法的
        if (i > start && s[start] == '0') {
            break;
        }
        num = num * 10 + (s[i] - '0');
        // 把当前数字转成字符串
        sprintf(num_str, "%lld", num);
        // 如果是第一个数字，不需要加运算符
        if (start == 0) {
            strcpy(new_exp, num_str);
            dfs(s, target, i + 1, new_exp, num, num);
        } else {
            // 加运算符：+
            sprintf(new_exp, "%s+%s", current_exp, num_str);
            dfs(s, target, i + 1, new_exp, current_val + num, num);
            // 减运算符：-
            sprintf(new_exp, "%s-%s", current_exp, num_str);
            dfs(s, target, i + 1, new_exp, current_val - num, -num);
            // 乘运算符：*，需要修正优先级，比如a + b * c = (a + b) - b + b * c
            sprintf(new_exp, "%s*%s", current_exp, num_str);
            dfs(s, target, i + 1, new_exp, current_val - last_val + last_val * num, last_val * num);
        }
    }
}

int main() {
    char s[MAX_STR_LEN];
    int target;
    char init_exp[MAX_EXP_LEN] = {0};
    scanf("%s %d", s, &target);
    dfs(s, target, 0, init_exp, 0, 0);
    if (match_count == 0) {
        printf("None\n");
    }
    return 0;
}

核心逻辑说明 #

• 递归过程中实时拼接表达式字符串，每选一个运算符和数字就更新一次表达式
• 引入last_val参数处理乘法优先级，避免运算结果错误
• 自动过滤前导零的不合法数字拼接（比如不会出现1+02这种表达式）
• 使用整数运算拼接数字，避免pow()的浮点数精度问题
• 用全局变量计数匹配到的表达式，遍历结束后如果计数为0直接输出None

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