正式賽1011 合法比對

Problem Description

括号序列指的是隻包含 ‘(’ 和 ‘)’ 的序列。

合法括号序列的定義如下：

1.空序列為合法序列。

2.如果 A 是一個合法序列，則 (A) 也為合法序列。

3.如果 A 和 B 都為合法序列，則 AB 也為合法序列。

現給出一個括号序列，求最少删去幾個括号能得到一個合法序列。

Input

第一行一個整數 T(1≤T≤30) ，表示測試資料組數。接下來包含 T 組測試資料。

對于每組測試資料，第一行輸入一個整數 n (1≤n≤2×105) ，表示括号序列的長度。

第二行輸入一個長為 n 的括号序列。

Output

對于每組測試資料，輸出一個數表示最少删去幾個括号能得到一個合法的括号序列。

Sample Input

2

6

()(())

7

())(()(

Sample Output

3

仔細讀題，了解題意。

#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,index=0;
        scanf("%d",&n);
        getchar();
        char str[n];
        char a;
        for(int i=0;i<n;i++)
        {
            a=getchar();
            if(index==0)
            {
                str[index]=a;
                index++;
                //cout<<"index1:"<<index<<"str_top1:"<<str[index-1]<<endl;  //測試所用
            }else{
                if(a=='(')
                {
                    str[index]=a;
                    index++;
                }else if(a==')'){
                    if(str[index-1]=='(')
                    {
                        str[index-1]='0';
                        //cout<<"str_top:"<<str[index-1]<<endl;  //測試所用
                        index--;
                    }else{
                        str[index]=a;
                        index++;
                    }
                }
            }
        }
        printf("%d\n",index);
    }
    return 0;
}