括号匹配问题：栈的”超简单”应用¶
在数据结构中，栈（Stack）是一种非常基础但应用广泛的结构，它的特点是后进先出（LIFO）——就像我们往一个桶里放书，最后放进去的书总是最先被拿出来。这种特性让栈在很多问题中大显身手，其中最经典的应用之一就是括号匹配问题。
一、什么是括号匹配问题？¶
括号匹配问题的核心是判断一个由()、[]、{}组成的字符串是否合法。合法的条件是：
1. 所有左括号都有对应的右括号，且顺序正确（不能交叉）；
2. 例如："(()())"是合法的，"([)]"是不合法的（交叉了）。
二、为什么用栈解决？¶
栈的“后进先出”特性完美适配括号匹配的逻辑：
- 当遇到左括号时，我们需要“记住”它，稍后匹配对应的右括号；
- 当遇到右括号时，必须找到最近的未匹配的左括号（即栈顶元素），这样才能保证顺序正确。
三、用栈解决括号匹配的步骤¶
步骤1：初始化一个栈（可以用列表模拟，Python中append是压栈，pop是弹栈）。
步骤2：遍历字符串中的每个字符，分两种情况处理：
- 如果是左括号（(、[、{）：直接压入栈中（标记为“待匹配”）；
- 如果是右括号（)、]、}）：
- 若栈为空，说明没有对应的左括号，直接返回“不匹配”；
- 若栈不为空，取出栈顶元素，检查是否与当前右括号匹配。例如：当前是)，则栈顶应为(；当前是]，栈顶应为[；
- 若匹配，弹出栈顶元素（表示已匹配）；若不匹配，直接返回“不匹配”。
步骤3：遍历结束后，若栈为空，说明所有左括号都匹配了，返回“匹配”；否则，栈中还有未匹配的左括号，返回“不匹配”。
四、举个例子让你秒懂！¶
例子1：合法括号串——”(()())”
- 初始化栈：[]
- 遍历字符：( → 左括号，压栈 → 栈：['(']
- 遍历字符：( → 左括号，压栈 → 栈：['(', '(']
- 遍历字符：) → 右括号，查对应左括号(，栈顶是(，匹配，弹出 → 栈：['(']
- 遍历字符：( → 左括号，压栈 → 栈：['(', '(']
- 遍历字符：) → 右括号，对应左括号(，栈顶是(，匹配，弹出 → 栈：['(']
- 遍历字符：) → 右括号，对应左括号(，栈顶是(，匹配，弹出 → 栈：[]
- 遍历结束，栈为空 → 合法。
例子2：非法括号串——”([)]”
- 初始化栈：[]
- 遍历字符：( → 压栈 → 栈：['(']
- 遍历字符：[ → 压栈 → 栈：['(', '[']
- 遍历字符：) → 右括号，对应左括号(，但栈顶是[，不匹配 → 非法。
五、关键细节要注意！¶
- 区分括号类型：必须保证右括号和左括号一一对应，例如
(只能对应)，不能用[对应)。可以用一个字典建立映射：{')':'(', ']':'[', '}':'{'}。 - 右括号优先处理：如果栈为空时遇到右括号，直接返回非法（没有对应的左括号）。
- 最终栈是否为空：遍历结束后栈为空，说明所有左括号都匹配了；否则还有未匹配的左括号，也非法。
六、总结¶
栈的“后进先出”特性天然适合处理“最近匹配”的问题，括号匹配正是典型场景。核心逻辑是：左括号压栈，右括号查栈顶匹配，最后检查栈是否为空。通过这几个步骤，你就能轻松判断任意括号串是否合法啦！
小练习¶
试着用栈解决下面的括号串：
1. "()[]{}" → 合法
2. "([)]" → 非法
3. "(())" → 合法
4. "(()" → 非法
（答案：1.合法，2.非法，3.合法，4.非法）
通过这些例子，你会发现栈的应用原来这么简单！掌握栈的核心思想，后续学习更多数据结构问题时会更轻松~