用一个temp变量，每次出现左括号，+1，右括号，-1；用ans来记录出现的最小的值，很显然最终temp不等于0或者ans比-2小都是不可以的。-2是可以的，因为：“))((”可以把最左边的和最右边的交换即可，其他-2的情形同理。另外要注意的坑点是Hint里面所说的：“But do nothing is not allowed.”。因此，“()”是不可以的，这个要特判。
代码如下：
1 #include <stdio.h> 2 #include <algorithm> 3 #include <string.h> 4 #include <math.h> 5 using namespace std; 6 const int N = 100000 + 5; 7 8 char s[N]; 9 10 int main() 11 { 12 int T;scanf("%d",&T); 13 while(T--) 14 { 15 int n;scanf("%d",&n); 16 scanf("%s",s+1); 17 if(strlen(s+1)==2 && s[1]==‘(‘ && s[2]==‘)‘) 18 { 19 puts("No"); 20 continue; 21 } 22 int temp = 0; 23 int ans = 0; 24 for(int i=1;i<=n;i++) 25 { 26 if(s[i] == ‘)‘) temp --; 27 else temp ++; 28 ans = min(ans,temp); 29 } 30 if(ans<-2 || temp!=0) puts("No"); 31 else puts("Yes"); 32 } 33 }
HDU 5831 Rikka with Parenthesis II ——（括号匹配问题）
原文：http://www.cnblogs.com/zzyDS/p/5792474.html