如何修正24点游戏C程序，使其输出带正确括号的合规解

问题描述 #

现有一段实现24点游戏的C语言代码，功能是接收4个1-10范围内的数字，通过*、/、+、-四种运算符组合运算得到结果24。程序当前通过生成数字全排列，结合递归尝试所有运算组合来求解，但输出格式不符合运算优先级要求：输入1 2 4 6时，期望输出(2-1)*4*6，实际却输出1 - 2 * 4 * 6，需要修正程序使其输出符合运算优先级的带括号正确表达式。

原代码 #

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int flag = 0;
char myArr[3];
int myChar;
int changeEl[4];

void swap(int *a, int *b) {
  int h = (*a);
  (*a) = (*b);
  (*b) = h;
}

void Cal24 (int arr[4], int pointer, int sum, char myArr[3], char ch, int charrpoint) {
  if (pointer != 0) {
    myArr[pointer - 1] = ch;
  }
  
  if (sum == 24 && pointer == 3) {
    for (int i = 0; i < 4;  i++) {
      printf("%d", changeEl[i]);
      if (i < 3) {
        printf(" %c ", myArr[i]);
      }
    }
    flag = 1;
    return;
  }
 
  
  if (pointer <= 3 && flag == 0) {
    Cal24(arr, pointer+1, sum * arr[pointer+1], myArr, '*', charrpoint);
    Cal24(arr, pointer+1, sum + arr[pointer+1], myArr, '+', charrpoint);
    if (sum >= arr[pointer+1]) {
      Cal24(arr, pointer+1, sum - arr[pointer+1], myArr, '-', charrpoint);
    } else {
      Cal24(arr, pointer+1, arr[pointer+1] - sum, myArr, '-', charrpoint + 1);
    }
    if (sum >= arr[pointer + 1] && sum % arr[pointer + 1] == 0) {
      Cal24(arr, pointer+1, sum / arr[pointer+1], myArr, '/', charrpoint);
    } else if (sum < arr[pointer + 1] && arr[pointer + 1] % sum == 0){
      Cal24(arr, pointer+1, arr[pointer+1] / sum, myArr, '/', charrpoint);
    }
  }
}

void permute(int index, int *arr) {
  if (index == 4 && flag == 0) {
      for (int a = 0; a < 4; a++) {
        changeEl[a] = arr[a];
      }
    Cal24(arr, 0, arr[0], myArr, myChar, 0);
  }
  
  for (int i = index; i < 4; i++) {
    swap(arr + index, arr + i);
    permute(index + 1, arr);
    swap(arr + index, arr + i);
  }
}

int main(int argc, const char * argv[]) {
  int num, arr[4];

  for (int i = 0; i < 4; i++) {
    scanf("%d", &num);
    arr[i] = num;
  }
  
  permute(0, arr);
  
  if (flag == 0) {
    printf("NO SOLUTIONS");
  }
  printf("\n");
  return 0;
}

修正思路 #

原程序的核心问题是仅记录了数字顺序和运算符，没有跟踪运算的结合逻辑与优先级，导致无法正确添加括号。修正方案需要：

• 递归过程中跟踪当前的表达式字符串，而非仅跟踪运算结果
• 记录每个表达式的运算符优先级，用于判断是否需要为子表达式添加括号
• 处理减法、除法的顺序问题，生成符合运算逻辑的表达式

修改后的代码 #

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int flag = 0;

// 定义运算符优先级：*、/ 优先级为2，+、- 优先级为1
int get_priority(char op) {
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0; // 单个数字的优先级最高
}

// 给表达式添加括号（当需要时）
void wrap_expression(char *result, const char *expr, int expr_prio, int parent_prio) {
    if (expr_prio < parent_prio) {
        sprintf(result, "(%s)", expr);
    } else {
        strcpy(result, expr);
    }
}

void swap(int *a, int *b) {
    int h = *a;
    *a = *b;
    *b = h;
}

