括号配对问题

括号配对问题

时间限制： 3000 ms  |  内存限制： 65535 KB 难度： 3 描述 现在，有一行括号序列，请你检查这行括号是否配对。 输入 第一行输入一个数N（0<N<=100）,表示有N组测试数据。后面的N行输入多组输入数据，每组输入数据都是一个字符串S(S的长度小于10000，且S不是空串），测试数据组数少于5组。数据保证S中只含有"[","]","(",")"四种字符 输出 每组输入数据的输出占一行，如果该字符串中所含的括号是配对的，则输出Yes,如果不配对则输出No 样例输入 3 [(]) (]) ([[]()]) 样例输出 No No Yes 来源 网络 上传者

naonao

方法一：字符串函数， strstr(s,ss); ss是否在s中 不出现返回0

#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #define inf 0x3f3f3f #define M 10000+10 using namespace std; char str[M]; int main() { int t; scanf("%d",&t); while(t--) { scanf("%s",str); int len=strlen(str); int left,right,left1,right1; if(len&1) printf("No\n"); else  { left=right=left1=right1=0; int exist=1; for(int i=0;i<len;i++) { if(str[i]=='(') left++; if(str[i]==')') right++; if(str[i]=='[') left1++; if(str[i]==']')  right1++; } if(strstr(str,"[)")!=0||strstr(str,"(]")!=0||str[0]==']'||str[0]==')'||str[len-1]=='['||str[len-1]=='(' )  //  不成立情况 exist=0; if(left!=right||left1!=right1)   // 不成立情况 exist=0; if(exist) printf("Yes\n"); else printf("No\n"); } } return 0;  } 

法二 栈

#include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<stack> #define inf 0x3f3f3f #define M 10000+10 using namespace std; char str[M]; int main() {   int t;   scanf("%d",&t);   while(t--)   {   scanf("%s",str);   stack<char>num;   for(int i=0;i<strlen(str);i++)   {   if(num.empty())   num.push(str[i]);   else    {   if(str[i]=='('||str[i]=='[')   num.push(str[i]);   else if(str[i]==')'&&num.top()=='('||str[i]==']'&&num.top()=='[')   num.pop();   ///  如果能够配对则删掉

  else num.push(str[i]);  } } if(num.empty()) printf("Yes\n"); // 全部消除 就说明都是配对的 else printf("No\n"); } return 0;  }