ny2 括号配对问题

Love The Way You Lie 2022-03-28 07:50 174阅读 0赞

## 括号配对问题 ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

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

输入

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

输出

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

样例输入

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

样例输出

No
    No
    Yes
    AC代码如下：
    第一种方法：

1 #include<stdio.h>
     2 
     3 #define Max 11000
     4 
     5 char str[Max];
     6 
     7 int main()
     8 
     9 {
    10     
    11 int ca,i;
    12  
    13     scanf("%d",&ca);
    14  
    15     getchar();
    16   
    17    while(ca--)
    18   
    19 {
    20          
    21  i = 0;
    22       
    23   while((str[i] = getchar()) != '\n')
    24  {
    25     
    26       if(((str[i] == ')' && str[i - 1] == '(') || (str[i] == ']' && str[i - 1] == '[')) && i > 0)
    27 
    28               i --;
    29  //输入一个判断前一个 前面是否有和它能够配对的字符；如果有则消去这两个字符
    30 
    31           else  i ++;
    32  //否者继续输入
    33  }
    34  
    35       printf("%s\n", i ? "No" : "Yes");
    36  
    37  }
    38    
    39  return 0;
    40 }

第二种：用的C++库函数

1 #include<iostream>
     2 #include<cstring>
     3 #include<cstdio>
     4 #include<stack>
     5 using namespace std;
     6 stack< char >s;
     7 bool mate(char a,char b)
     8 {
     9  return  a=='(' && b==')' ||   a=='[' && b==']';
    10 }
    11 int main()
    12 {
    13  int n,i;
    14  char str[10100];
    15  cin>>n;
    16  while(n--)
    17  {
    18   while(!s.empty()) s.pop();
    19   cin>>str; 
    20   for(i=0;str[i]!='\0';i++)
    21   {
    22                if( s.empty() || !mate(  str[i] ,s.top()) )
    23        s.push(str[i]) ;
    24                else s.pop() ;
    25   }
    26    if(s.empty())
    27     cout<<"Yes"<<endl;
    28    else cout<<"No"<<endl;
    29  }
    30  return 0;
    31 }