C语言编程--17.有效的括号

题目：

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([])”
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

代码：

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

// 定义链表节点结构体
// 每个节点包含一个字符数据和一个指向下一个节点的指针
typedef struct Node
{
    char data;  // 存储字符数据
    struct Node *next;  // 指向下一个节点的指针
} Node;

// 定义栈结构体
// 栈使用链表实现，top 指针指向栈顶节点
typedef struct
{
    Node* top;  // 栈顶指针
} Stack;

// 初始化栈
// 该函数将栈的 top 指针置为 NULL，表示栈为空
void initStack(Stack* s)
{
    s->top = NULL;  // 将栈顶指针置为 NULL
}

// 判断栈是否为空
// 如果栈的 top 指针为 NULL，则栈为空，返回 1；否则返回 0
int isEmpty(Stack* s)
{
    return s->top == NULL;  // 判断栈顶指针是否为 NULL
}

// 入栈操作
// 该函数将一个字符压入栈中
void push(Stack* s, char value)
{
    // 为新节点分配内存
    Node* newnode = (Node*)malloc(sizeof(Node));
    if (newnode == NULL)
    {
        // 内存分配失败，输出错误信息
        printf("内存分配失败！");
        return;
    }
    newnode->data = value;  // 将数据存入新节点
    newnode->next = s->top;  // 新节点的 next 指针指向原栈顶节点
    s->top = newnode;  // 更新栈顶指针为新节点
}

// 出栈操作
// 该函数将栈顶元素弹出
void pop(Stack* s)
{
    if (isEmpty(s))
    {
        // 栈为空，输出错误信息
        printf("栈为空");
        return;
    }
    Node* temp = s->top;  // 临时指针指向栈顶节点
    char value = temp->data;  // 获取栈顶节点的数据
    s->top = s->top->next;  // 更新栈顶指针为原栈顶节点的下一个节点
    free(temp);  // 释放原栈顶节点的内存
}

// 判断字符串中的括号是否有效
// 该函数使用栈来检查字符串中的括号是否匹配
bool isValid(char* s) {
    Stack stack;
    initStack(&stack);  // 初始化栈
    int n = strlen(s);  // 获取字符串的长度
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            // 如果是左括号，直接入栈
            push(&stack, s[i]);
        else if (s[i] == ')' && stack.top && stack.top->data == '(')
            // 如果是右括号且栈不为空，并且栈顶元素是对应的左括号，则出栈
            pop(&stack);
        else if (s[i] == ']' && stack.top && stack.top->data == '[')
            // 如果是右括号且栈不为空，并且栈顶元素是对应的左括号，则出栈
            pop(&stack);
        else if (s[i] == '}' && stack.top && stack.top->data == '{')
            // 如果是右括号且栈不为空，并且栈顶元素是对应的左括号，则出栈
            pop(&stack);
        else
            // 其他情况，将字符入栈
            push(&stack, s[i]);
    }
    if (stack.top)
        // 如果栈不为空，说明有括号不匹配，返回 false
        return false;
    else
        // 如果栈为空，说明所有括号都匹配，返回 true
        return true; 
}

代码分析：

逻辑清晰：代码结构清晰，将栈的基本操作（初始化、入栈、出栈、判断是否为空）封装成独立的函数，提高了代码的可读性和可维护性。isValid 函数利用栈的特性来判断括号是否匹配，逻辑简洁明了。
内存管理：在入栈操作中，会检查内存分配是否成功，避免了因内存分配失败而导致的程序崩溃。在出栈操作中，会释放栈顶节点的内存，避免了内存泄漏。
扩展性：栈的实现使用链表，易于扩展。如果需要存储更多类型的数据，只需要修改 Node 结构体的 data 成员即可。