有效括號匹配算法：棧的經典應用

題目描述

給定一個只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判斷該字符串是否有效。有效條件：括號必須按正確順序閉合，如 "()" 和 "()[]{}" 有效，但 "(]" 和 "([)]" 無效。

解題思路：棧

利用棧的先進後出特性，遍歷字符串：

1. 遇到左括號 (、{、[ 直接入棧。
2. 遇到右括號時，若棧為空則無效；否則彈出棧頂元素，檢查是否匹配（如 ) 對應 (）。
3. 遍歷結束後，棧必須為空才有效。

代碼實現

#include <iostream>
#include <vector>
#include <string>
#include <stack>
using namespace std;

bool isValid(string s) {
    if (s.empty()) return true;
    stack<char> CharStack;
    for (int i = 0; i != s.size(); ++i) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
            CharStack.push(s[i]);
        else {
            if (CharStack.empty()) return false;
            switch (s[i]) {
                case ')':
                    if (CharStack.top() == '(') CharStack.pop();
                    else return false;
                    break;
                case ']':
                    if (CharStack.top() == '[') CharStack.pop();
                    else return false;
                    break;
                case '}':
                    if (CharStack.top() == '{') CharStack.pop();
                    else return false;
                    break;
                default: break;
            }
        }
    }
    return CharStack.empty();
}

複雜度分析

• 時間複雜度：O(n)，n 為字符串長度，每字符進出棧一次。
• 空間複雜度：O(n)，最坏情況所有字符均為左括號。

擴展應用

此模板可擴展至：表達式求值、語法解析、編譯器詞法分析等場景。掌握棧處理括號匹配是數據結構的基石技能。