1476: 括号括号
时间限制: 3 Sec 内存限制: 128 MB
提交: 305 解决: 61 统计
题目描述
小明今年上大学，在大学里发现有很多同学都女朋友，两人整天都在一起腻歪，小明看到后感觉很孤单，现在，给你一行括号序列，你来判断一下其中的括号是否配对。
输入
多组输入，每一组第一行输入一个数T（0<<N≤≤100）,表示有T组测试数据。后面的T行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[", "]", "(", ")" 四种字符
输出
每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No。
样例输入
3
[(])
(])
([[]()])
样例输出
No
No
Yes
思路
两个循环，i从左往右遍历，j从右往左遍历，当i>=j的时候停止，如果遇到能匹配的括号，将这两个括号变成别的符号，当循环结束后统计括号的个数或者统计不是括号的个数（刚才改变成的符号）。如果括号数为0或者符号数为l，输出“Yes”
AC代码
emmmmm，下面这个代码是错的，数据太水了，就AC了ヽ(￣▽￣)ﾉ。真正的AC代码在最后
#include<bits/stdc++.h>
#define ll long long
#define ms(a) memset(a,0,sizeof(a))
#define pi acos(-1.0)
const int maxn=1e6+10;
using namespace std;
char ch[maxn];
int main()
{
int n;
while(~scanf("%d",&n))
{
while(n--)
{
scanf("%s",ch);
int l=strlen(ch);
if(l%2)
printf("No
");
else
{
int flag=0;
for(int i=0;i<l;i++)
{
for(int j=l-1;j>=0;j--)
{
if(i>=j)
break;
if(ch[i]=='('||ch[i]=='[')
{
if((ch[i]=='('&&ch[j]==')')||(ch[i]=='['&&ch[j]==']'))
{
if((j-i)%2)
{
ch[i]='!';
ch[j]='!';
}
else
continue;
}
}
}
}
for(int i=0;i<l;i++)
{
if(ch[i]=='!')
flag++;
}
if(flag==l)
printf("Yes
");
else
printf("No
");
}
}
}
return 0;
}
这个才是AC代码
#include<iostream>
#include<stack>
#include<string>
#include <stdio.h>
using namespace std;
bool judge(string str)
{
stack<char>S;
while(!S.empty())
S.pop();
int len=str.length();
int i;char temp;
for(int i=0;i<len;i++)
{
if(str[i]=='('||str[i]=='[')
S.push(str[i]);
else
{
if(S.empty()) return false;
temp=S.top();
S.pop();
switch(str[i])
{
case ')':
{
if(temp!='(') return false;
continue;
}
case ']':
{
if(temp!='[') return false;
continue;
}
}
}
}
if(!S.empty()) return false;
return true;
}
int main()
{
int ntest;
while(scanf("%d",&ntest)!=EOF){
string str;
while(ntest--)
{
cin>>str;
if(judge(str))
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
}
return 0;
}