递归+栈生成有效括号仅输出首个结果的问题排查

问题描述 #

给定n对括号，编写函数生成所有有效括号组合。

实现方案（C语言） #

我采用递归方式实现了gen_para函数，通过栈构建有效括号序列，当序列完整时打印，再通过递归弹出栈元素探索其他可能序列：

void gen_para(Stack* s, int n, int opened, int closed) { // recursive
    if (n == opened && n == closed) {
        print_s(s);
        // clear_s(s);
    }
    else if (opened < n) {
        push(s, '(');
        gen_para(s, n, opened + 1, closed);
        pop(s);
    }
    else if (closed < opened) {
        push(s, ')');
        gen_para(s, n, opened, closed + 1);
        pop(s);
    }
}

以下是完整的栈实现代码：

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

typedef struct Node {
    char data;
    struct Node* next;
} Node;

typedef struct Stack {
    char size;
    Node* head;
    Node* tail;
} Stack;

const Stack stack_init = { .size = 0, .head = NULL, .tail = NULL };

Node* create_node(char elm) {
    Node* node = malloc(sizeof * node);
    if (!node) return node;
    node->data = elm;
    node->next = NULL;
    return node;
}

Stack* create_stack() {
    Stack* s = malloc(sizeof * s);
    s->size = 0;
    s->head = NULL;
    s->tail = NULL;
    return s;
}

int is_empty_s(Stack *s) {
    return s->tail == NULL;
}

void push(Stack *s, char elm) {
    Node* updated_head = create_node(elm);
    if (!s->head) {
        s->head = updated_head;
        s->tail = s->head;
    } else {
        updated_head->next = s->head;
        s->head = updated_head;
    }
    s->size++;
}

char pop(Stack *s) {
    if (!is_empty_s(s)) {
        Node* node = s->head;
        char elm = node->data;
        s->head = s->head->next;
        if (!s->head)
            s->tail = NULL;
        s->size--;
        free(node);
        return elm;
    }
    return 'N';
    
}

char top(Stack *s) {
    char top;
    if (s->head)
        top = s->head->data;
    else
        top = 'N';
    return top;
}

void clear_s(Stack *s) {
    while (s->tail)
        pop(s);
}

Stack* reverse_it(Stack *s) {
    Stack *s2 = malloc(sizeof *s2);
    if (!s2) return s2;
    *s2 = stack_init;

    while (s->tail)
        push(s2, pop(s));
    s->head = s2->head;
    return s;
}

void print_s(Stack *s) { 
    if (!is_empty_s(s)) {
        char data = pop(s);
        // or place here instead printf("%c", data); if you want to print the other way
        print_s(s);
        printf("%c", data);
        push(s, data);
    }
}

int main() {
    Stack s1 = stack_init;
    int n = 2;
    gen_para(&s1, n, 0, 0);
    return 0;
}

遇到的问题 #

当n=2时，预期输出为(())和()()，但实际仅输出第一个结果。排查发现生成第二个序列的递归调用前栈是空的，无法定位问题。

问题原因与解决方法 #

问题核心在gen_para的分支判断逻辑：你用else if处理closed < opened的情况，这导致只有当opened < n不成立时，才会进入添加右括号的分支。但实际上，即使opened < n成立，只要closed < opened，我们也需要尝试添加右括号——这才是遍历所有有效路径的关键。

举个具体场景：当n=2，栈内已有一个(（此时opened=1，closed=0），opened < n条件成立，原代码只会进入添加左括号的分支，完全漏掉了添加右括号生成()()的路径。

修改方式很简单，把两个else if改成独立的if，让两个分支可以并行判断：

void gen_para(Stack* s, int n, int opened, int closed) { // recursive
    if (n == opened && n == closed) {
        print_s(s);
        printf("\n"); // 可选：添加换行让输出更清晰
        // clear_s(s);
    }
    if (opened < n) { // 去掉else，改为独立if
        push(s, '(');
        gen_para(s, n, opened + 1, closed);
        pop(s);
    }
    if (closed < opened) { // 去掉else，改为独立if
        push(s, ')');
        gen_para(s, n, opened, closed + 1);
        pop(s);
    }
}

另外，原print_s函数打印时没有换行，两个结果会连在一起，建议添加换行来区分不同序列。

修改后程序即可正确生成所有有效括号组合。

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