給定一個字元串，其中的字元只包含三種括弧：花括弧{ }、中括弧[ ]、圓括弧( )，即它僅由 「( ) [ ] { }」 這六個字元組成。設計演算法，判斷該字元串是否有效，即字元串中括弧是否匹配。括弧匹配要求括弧必須以正確的順序配對，如 「{ [ ] ( ) }」 或 「[ ( { } [ ] ) ]」 等為正確的格式，而 「[
( ] )」 或 「{ [ ( ) }」 或 「( { } ] )」 均為不正確的格式。

解決此問題，單純從每種括弧的數量上進行匹配是錯誤的，比如對於 「[ ( ] )」，雖然中括弧和圓括弧在數量上是匹配的，但它們的順序卻不匹配。 在考察第 i 位字元 c 與前面的括弧是否匹配時，如果 c 為左括弧，開闢緩衝區記錄下來，希望 c 能夠與後面出現的同類型最近右括弧匹配；如果 c 為右括弧，考察它能否與緩衝區中的左括弧匹配。這個匹配過程，是檢查緩衝區最後出現的同類型左括弧，這也就考慮到了後進先出的思想，所以我們很容易想到棧。棧是一種特殊的線性表，只允許在表的頂端
top 進行插入或者刪除操作，是一種操作受限制的線性表，棧元素正是服從後進先出原則。因此，我們利用棧來解決這個問題。

檢驗括弧是否匹配的方法可以用”期待的急迫程度”這個概念來描述。 分析可能出現的不匹配的情況有以下三種：

（1）到來的右括弧非是所「期待」 的，即出現的右括弧與棧中最後一個左括弧不匹配。

（2）到來的是「不速之客」，即再出現右括弧時棧已經為空。

（3）直到結束，也沒有到來所「期待」 的，所有字元掃描結束後棧中仍有元素。

完整的括弧匹配演算法流程如下：

從前向後掃描字元串：

1. 遇到左括弧 x，就把 x 壓棧；
2. 遇到右括弧 y：
   • 如果發現棧頂元素x和該括弧y匹配，則棧頂元素出棧，繼續判斷下一個字元；
   • 如果棧頂元素x和該括弧y不匹配，字元串不匹配；
   • 如果棧為空，字元串不匹配；
3. 掃描完成後，如果棧恰好為空，則字元串匹配，否則，字元串不匹配。

#include<iostream>
#include<stack>
#include<string>
using namespace std;
//檢測是否棧頂元素與此時的右括弧是否匹配
bool isTopMatch(char a, char b) {
    if (a == '(')return b == ')';
    if (a == '[')return b == ']';
    if (a == '{')return b == '}';
}

bool isCheck(string s) {
    stack<char>stk;
    int i = 0;
    while (i!=s.length()) {
        //判斷是否是左括弧類型符
        if (s[i] == '(' || s[i] == '[' || s[i] == '{')stk.push(s[i]);
        else {
            if(stk.empty() || !isTopMatch(s[i],stk.top()))
                return false;
            stk.pop();
        }
        ++i;
    }
    if (!stk.empty())return false;
    return true;
}
int main() {
    string s = "[{{[]({})}}]";
    if (isCheck(s))cout << "匹配成功" << endl;
    else cout << "匹配失敗" << endl;
    return 0;
}