你好，同学。欢迎来到数据结构基础训练。今天我们要讨论的是计算机科学中一个极其经典的问题，它不仅是编译器语法检查的核心逻辑，也是理解 栈（Stack） 这一数据结构最直观的案例。

---

一、 预备知识点

在解决本题前，请确保你已经掌握：

1. 栈（Stack）的逻辑：后进先出（LIFO）。
2. 映射关系：如何快速匹配成对的符号。
3. C++ STL std::stack 的基本操作：
   • push()：压栈。
   • pop()：出栈。
   • top()：查看栈顶。
   • empty()：判断是否为空。

---

二、 NOI 竞赛题目描述

题目名称：有效的括号 (Valid Parentheses) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 $s$，判断字符串是否有效。

有效字符串需满足：

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

【输入格式】 输入包含一行，为一个字符串 $s$。

【输出格式】 输出一行，如果字符串有效输出 true，否则输出 false。

【样例输入 1】

()

【样例输出 1】

true

【样例输入 2】

()[]{}

【样例输出 2】

true

【样例输入 3】

(]

【样例输出 3】

false

【数据规模与约定】

• $1 \le s.length \le 10^4$
• 字符串 $s$ 仅由括号符号组成。

---

三、 启发式思路引导：草稿纸上的推演

请观察这个括号序列：{ [ ( ) ] }。

1. 核心矛盾：谁是当前最急需匹配的？

当你读到 ( 时，你并不关心最外层的 { 何时闭合，你只关心接下来的字符是不是 )。

• 观察：最后进入的左括号，必须最先被匹配掉。
• 启发：这完全符合“后进先出”的特征。

2. 草稿纸模拟过程

假设输入为 ( [ ] )：

1. 读取 (：它是左括号，扔进栈里。栈内状态：( )（左边为底）。
2. 读取 [：它是左括号，扔进栈里。栈内状态：( [。
3. 读取 ]：它是右括号。它必须和“当前栈顶”匹配。栈顶是 [，匹配成功！将 [ 弹出。栈内状态：( )。
4. 读取 )：它是右括号。与当前栈顶 ( 匹配成功！弹出。栈内状态：空。
5. 结束：字符串读完且栈为空，结论：true。

3. 失败的情况（异常捕获）

• 类型不匹配：读到 ] 但栈顶是 (。
• 顺序不对：字符串还没读完，栈已经空了（如 ())）。
• 最后未闭合：字符串读完了，栈里还有剩下的左括号（如 (()）。

---

四、 算法流程图（伪代码逻辑）

在 Mermaid 流程图中，我们使用通俗易懂的文字描述逻辑，避开语法干扰。

graph TD
    Start{开始检查} --> Loop{遍历字符串每个字符 c}
    Loop -- 读完所有字符 --> FinalCheck{栈是否为空}
    
    FinalCheck -- 为空 --> Valid(返回 true)
    FinalCheck -- 不为空 --> Invalid(返回 false)
    
    Loop -- c 是左括号 --> Push(将 c 压入栈中)
    Push --> Loop
    
    Loop -- c 是右括号 --> EmptyCheck{栈是否为空}
    EmptyCheck -- 为空 --> Invalid
    EmptyCheck -- 不为空 --> MatchCheck{c 与栈顶括号是否匹配}
    
    MatchCheck -- 匹配成功 --> Pop(弹出栈顶元素)
    MatchCheck -- 匹配失败 --> Invalid
    Pop --> Loop

---

五、 复杂度分析与优化建议

• 时间复杂度：$O(n)$。我们只需扫描一遍字符串，栈的入栈和出栈操作都是 $O(1)$。
• 空间复杂度：$O(n)$。在最坏情况下（例如输入全是左括号 ((((((），我们需要将所有字符存入栈中。

优化建议：

1. 奇数判断：如果字符串长度是奇数，一定无效，可以直接返回 false。
2. 映射表：在 C++ 中可以使用 std::map 或者 switch-case 建立右括号到左括号的映射，增加代码的可读性和扩展性。
3. 数组模拟栈：在 NOI 竞赛中，如果追求更极致的常数速度，可以用 char st[10005] 和一个指针 top 手写模拟栈。

---

六、 读题关键词总结

在处理括号匹配或具有层级关系的题目时，请圈出这些关键词：

1. “相同类型”：意味着需要分类讨论或使用映射。
2. “正确顺序”：暗示了嵌套关系，这是使用栈的强烈信号。
3. “每个右括号都有对应”：提示不仅要看匹配，还要看栈最终是否清空。

教练寄语：栈是算法竞赛中最基础也最强大的武器之一。当你发现问题具有“撤销”、“回溯”或“就近匹配”的特征时，第一反应就应该是栈。去吧，用 C++ STL 把它实现出来！