COJ1271 Brackets Sequence

斌牛出的校赛题

1271: Brackets Sequence

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 92 Solved: 36
[Submit][Status][Web Board]

Description

Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.

2. If S is a regular sequence, then (S) is a regular sequence.

3. If A and B are regular sequences, then AB is a regular sequence.

For example, these sequences of characters are regular brackets sequences: (), (()), ()(), ()(()), ((())())().

And all the following character sequences are not: (, ), ((), ()), ())(, (()(, ()))().

A sequence of characters '(' and ')' is given. You can insert only one '(' or ')' into the left of the sequence, the right of the sequence, or the place between any two adjacent characters, to try changing this sequence to a regular brackets sequence.

Input

The first line has a integer T (1 <= T <= 200), means there are T test cases in total.

For each test case, there is a sequence of characters '(' and ')' in one line. The length of the sequence is in range [1, 10⁵].

Output

For each test case, print how many places there are, into which you insert a '(' or ')', can change the sequence to a regular brackets sequence.

What's more, you can assume there has at least one such place.

Sample Input

)

())

(()(())

((())())(()

Sample Output

思路是看了博客上的

D. Brackets Sequence

这个题目如果熟悉判断一个括号序列是否合法的方法的话，应该还比较容易想到解法，所以先提一下判断括号序列是否合法的一个方法。

我们将一个括号序列中的左括号当成1，右括号当成-1，然后从左至右依次累加，就可以得到一个整数序列，比如()(()())对应的整数序列就是1 0 1 2 1 2 1 0，如果整数序列中不存在负数，且最后一个数是0，那么这个括号序列就是合法的。

接下来我们考虑此题的解法。由于题目说了答案至少是1，那么也就是说这个序列相比合法的括号序列而言只是少了一个括号，至于少的是左括号还是右括号，我们根据括号的数量是很容易判断出来的。

不妨先讨论缺少一个左括号的情况。比如(()))()这个序列，对应的整数序列就是1 2 1 0 -1 0 -1。接着我们考虑在哪里插入一个左括号可以使其变成一个合法的括号序列，其实也就是考虑在哪里插入一个左括号后使这个整数序列所有的值都是非负的。考虑到插入一个左括号的效果是插入一个整数，并且让插入位置右边的所有整数都+1，因此左括号可以插入的最右的位置应该是最左的-1的左边，同时这个位置左边的任何一个位置都可以作为插入位置。这样我们只要遍历一下这个整数序列找到第一个-1出现的位置就可以知道有多少个位置可以插入左括号了。

至于缺少一个右括号的情况，比如()((())这个序列，我们可以将其翻转一下，就变成了(()))()，这样就又变成了缺少一个左括号的情况了。

来源：http://122.207.68.93/csuacm/

#include <iostream>
#include <cstring>
using namespace std;
char seq[100005];
int calc[100005];

int main()
{
    int t;
    cin>>t;
    cin.get();
    while (t--)
    {

        memset (calc,0,sizeof calc);
        cin.getline(seq,100002);
        int len=strlen(seq);
        for (int i=0;i<len;i++)
        {
            int front;
            if (i==0) front=0;
            else front=i-1;
            if (seq[i]=='(') calc[i]=calc[front]+1;
            if (seq[i]==')') calc[i]=calc[front]-1;
        }
        int sum=0;
        for (int j=0;j<len;j++)
        {
            if (calc[j]==-1)
            {
                sum=sum+j+1;
                break;
            }
        }
        for (int k=len-1;k>=0;k--)
        {
            if (seq[k]=='(') calc[k] = calc[k+1]+1;
            if (seq[k]==')') calc[k]= calc[k+1] -1;
        }
        for (int q=len-1;q>=0;q--)
        {
            if (calc[q]==1)
            {
                sum=sum+len-q;
                break;
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}