Description
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Correct parentheses sequences can be defined recursively as follows: 1.The empty string "" is a correct sequence. 2.If "X" and "Y" are correct sequences, then "XY" (the concatenation of X and Y) is a correct sequence. 3.If "X" is a correct sequence, then "(X)" is a correct sequence. Each correct parentheses sequence can be derived using the above rules. Examples of correct parentheses sequences include "", "()", "()()()", "(()())", and "(((())))". Now Yuta has a parentheses sequence , and he wants Rikka to choose two different position and swap . Rikka likes correct parentheses sequence. So she wants to know if she can change S to a correct parentheses sequence after this operation. It is too difficult for Rikka. Can you help her?
Input
The first line contains a number t(1<=t<=1000), the number of the testcases. And there are no more then 10 testcases with n>100 For each testcase, the first line contains an integers n(1<=n<=100000), the length of S. And the second line contains a string of length S which only contains ‘(’ and ‘)’.
Output
For each testcase, print "Yes" or "No" in a line.
Sample Input
3 4 ())( 4 ()() 6 )))(((Sample Output
Yes Yes No
在用栈模拟括号匹配完之后，在栈里剩下的就是不能匹配的括号，当且仅当是）（和））（（组合时，才是Yes
#include<cmath> #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<queue> #include<stack> #define inf 0x3f3f3f3f using namespace std; stack<char> s; char a[1000]; int main() { int T; cin>>T; while(T--) { int n; cin>>n; string str; cin>>str; if(str[0]=='('&&str[1]==')'&&n==2) { cout<<"No"<<endl; continue; } if(n%2==1) { cout<<"No"<<endl; continue; } while(!s.empty()) s.pop(); for(int i=0;i<=n-1;i++) { if(s.empty()==1) s.push(str[i]); else { if(str[i]=='(') s.push(str[i]); else { if(s.top()=='(') s.pop(); else s.push(str[i]); } } } if(s.empty()==1) cout<<"Yes"<<endl; else { int k=0; while(!s.empty()) { a[k++]=s.top(); s.pop(); } if(a[0]=='('&&a[1]==')'&&k==2) cout<<"Yes"<<endl; else if(a[0]=='('&&a[1]=='('&&a[2]==')'&&a[3]==')'&&k==4) cout<<"Yes"<<endl; else cout<<"No"<<endl; } } return 0; }
