基于双向链表实现栈的括号匹配代码无输出问题求助

核心问题分析 #

你的代码无法运行或输出异常，主要由以下几个关键问题导致：

• pop函数空指针解引用：当栈只剩最后一个元素时，(*top)->next为NULL，此时执行((*top)->next)->prev = NULL会直接触发崩溃。
• pop函数无有效返回值：栈空时函数未返回明确值，调用后会读取随机内存值，引发未定义行为。
• print函数遍历不完整：循环条件ptr->next != NULL会跳过最后一个节点，无法完整打印栈内容。
• isFull函数内存泄漏：每次调用都会malloc一个节点但不释放，长期运行会耗尽内存。
• 括号匹配逻辑未处理pop失败场景：遇到右括号时若栈为空，pop返回的随机值会导致匹配判断错误。

修正后的完整代码 #

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

struct node
{
    char data;
    struct node *next;
    struct node *prev;
}*top = NULL;

int isFull()
{
    struct node *n = (struct node *)malloc(sizeof(struct node));
    if (n == NULL)
    {
        return 1;
    }
    else
    {
        free(n); // 释放临时节点，避免内存泄漏
        return 0;
    }
}

int isEmpty(struct node *top)
{
    return top == NULL; // 简化逻辑判断
}

struct node *push(struct node *top, char val)
{
    if (isFull())
    {
        printf("Stack overflowed!\n");
        return top; // 栈满时返回原指针，避免丢失栈状态
    }
    struct node *ptr = (struct node *)malloc(sizeof(struct node));
    ptr->data = val;
    ptr->prev = NULL;
    ptr->next = top;
    if (top != NULL)
    {
        top->prev = ptr;
    }
    top = ptr;
    return top;
}

char pop(struct node **top)
{
    if (isEmpty(*top))
    {
        printf("Stack Underflowed!\n");
        return '\0'; // 返回特殊字符标识弹出失败
    }
    struct node *ptr = *top;
    char x = ptr->data;
    *top = ptr->next;
    if (*top != NULL) // 仅当新栈顶存在时，修改其prev指针
    {
        (*top)->prev = NULL;
    }
    free(ptr);
    return x;
}

void print(struct node *start)
{
    struct node *ptr = start;
    while (ptr != NULL) // 修改循环条件，遍历所有节点
    {
        printf("%c ", ptr->data);
        ptr = ptr->next;
    }
    printf("\n");
}

int match(char a, char b)
{
    return (a == '{' && b == '}') || 
           (a == '[' && b == ']') || 
           (a == '(' && b == ')'); // 简化匹配逻辑
}

int parenthesis(struct node *top, char *str)
{
    char popped_char;
    for (int i = 0; str[i] != '\0'; i++)
    {
        if (str[i] == '{' || str[i] == '[' || str[i] == '(')
        {
            top = push(top, str[i]);
        }
        else if (str[i] == '}' || str[i] == ']' || str[i] == ')')
        {
            popped_char = pop(&top);
            // 检查弹出是否失败，或匹配是否成功
            if (popped_char == '\0' || !match(popped_char, str[i]))
            {
                return 0;
            }
        }
    }
    return isEmpty(top); // 栈空则匹配成功
}

int main()
{
    char *str = (char*)malloc(100*sizeof(char));
    if (str == NULL) // 检查内存分配是否成功
    {
        printf("Memory allocation failed!\n");
        return 1;
    }
    printf("Enter the string\n");
    scanf("%s", str);
    if (parenthesis(top, str))
    {
        printf("Parenthesis Matched!\n");
    }
    else
    {
        printf("Parenthesis did not match!\n");
    }
    free(str); // 释放字符串内存，避免泄漏
    return 0;
}

关键修复点说明 #

1. pop函数：增加新栈顶的非空判断，避免空指针解引用；栈空时返回'\0'，调用处可识别弹出失败。
2. isFull函数：释放临时malloc的节点，解决内存泄漏问题。
3. print函数：修正循环条件，确保所有栈节点都被打印。
4. push函数：合并空栈与非空栈的处理逻辑，栈满时返回原指针，避免丢失栈状态。
5. 括号匹配逻辑：增加pop失败的判断，遇到右括号时若栈为空直接返回不匹配。
6. main函数：增加内存分配失败的检查，使用完字符串后释放内存，避免泄漏。

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