Scaena Felix

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 101    Accepted Submission(s): 49

Problem Description

Given a parentheses sequence consist of '(' and ')', a modify can filp a parentheses, changing '(' to ')' or ')' to '('.

If we want every not empty <b>substring</b> of this parentheses sequence not to be "paren-matching", how many times at least to modify this parentheses sequence?

For example, "()","(())","()()" are "paren-matching" strings, but "((", ")(", "((()" are not.

 

 

Input

The first line of the input is a integer 

T, meaning that there are T test cases.

Every test cases contains a parentheses sequence S only consists of '(' and ')'.

1≤|S|≤1,000.

 

 

Output

For every test case output the least number of modification.

 

 

Sample Input

3 () (((( (())

 

 

Sample Output

1 0 2

题解：水题。。。。匹配括号的个数。。。

代码：

1 #include
       
         2 #include
        
          3 using namespace std; 4 const int MAXN=1100; 5 char m[MAXN]; 6 int main(){ 7     int T; 8     scanf("%d",&T); 9     while(T--){10         stack
         
          st;11         scanf("%s",m);12         int k=0;13         for(int i=0;m[i];i++){14             if(m[i]=='(')st.push(m[i]);15             else if(!st.empty())st.pop(),k++;16         }17         printf("%d\n",k);18     }19     return 0;20 }