题目：

现在，有一行括号序列，请你检查这行括号是否配对。

输入格式:

第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有”[“, “]”, “(“, “)” 四种字符

输出格式:

每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No

输入样例:

1
2
3
4
3
[(])
(])
([[]()])

输出样例:

1
2
3
No
No
Yes

思路

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

using namespace std;

int N;

int main()
{
    map<char,char> m;
    m['(']=')',m['[']=']';
    cin>>N;
    for(int i=0; i<N; i++)
    {
        string str;
        cin>>str;
        stack<char> s;
        int j;
        for(j=0; j<str.length(); j++)
        {
            if(m.count(str[j])) s.push(str[j]);
            else
            {
                if(s.empty()) break;
                char ch=s.top();
                s.pop();
                if(m[ch]!=str[j]) break;
            }
        }
        if(j<str.length()||!s.empty()) puts("No");
        else puts("Yes");
    }
}