qscoj 11 喵哈哈村的括号序列

链接

http://qscoj.cn/problem/11/

发布时间: 2017年2月21日 20:05   最后更新: 2017年2月21日 20:07   时间限制: 1000ms   内存限制: 128M

描述

喵哈哈村的括号序列和外界的括号序列实际上是一样的。

众所周知"()"这样的，就是一个标准的括号序列；"()()()()"这样也是括号序列；“((()))()”这样也是一个合法的括号序列。但是"((("这样，就不是一个合法的括号序列了。

现在沈宝宝非常好奇，给你一个字符串，请从中找出最长的合法括号序列出来。

不知道你能找到吗？

输入

第一行一个T，表示有T组数据。
接下来T行，每一行都是一个字符串。
保证字符串的长度小于100000。
而且字符串中保证只会出现"(",")"这两种字符之一。
1<=T<=10

输出

对于每一组测试数据，输出最长的合法括号序列的长度。

样例输入1 

2
)((())))(()())
)(

样例输出1

6
0

题解
若为“（”，存入栈S，若遇到“）”，将“（”，“）“都标记为1，取出栈顶，若位置连续为1，用mx记录括号组数。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100006;
string s;
int vis[maxn];

void solve(){
    cin>>s;
    memset(vis,0,sizeof(vis));
    stack<int> S;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(') S.push(i);
        else {
            if(S.size()==0)continue;
            vis[i]=1;
            vis[S.top()]=1;
            S.pop();
        }
    }
    int ans=0,mx=0;
    for(int i=0;i<s.size();i++){
        if(vis[i]==0) mx=0;
        else mx++;
        ans=max(ans,mx); 
    }
    cout<<ans<<endl;
}

int main(){
    int n;
    cin>>n;
    while(n--){
        solve();
    }   
}