1476: 括号括号

时间限制: 3 Sec 内存限制: 128 MB

提交: 305 解决: 61 

题目描述

小明今年上大学，在大学里发现有很多同学都女朋友，两人整天都在一起腻歪，小明看到后感觉很孤单，现在，给你一行括号序列，你来判断一下其中的括号是否配对。

输入

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

输出

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

样例输入

3[(])(])([[]()])

样例输出

NoNoYes

思路

两个循环，i从左往右遍历，j从右往左遍历，当i>=j的时候停止，如果遇到能匹配的括号，将这两个括号变成别的符号，当循环结束后统计括号的个数或者统计不是括号的个数（刚才改变成的符号）。如果括号数为0或者符号数为l，输出“Yes”

AC代码

emmmmm，下面这个代码是错的，数据太水了，就AC了ヽ(￣▽￣)ﾉ。真正的AC代码在最后

#include
    
     #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\n");			else			{				int flag=0;				for(int i=0;i
     
      =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
     
    

这个才是AC代码

#include
    
     #include
     
      #include
      
       #include 
       
        using namespace std;bool judge(string str){    stack
        
         S;    while(!S.empty())    S.pop();    int len=str.length();    int i;char temp;    for(int i=0;i
         
          >str; if(judge(str)) cout<<"Yes"<