题目：

描述:

假设表达式中只包含三种括号：圆括号、方括号和花括号，它们可相互嵌套，如([{}])或({[][()]})等均为正确的格式,而{[]})}或{[()]或([]}均为不正确的格式.

输入一串括号

如果输入的右括号多余，输出:Extra right brackets

如果输入的左括号多余, 输出:Extra left brackets

如果输入的括号不匹配，输出:Brackets not match

如果输入的括号匹配，输出:Brackets match

输入格式:

一行只含 ( ) [ ] { } 这6种字符，不含其它任何字符的字符串。字符串不超过1000个字符。

输出格式:

如果输入的右括号多余，输出:

Extra right brackets
    

如果输入的左括号多余, 输出:

Extra left brackets
    

如果输入的括号不匹配，输出:

Brackets not match
    

如果输入的括号匹配，输出:

Brackets match
    

输入样例:

{{{{)))

输出样例:

Brackets not match

---

思路：

本来这个题打算用s.find()、count()函数，来先找到左括号，再往后查数量和顺序是否对应。但实际上括号并不一定是从中间对称的（例如 ({[][()]}) ），使用上述办法不仅十分复杂，还不能考虑到所有情况。

其实这个题的最佳解法是用栈。因为栈的特性能够很好地用于这种套娃问题的处理。

废话不多说，说明都写在下面代码的注释里了。

---

解法：

#include <bits/stdc++.h>
using namespace std;

stack<int> st;
map<char, char> mp;

int main()
{
    // 用map创建键值对，建立左右括号的对应关系
    mp['('] = ')';
    mp['{'] = '}';
    mp['['] = ']';

    string s;
    cin >> s;
    for (size_t i = 0; i < s.length(); i++) {
        // 从前往后依次读入字符
        int c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            // 如果读取的是左括号，就先入栈保存（放到了栈顶）
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            // 如果读取的是右括号
            if (st.empty()) {
                // 如果栈为空，就说明没有左括号与之匹配，则该右括号是多余的，程序结束例如 {[]})
                cout << "Extra right brackets" << endl;
                return 0;
            } else {
                if (c == mp[st.top()]) {
                    // 如果栈顶的左括号与当前右括号匹配，就弹出栈顶的左括号，意味着当前这对括号合法不用在管了，程序进行下一轮循环
                    st.pop();
                } else {
                    // 如果栈顶的左括号与当前右括号不匹配，就输出不匹配，程序结束例如 [{)]
                    cout << "Brackets not match" << endl;
                    return 0;
                }
            }
        }
    }
    // 当所有字符处理完之后
    if (!st.empty()) {
        // 如果此时栈里还有元素，也就说明左括号有多余的，例如 {[()]
        cout << "Extra left brackets" << endl;
    } else {
        // 如果此时栈空了，就说明万事大吉，括号是匹配的
        cout << "Brackets match" << endl;
    }

    return 0;
}