括號匹配問題：棧的”超簡單”應用¶
在數據結構中，棧（Stack）是一種非常基礎但應用廣泛的結構，它的特點是後進先出（LIFO）——就像我們往一個桶裏放書，最後放進去的書總是最先被拿出來。這種特性讓棧在很多問題中大顯身手，其中最經典的應用之一就是括號匹配問題。
一、什麼是括號匹配問題？¶
括號匹配問題的核心是判斷一個由()、[]、{}組成的字符串是否合法。合法的條件是：
1. 所有左括號都有對應的右括號，且順序正確（不能交叉）；
2. 例如："(()())"是合法的，"([)]"是不合法的（交叉了）。
二、爲什麼用棧解決？¶
棧的“後進先出”特性完美適配括號匹配的邏輯：
- 當遇到左括號時，我們需要“記住”它，稍後匹配對應的右括號；
- 當遇到右括號時，必須找到最近的未匹配的左括號（即棧頂元素），這樣才能保證順序正確。
三、用棧解決括號匹配的步驟¶
步驟1：初始化一個棧（可以用列表模擬，Python中append是壓棧，pop是彈棧）。
步驟2：遍歷字符串中的每個字符，分兩種情況處理：
- 如果是左括號（(、[、{）：直接壓入棧中（標記爲“待匹配”）；
- 如果是右括號（)、]、}）：
- 若棧爲空，說明沒有對應的左括號，直接返回“不匹配”；
- 若棧不爲空，取出棧頂元素，檢查是否與當前右括號匹配。例如：當前是)，則棧頂應爲(；當前是]，棧頂應爲[；
- 若匹配，彈出棧頂元素（表示已匹配）；若不匹配，直接返回“不匹配”。
步驟3：遍歷結束後，若棧爲空，說明所有左括號都匹配了，返回“匹配”；否則，棧中還有未匹配的左括號，返回“不匹配”。
四、舉個例子讓你秒懂！¶
例子1：合法括號串——”(()())”
- 初始化棧：[]
- 遍歷字符：( → 左括號，壓棧 → 棧：['(']
- 遍歷字符：( → 左括號，壓棧 → 棧：['(', '(']
- 遍歷字符：) → 右括號，查對應左括號(，棧頂是(，匹配，彈出 → 棧：['(']
- 遍歷字符：( → 左括號，壓棧 → 棧：['(', '(']
- 遍歷字符：) → 右括號，對應左括號(，棧頂是(，匹配，彈出 → 棧：['(']
- 遍歷字符：) → 右括號，對應左括號(，棧頂是(，匹配，彈出 → 棧：[]
- 遍歷結束，棧爲空 → 合法。
例子2：非法括號串——”([)]”
- 初始化棧：[]
- 遍歷字符：( → 壓棧 → 棧：['(']
- 遍歷字符：[ → 壓棧 → 棧：['(', '[']
- 遍歷字符：) → 右括號，對應左括號(，但棧頂是[，不匹配 → 非法。
五、關鍵細節要注意！¶
- 區分括號類型：必須保證右括號和左括號一一對應，例如
(只能對應)，不能用[對應)。可以用一個字典建立映射：{')':'(', ']':'[', '}':'{'}。 - 右括號優先處理：如果棧爲空時遇到右括號，直接返回非法（沒有對應的左括號）。
- 最終棧是否爲空：遍歷結束後棧爲空，說明所有左括號都匹配了；否則還有未匹配的左括號，也非法。
六、總結¶
棧的“後進先出”特性天然適合處理“最近匹配”的問題，括號匹配正是典型場景。核心邏輯是：左括號壓棧，右括號查棧頂匹配，最後檢查棧是否爲空。通過這幾個步驟，你就能輕鬆判斷任意括號串是否合法啦！
小練習¶
試着用棧解決下面的括號串：
1. "()[]{}" → 合法
2. "([)]" → 非法
3. "(())" → 合法
4. "(()" → 非法
（答案：1.合法，2.非法，3.合法，4.非法）
通過這些例子，你會發現棧的應用原來這麼簡單！掌握棧的核心思想，後續學習更多數據結構問題時會更輕鬆~