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

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

代码：

 #include<stdio.h>

 #include<stack>

 using namespace std;

 const int MAXN=;

 char m[MAXN];

 int main(){

     int T;

     scanf("%d",&T);

     while(T--){

         stack<char>st;

         scanf("%s",m);

         int k=;

         for(int i=;m[i];i++){

             if(m[i]=='(')st.push(m[i]);

             else if(!st.empty())st.pop(),k++;

         }

         printf("%d\n",k);

     }

     return ;

 }

of

hdoj Scaena Felix

Scaena Felix