括號匹配#
給定一個包含 (, ), {, }, [, ] 的字串，判斷這個字串中的括號是否匹配。若匹配則輸出 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;
}
