嵌套数组多层求和的C语言实现问题求助

问题核心 #

需要计算嵌套数组的累加和，规则为从最内层数组开始求和，再将结果与外层数组元素累加（例如{1, {2, 3}}的结果为1 + (2+3) = 6）。

思路分析 #

• 动态规划不适用：DP针对有重叠子问题、最优子结构的场景，而嵌套数组求和是线性的嵌套展开，无重复子问题需要复用，因此栈的思路更直接匹配需求。
• 栈实现的合理性：遇到{时入栈标记，遇到数字暂存，遇到}时计算当前栈内数字的和，再将该和作为新元素压入外层栈，完全契合“从内到外累加”的规则。

代码优化建议 #

假设你采用字符串栈的实现思路，这里给出几个关键优化方向：

1. 替换字符串栈为数值栈
   无需存储字符串，直接用数值栈+特殊标记（比如INT_MIN表示{），避免重复的字符串转数字操作，大幅提升效率。
2. 简化字符处理逻辑
   • 遍历输入时直接跳过空格和逗号；
   • 遇到{压入标记值，遇到数字时完整读取多位数后压栈；
   • 遇到}时弹出元素直到标记值，计算和后将结果压回栈。
3. 完善内存管理
   手动实现栈时需添加扩容逻辑避免溢出，使用完毕后及时释放内存。

示例实现框架 #

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <limits.h>

#define INIT_STACK_SIZE 10

typedef struct {
    int* data;
    int top;
    int capacity;
} Stack;

Stack* create_stack() {
    Stack* stack = malloc(sizeof(Stack));
    stack->data = malloc(INIT_STACK_SIZE * sizeof(int));
    stack->top = -1;
    stack->capacity = INIT_STACK_SIZE;
    return stack;
}

void expand_stack(Stack* stack) {
    stack->capacity *= 2;
    stack->data = realloc(stack->data, stack->capacity * sizeof(int));
}

void push(Stack* stack, int val) {
    if (stack->top == stack->capacity - 1) {
        expand_stack(stack);
    }
    stack->data[++stack->top] = val;
}

int pop(Stack* stack) {
    return stack->data[stack->top--];
}

int is_empty(Stack* stack) {
    return stack->top == -1;
}

void free_stack(Stack* stack) {
    free(stack->data);
    free(stack);
}

int calculate_nested_sum(const char* s) {
    Stack* stack = create_stack();
    int num = 0;
    int in_num = 0;

    for (int i = 0; s[i] != '\0'; i++) {
        if (isspace(s[i]) || s[i] == ',') {
            if (in_num) {
                push(stack, num);
                num = 0;
                in_num = 0;
            }
            continue;
        }
        if (s[i] == '{') {
            push(stack, INT_MIN); // 用INT_MIN标记左括号
            continue;
        }
        if (s[i] == '}') {
            if (in_num) {
                push(stack, num);
                num = 0;
                in_num = 0;
            }
            int sum = 0;
            int val;
            while ((val = pop(stack)) != INT_MIN) {
                sum += val;
            }
            push(stack, sum);
            continue;
        }
        // 处理多位数
        in_num = 1;
        num = num * 10 + (s[i] - '0');
    }

    int result = pop(stack);
    free_stack(stack);
    return result;
}

int main() {
    // 测试示例
    const char* test1 = "{1, {2, 3}}";
    printf("Test 1: %d\n", calculate_nested_sum(test1)); // 输出6

    const char* test2 = "{{1,2}, {3,4}}";
    printf("Test 2: %d\n", calculate_nested_sum(test2)); // 输出10

    const char* test3 = "{1, {2, {3, 4}}}";
    printf("Test 3: %d\n", calculate_nested_sum(test3)); // 输出10

    return 0;
}

额外注意事项 #

• 上述代码假设输入格式合法（无括号不匹配、非法字符等），若需处理异常输入，需添加错误判断（如栈空时pop、遇到未知字符等）；
• 如需支持负数，需增加-字符的处理逻辑，标记负数后对后续数字取反；
• 若嵌套深度极大，可改用链表实现栈，避免固定容量的限制。

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