7454 Parentheses

A bracket is a punctuation mark, which is used in matched pairs, usually used within articles or programs. Brackets include round brackets, square brackets, curly brackets, angle brackets, and various other pairs of symbols. Let’s focus on the round brackets, also called parentheses. A sequence of parentheses is said to be well-formed if the parentheses are properly nested. For example, A = a1a2 . . . a18 = “(()())()()()(())()” is well-formed, but B = b1b2 . . . b18 = “(()())))(((((())((” is not. (See Figure 1.) More formally, a sequence of parentheses P = p1p2 . . . pn is well-formed

if (1) when scanning it from p1 to pn, the number of right parentheses does not exceed the number of left parentheses at any state, and

(2) the numbers of left and right parentheses are equal.

Figure 1. Two sequences of parentheses.AutoText is a company, which is developing a text editor for programmers.  The new editor willprovide many powerful functions to automatically correct typing errors. On a keyboard, the left andright parentheses are adjacent. Thus, it is often that “)” is mistyped as “(” or vice versa. And therefore,one of the functions AutoText wants to provide is to automatically convert a sequence of parenthesesP(that may not be well-formed) into a wellformed sequenceP′. In the conversion, the only allowedoperation is to reverse a parenthesis (i.e., either to replace a “(” with a “)” or to replace a “)” witha “(”). For example, in Figure 1, we can convertBinto the well-formed sequenceAby performing 4reverse operations onb7,b10,b12,b18. Of course, there may be several ways to convert a sequence intoa well-formed sequence. A conversion is optimal if it uses the minimum number of reverse operations.Please write a program to compute the minimum number of reverse operations that make a givensequence of parenthesesP=p1p2:::pnwell-formed.InputThe first line contains an integerT10indicating the number of test cases. The first line of each testcase contains an even integern,2n100, indicating the length ofP. Next, the second line givesthe sequenceP.

Output

For each test case, output the minimum number of reverse operations that makePwell-formed.

Sample Input

3

18

(()())))(((((())((

2

()

8

(()))()(

Sample Output

4

0

2

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
stack<char>s;
int main()
{
    int t,n,ans;
    int x,y;
    char c;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        getchar();
        ans=0;
        while(!s.empty())///清空栈
        {
            s.pop();
        }
        while(n--)
        {
            scanf("%c",&c);
            if(c=='(')
            {
                s.push(c);
            }
            else if(c==')')
            {
                if(!s.empty()&&s.top()=='(')///已经匹配出栈
                {
                    s.pop();
                }
                else
                {
                    s.push(c);
                }
            }
        }
        x=0;
        y=0;
        ans=0;
        while(!s.empty())
        {
            if(s.top()=='(')
            {
                x++;
            }
            else if(s.top()==')')
            {
                y++;
            }
            if(x==1&&y==1)///出现')('的情况
            {
                x--;
                y--;
                ans=ans+2;///两个同时翻转
            }
            else if(x==2)///出现'(('的情况
            {
                x=x-2;
                ans++;///翻转一个
            }
            else if(y==2)///出现'))'的情况
            {
                y=y-2;
                ans++;///翻转一个
            }
            s.pop();
        }
        printf("%d\n",ans);
    }
    return 0;
}