Rikka with Parenthesis II

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 691    Accepted Submission(s): 379 Problem 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  S , and he wants Rikka to choose two different position  i,j  and swap  Si,Sj .  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，否则No。但是“()”是No，因为必须要进行交换。

#include<iostream> #include<stack> #include<cstdio> using namespace std; int T, N; char s[100010], ch; int main() { scanf("%d", &T); while(T--) { stack<char>st; scanf("%d", &N); scanf("%s", s); if(N%2) { cout <<"No"<< endl; continue; } if(N == 2 && s[0] == '(' && s[1] == ')') { cout <<"No"<< endl; continue; } for(int i = 0;i < N; ++i) { if(s[i] == '(') st.push(s[i]); else if(s[i] == ')') { if(!st.empty() && st.top() == '(') st.pop(); else st.push(s[i]); } } if(st.empty()) cout <<"Yes"<< endl; else if(st.size() != 2 && st.size() != 4) cout <<"No"<< endl; else { char ss[10]; if(st.size() == 2) { ss[1] = st.top(); st.pop(); ss[0] = st.top(); if(ss[0] == ')' && ss[1] == '(') cout <<"Yes"<< endl; else cout <<"No"<< endl; } else { for(int i = 3;i >= 0; --i) { ss[i] = st.top(); st.pop(); } if(ss[0] == ')' && ss[1] == ')' && ss[2] == '(' && ss[3] == '(') cout <<"Yes"<< endl; else cout <<"No"<< endl; } } } return 0; }