描述
今天发现了nyoj,如获至宝。准备开刷。
括号配对问题
现在,有一行括号序列,请你检查这行括号是否配对。
- 输入
- 第一行输入一个数N(0<N<=100),表示有N组测试数据。后面的N行输入多组输入数据,每组输入数据都是一个字符串S(S的长度小于10000,且S不是空串),测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符
- 输出
- 每组输入数据的输出占一行,如果该字符串中所含的括号是配对的,则输出Yes,如果不配对则输出No
- 样例输入
-
3
[(])
(])
([[]()]) - 样例输出
-
No
No
Yes 开始想的比较简单,直接计数。后来发现题目比想象的复杂,只好用栈来实现了。#include <cstdio>
#include <cstring>
#include <stack> using namespace std; char s[];
stack <char> temp; bool isOk() {
int len = strlen(s);
for(int i = ; i < len; i++) {
if(s[i] == '(') {
temp.push('(');
}
if(s[i] == ')') {
if(temp.empty()) {
return false;
}
if(temp.top() != '(') {
return false;
}
else {
temp.pop();
}
}
if(s[i] == '[') {
temp.push('[');
}
if(s[i] == ']') {
if(temp.empty()) {
return false;
}
if(temp.top() != '[') {
return false;
}
else {
temp.pop();
}
}
}
if(temp.empty()) {
return true;
}
return false;
} int main(int argc, char const *argv[])
{
int n;
while(scanf("%d",&n) != EOF) {
while(n--) {
scanf("%s",s);
while(!temp.empty()) {
temp.pop();
} if(isOk()) {
puts("Yes");
}
else {
puts("No"); }
}
}
return ;
}