C语言编程实战：每日一题：有效的括号

在这里插入图片描述

🌈这里是say-fall分享，感兴趣欢迎三连与评论区留言 🔥专栏： 《C语言从零开始到精通》 《C语言编程实战》 《数据结构与算法》 《小游戏与项目》 💪格言：做好你自己，你才能吸引更多人，并与他们共赢，这才是你最好的成长方式。

题目：有效的括号

• LeetCode：有效的括号

在这里插入图片描述

一、题目背景与核心考点

1. 题目意义

“有效的括号”是LeetCode简单难度经典题目，也是面试高频题。它看似基础，却能全面考察对栈数据结构的理解、字符串遍历技巧、边界条件处理能力，同时涉及内存安全（避免内存泄漏）等工程化细节。

2. 核心考点

• 栈的“先进后出（LIFO）”特性应用；
• 字符串逐字符遍历与条件判断；
• 边界案例（空字符串、单边括号、不匹配括号、嵌套括号）处理；
• 数据结构的初始化与销毁（内存安全）。

二、思路解析

利用栈 “先进后出（LIFO）” 的特性，将左括号作为“前驱标记”压栈，遇到右括号时与栈顶左括号校验匹配性，核心逻辑如下：

1. 核心逻辑拆解

假设输入字符串为 "({[]})"，遍历过程如下：

遍历结束后栈为空，返回 true（有效）。

2. 分情况详细说明

1. 左括号处理：遍历字符串，遇到任意左括号（( { [），直接压入栈中——栈中存储的是“等待匹配的左括号”，后续需通过右括号“消解”；
2. 右括号处理：遇到右括号时，需分3种临界情况判断：
   • 栈为空：说明当前右括号没有对应的左括号（如输入 ")()" "}}{"），直接返回 false；
   • 栈顶左括号与当前右括号匹配（'('→')'、'{'→'}'、'['→']'）：弹出栈顶左括号（表示匹配成功，消解一个左括号），继续遍历；
   • 栈顶左括号与当前右括号不匹配（如 '(' 对应 ']'、'{' 对应 ')'）：括号结构无效，返回 false；
3. 遍历结束后校验：
   • 栈为空：所有左括号都被右括号匹配消解，返回 true；
   • 栈非空：存在未被匹配的左括号（如输入 "(()" "{[}"），返回 false；
4. 内存安全： 代码中所有分支（返回 true 或 false 前）都调用了 StackDestroy，目的是释放栈在堆上申请的内存，避免内存泄漏——这是C语言编程中容易忽略的工程化细节，尤其在多次调用该函数时，内存泄漏会累积影响程序性能。

3. 栈的核心作用

为什么选择栈？因为括号匹配具有“嵌套依赖”特性：最内层的左括号需要最先被最内层的右括号匹配（如 ({}) 中，{ 必须先与 } 匹配，再让 ( 与 ) 匹配），这与栈“先进后出”的特性完全契合——后压入的左括号（内层）先弹出匹配。

三、栈的实现

这里不在代码中展示栈的代码，有想了解的可以点击 栈：源代码

栈实现说明

• 采用顺序栈（数组存储），效率高于链式栈（无需额外存储指针）；
• 加入扩容机制：初始容量为4，栈满时自动扩容2倍，适配长字符串场景；
• 加入assert断言：避免空指针、空栈出栈/取顶等非法操作，便于调试；
• 严格遵循“初始化→使用→销毁”流程，确保内存安全。

四、题目代码

//有效的括号
bool isValid(char* s)
{
    Stack st;
    StackInit(&st); // 初始化栈
    while (*s) // 遍历字符串（*s不为'\0'时继续）
    {
        // 左括号：直接压栈，等待后续右括号匹配
        if (*s == '(' || *s == '{' || *s == '[')
        {
            StackPush(&st, *s);
        }
        // 右括号：校验匹配性
        else
        {
            // 情况1：栈为空，无对应左括号
            if (StackEmpty(&st) == 1)
            {
                StackDestroy(&st); // 释放内存
                return false;
            }
            // 情况2：栈顶左括号与当前右括号匹配，弹出栈顶
            if (StackTop(&st) == '(' && *s == ')' ||
                StackTop(&st) == '{' && *s == '}' ||
                StackTop(&st) == '[' && *s == ']')
            {
                StackPop(&st);
            }
            // 情况3：括号不匹配
            else
            {
                StackDestroy(&st); // 释放内存
                return false;
            }
        }
        s++; // 指针移动到下一个字符
    }
    // 遍历结束：栈非空表示有未匹配的左括号
    if (StackEmpty(&st) != 1)
    {
        StackDestroy(&st); // 释放内存
        return false;
    }
    // 所有括号匹配成功
    StackDestroy(&st); // 释放内存
    return true;
}

五、复杂度分析

1. 时间复杂度：O(n)

• 字符串遍历：每个字符仅遍历一次，时间复杂度O(n)（n为字符串长度）；
• 栈操作：入栈（StackPush）、出栈（StackPop）、取顶（StackTop）均为O(1)操作（顺序栈通过数组索引访问，无循环）；
• 扩容操作：最坏情况下扩容次数为O(log n)（每次扩容2倍），总扩容时间为O(n)（所有元素重新拷贝的总次数为n），不影响整体O(n)复杂度。

2. 空间复杂度：O(n)

• 最坏情况：输入字符串全为左括号（如 "((((("），栈需存储所有左括号，空间复杂度O(n)；
• 最优情况：输入字符串为空或有效匹配（如 "()"），空间复杂度O(1)（空栈或栈内元素最多为1）。

六、常见误区

• 忘记处理空字符串：输入""时，代码遍历不执行，栈为空，返回true（正确），但新手可能误判为空串无效；
• 忽略内存泄漏：未在所有分支调用StackDestroy，导致栈内存无法释放；
• 空栈取顶/出栈：未判断StackEmpty就调用StackTop或StackPop，导致程序崩溃（原文通过StackEmpty判断避免了该问题）；
• 括号匹配逻辑写错：如将'('与']'误判为匹配，需严格对应三种括号的配对关系。

七、总结

1. 题目总结

“有效的括号”是栈数据结构的经典应用，核心是利用“先进后出”特性解决括号的嵌套匹配问题。代码逻辑清晰，需重点关注：

• 边界条件（空串、空栈、括号不匹配）的全面处理；
• 内存安全（栈的初始化与销毁）；
• 时间/空间复杂度的平衡。

2. 拓展应用

栈的“先进后出”特性还适用于以下场景：

• 表达式求值（如后缀表达式转换、四则运算括号优先级处理）；
• 函数调用栈（程序执行时的函数调用顺序管理）；
• 括号相关变种题目（如“最长有效括号”“删除无效括号”）；
• 字符串解码（如LeetCode 394："3[a2[bc]]" 解码为 "abcbcabcbcabcbc"）。

• 本节完…