给定仅包含“()[]{}”六种括号的字符串，请你判断该字符串中，括号的匹配是否是合法的，也就是对应括号的数量、嵌套顺序完全正确。

输入格式:

第一行一个整数T（T<=10）
其后T行每行一个字符串只包含[{()}]六种字符（字符串长度2e5以内）

输出格式:

对于每个字符串，匹配输出Yes,否则输出No

输入样例:

1
2
3
2
{()[]}
([)]

输出样例:

1
2
Yes
No

思路

给定一个括号序列，看序列是否合法，关键要明白如何判定序列是不合法的，而不合法其实就是有括号没有被正确地匹配掉，从左向右去遍历序列，它可包括以下三种情况：第一，遍历到了右括号，但是之前没有左括号和它匹配了；第二，遍历到了右括号，在它之前有左括号，但是很遗憾，不满足大对大、中对中、小对小，匹配不上；第三，遍历结束了，发现还有左括号没有被匹配掉。切记情况一定要讨论清楚了。结合上述，又因为每次匹配的时候，遍历到的那个右括号必须是和之前最后遇到的左括号匹配(显然，毕竟数学上不就这么用的么)，所以我们会想到用stack这个特性为后进先出的数据结构来实现以上操作。代码如下：

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <stack>

using namespace std;

int main() {
    int n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        bool flag = true;
        stack<char> stk;
        for(auto x : s) {
            if(x == '[' || x == '(' || x == '{')
                stk.push(x);
            else {
                if(stk.empty()) {
                    flag = false;
                    break;
                }
                if((x == '}' && stk.top() == '{') || (x == ')' && stk.top() == '(') || (x == ']' && stk.top() == '[')) {
                    stk.pop();
                } else {
                    flag = false;
                    break;
                }
            }
        }
        if (flag && stk.empty())
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>>

using namespace std;

int main()
{
    int T;
    map<char,char> m;//这里是故意定义了一个map，用于给定括号匹配的规则
    m['(']=')';m['[']=']';m['{']='}';
    cin>>T;
    for(int j=0;j<T; j++)
    {
        string str;
        cin>>str;
        stack<char> s;//每次输入都定义一个stack去处理对应的括号序列(要是定义到循环外的话记得clear一下)
        int flag=1;//设置括号序列是否合法的标志，为1时表示序列合法
        int i;
        for(i=0; i<str.length(); i++)//遍历序列
        {
            if(str[i]=='('||str[i]=='['||str[i]=='{')//碰到左括号时入栈
            {
                s.push(str[i]);
            }
            else//碰到右括号时
            {
                if(s.empty())//要是栈空，说明没有左括号和该右括号匹配了，则序列不合法
                {
                    flag=0;
                    break;
                }
                else//要是栈不空，那就去试试看用栈顶的左括号和该右括号匹配
                {
                    char temp=s.top();
                    s.pop();
                    if(m[temp]!=str[i])//如果匹配失败，那么序列不合法
                    {
                        flag=0;
                        break;
                    }
                }
            }
        }
        if(i==str.length()&&!s.empty())//这个判断别漏了，毕竟当序列都遍历完了我栈还要是不空的话，自然就表示还有左括号没被匹配走，序列还是不合法的
        {
            flag=0;
        }
        if(flag)
        {
            cout<<"Yes"<<endl;
        }
        else
        {
            cout<<"No"<<endl;
        }
    }
}