堆疊經典問題

括號匹配

給定一個包含 (, ), {, }, [, ] 的字串，判斷這個字串中的括號是否匹配。若匹配則輸出 yes，否則輸出 no。

匹配的意思是每個左括號都有對應的右括號，且括號之間的內容也是匹配的，就像這樣：

() 是匹配的
([]) 是匹配的
{()} 是匹配的
{[()]} 是匹配的
{[}] 不是匹配的
{[} 不是匹配的

首先我們可以思考看看最暴力的作法怎麼做，就是一直從字串左邊往右邊掃描，遇到一個合法的括號就把它移除，直到字串變成空字串，這樣就可以確定括號是匹配的。

發現中間有一個 {} 直接消除掉
({}) -> ()

消除完後發現還有一個 () 直接消除掉
() -> ""

最後發現字串是空的，括號是匹配的

這個作法的問題在於每次消除一個括號都要從頭開始掃描一次字串，還要考慮到把字串後面的內容往前搬花費的時間，非常的慢。不過既然每次都要重新掃一次、移除字串在把後面的內容往前搬動，不如就直接邊掃邊刪除吧？

作法具體來說就是，我們可以用一個堆疊來記錄目前還沒有被匹配的括號，當掃到一個右括號時，就可以從堆疊中取出一個左括號來匹配，如果堆疊是空的，或是取出的左括號和右括號不匹配，就可以直接判定這個字串不合法。

來看看這個範例，首先我們會有一個空堆疊與一個字串 [(){[]}]：

接著我們從左到右掃描字串，遇到左括號就放入堆疊：

繼續掃描，我們遇到的還是左括號，所以繼續放入堆疊：

再繼續掃描，遇到右括號 )，這時候我們可以從堆疊中取出一個左括號來匹配：

匹配成功的話，就可以把左括號從堆疊中移除：

繼續掃描，遇到左括號 {，放入堆疊：

再繼續掃描，遇到左括號 [，放入堆疊：

再繼續掃描，遇到右括號 ]，這時候我們可以從堆疊中取出一個左括號來匹配，配對成功，移除左括號：

再繼續掃描，遇到右括號 }，這時候我們可以從堆疊中取出一個左括號來匹配，配對成功，移除左括號：

再繼續掃描，遇到右括號 ]，這時候剛好把最後一個左括號取出來配對成功，移除左括號：

掃完整個字串後，堆疊是空的，這表示括號是匹配的。

剛剛作法的邏輯大致上就是這樣：

• 如果遇到左括號，就放入堆疊。
• 如果遇到右括號，就從堆疊中取出一個左括號來匹配，如果堆疊是空的，或是取出的左括號和右括號不匹配，就表示這個字串不合法。
• 如果掃描完整個字串後，堆疊是空的，就表示括號是匹配的。

這個作法的時間複雜度是 O(n)，其中 n 是字串的長度，因為我們只需要掃描一次字串，並且每次操作堆疊的時間複雜度是 O(1)。

程式碼如下：

string s = "[(){[]}]";
stack<char> stk;

// 掃描字串
for (char c : s) {
    // 遇到左括號就放入堆疊
    if (c == '(' || c == '{' || c == '[') {
        stk.push(c);
    // 遇到右括號就從堆疊中取出一個左括號來匹配
    } else {
        // 如果堆疊是空的，就表示這個字串不合法
        if (stk.empty()) {
            cout << "no" << endl;
            exit(0);
        }
        char t = stk.top();
        stk.pop();
        // 如果取出的左括號和右括號不匹配，就表示這個字串不合法
        if (
            (c == ')' && t != '(') ||
            (c == '}' && t != '{') ||
            (c == ']' && t != '[')
        ) {
            cout << "no" << endl;
            exit(0);
        }
    }
}

if (stk.empty()) {
    cout << "yes" << endl;
} else {
    cout << "no" << endl;
}