【NYOJ】[v1-2]括号配对问题

问题描述

括号配对问题

时间限制：3000 ms内存限制：128 MB

描述

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

输入

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

输出

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

样例输入

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

样例输出

1
2
3
No
No
Yes

题目来源

括号配对问题 - NYOJ

问题分析

用栈来检测是否对应

 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
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
char s[10200];
stack<char>q;
bool judge(char a,char b) {
    if(a=='('&&b==')')
        return false;
    if(a=='['&&b==']')
        return false;
    return true;
}
int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%s",s);
        int l=strlen(s);
        bool flag=true;
        while(!q.empty())
            q.pop();
        for(int i=0; i<l; i++) {
            if(!flag)
                continue;
            if(s[i]=='['||s[i]=='(')
                q.push(s[i]);
            else {
                if(q.empty()||judge(q.top(),s[i]))
                    flag=false;
                else
                    q.pop();
            }
        }
        printf("%s\n",flag?"Yes":"No");
    }
    return 0;
}