// 递归函数：跟踪当前表达式、当前结果、当前步骤
void Cal24(int arr[4], int step, int current_val, char current_expr[], int expr_prio) {
    // 完成3次运算，检查是否等于24
    if (step == 3) {
        if (current_val == 24) {
            printf("%s\n", current_expr);
            flag = 1;
        }
        return;
    }

    if (flag) return; // 找到解后直接返回

    for (int i = step + 1; i < 4; i++) {
        // 交换数字，模拟不同的运算顺序
        swap(&arr[step + 1], &arr[i]);

        int next_val;
        char next_expr[100];
        char temp_expr[50];
        char num_str[10];
        sprintf(num_str, "%d", arr[step + 1]);

        // 乘法
        next_val = current_val * arr[step + 1];
        wrap_expression(temp_expr, current_expr, expr_prio, get_priority('*'));
        sprintf(next_expr, "%s*%s", temp_expr, num_str);
        Cal24(arr, step + 1, next_val, next_expr, get_priority('*'));
        if (flag) { swap(&arr[step + 1], &arr[i]); return; }

        // 加法
        next_val = current_val + arr[step + 1];
        wrap_expression(temp_expr, current_expr, expr_prio, get_priority('+'));
        sprintf(next_expr, "%s+%s", temp_expr, num_str);
        Cal24(arr, step + 1, next_val, next_expr, get_priority('+'));
        if (flag) { swap(&arr[step + 1], &arr[i]); return; }

        // 减法：current_val - arr[step+1]
        next_val = current_val - arr[step + 1];
        wrap_expression(temp_expr, current_expr, expr_prio, get_priority('-'));
        sprintf(next_expr, "%s-%s", temp_expr, num_str);
        Cal24(arr, step + 1, next_val, next_expr, get_priority('-'));
        if (flag) { swap(&arr[step + 1], &arr[i]); return; }

        // 减法：arr[step+1] - current_val
        next_val = arr[step + 1] - current_val;
        wrap_expression(temp_expr, num_str, get_priority('-'), get_priority('-'));
        sprintf(next_expr, "%s-%s", temp_expr, current_expr);
        Cal24(arr, step + 1, next_val, next_expr, get_priority('-'));
        if (flag) { swap(&arr[step + 1], &arr[i]); return; }

        // 除法：current_val / arr[step+1]（确保整除）
        if (arr[step + 1] != 0 && current_val % arr[step + 1] == 0) {
            next_val = current_val / arr[step + 1];
            wrap_expression(temp_expr, current_expr, expr_prio, get_priority('/'));
            sprintf(next_expr, "%s/%s", temp_expr, num_str);
            Cal24(arr, step + 1, next_val, next_expr, get_priority('/'));
            if (flag) { swap(&arr[step + 1], &arr[i]); return; }
        }

        // 除法：arr[step+1] / current_val（确保整除）
        if (current_val != 0 && arr[step + 1] % current_val == 0) {
            next_val = arr[step + 1] / current_val;
            wrap_expression(temp_expr, num_str, get_priority('/'), get_priority('/'));
            sprintf(next_expr, "%s/%s", temp_expr, current_expr);
            Cal24(arr, step + 1, next_val, next_expr, get_priority('/'));
            if (flag) { swap(&arr[step + 1], &arr[i]); return; }
        }

        // 回溯交换
        swap(&arr[step + 1], &arr[i]);
    }
}

void permute(int index, int *arr) {
    if (index == 4) {
        if (flag) return;
        char init_expr[10];
        sprintf(init_expr, "%d", arr[0]);
        Cal24(arr, 0, arr[0], init_expr, 3); // 单个数字优先级设为3（最高）
        return;
    }

    // 去重排列，避免重复计算相同数字的排列
    int used[11] = {0};
    for (int i = index; i < 4; i++) {
        if (used[arr[i]]) continue;
        used[arr[i]] = 1;
        swap(&arr[index], &arr[i]);
        permute(index + 1, arr);
        swap(&arr[index], &arr[i]);
        if (flag) return;
    }
}

int main() {
    int arr[4];
    printf("输入4个1-10的数字：");
    for (int i = 0; i < 4; i++) {
        scanf("%d", &arr[i]);
    }

    permute(0, arr);

    if (!flag) {
        printf("NO SOLUTIONS\n");
    }
    return 0;
}

关键修改说明 #

1. 表达式跟踪：递归函数不再仅传递运算结果，而是传递当前的表达式字符串，以及该表达式的运算符优先级，用于判断是否需要添加括号。
2. 括号逻辑：通过wrap_expression函数，当子表达式的优先级低于父运算符时，自动给子表达式添加括号，保证运算顺序正确。
3. 减法/除法处理：分别处理两种顺序的减法和除法，生成符合逻辑的表达式，比如(2-1)而非1-2（当需要用大数减小数得到正数时）。
4. 去重排列：在全排列中加入去重逻辑，避免对相同数字的重复排列进行计算，提升效率。

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