C语言 | Leetcode C语言题解之第282题给表达式添加运算符

题目：

题解：

#define MAX_COUNT 10000 // 解的个数足够大
#define NUM_COUNT 100 // 操作数的个数足够大
long long num[NUM_COUNT] = {0};long long calc(char *a)
{ // 计算表达式a的值// 将数字和符号，入栈memset(num, 0, sizeof(num));int numCnt = 0, opCnt = 0;long long value = 0;char oper = '+';int len = strlen(a);for (int i = 0; i < len; i++) {if (a[i] == '0') { // 05这种以0开头的数字不符合要求if (i < len - 1 && isdigit(a[i+1])) {return INT_MIN; // 发现格式不对，直接返回}}if (isdigit(a[i])) {for (; isdigit(a[i]); i++) { // 计数数值value = value * 10 + (a[i] - '0');}}if (!isdigit(a[i]) || i == len -1) {switch(oper) {case '+':num[numCnt++] = value;break;case '-':num[numCnt++] = -value;break;case '*':value *= num[numCnt - 1];num[numCnt - 1] = value;break;default:return INT_MIN; // 发现格式不对，直接返回}value = 0;oper = a[i];} }value = num[numCnt - 1];for (numCnt--; numCnt > 0; numCnt--) {value += num[numCnt - 1];}return value;
}char* newStr(char *a, int len, int pos, const char*op)
{char *t = (char*)calloc(sizeof(char), len);strncpy(t, a, pos); // 前段strcat(t, op); // 符号strcat(t, a + pos); // 后段return t;
}void dfs(char *a, int pos, int target, char**p, int* returnSize)
{if (a == NULL || a[0] == 0 || p == NULL || returnSize == NULL) {return;} int len = strlen(a);if (pos >= len) { // 符号已经加全了if (target == calc(a)) { // 符合if (*returnSize > MAX_COUNT) {printf("overflow\n");return;}p[*returnSize] = a;(*returnSize)++;} else { // 不符合，丢掉free(a);}} else {char *a1 = newStr(a, len + 2, pos, "*"); // *号char *a2 = newStr(a, len + 2, pos, "+"); // +号char *a3 = newStr(a, len + 2, pos, "-"); // -号dfs(a1, pos + 2, target, p, returnSize); // *号dfs(a2, pos + 2, target, p, returnSize); // +号dfs(a3, pos + 2, target, p, returnSize); // -号dfs(a, pos + 1, target, p, returnSize); // 不加符号}
}char **addOperators(char *a, int target, int* returnSize)
{if (a == NULL || returnSize == NULL) {return NULL;}char **p = (char**)calloc(MAX_COUNT, sizeof(char*));if (p == NULL) {return NULL;}*returnSize = 0;dfs(strdup(a), 1, target, p, returnSize);return p;
}