首页 > 代码库 > 喵哈哈村的括号序列

喵哈哈村的括号序列

2024-09-07 15:07:25   217人阅读

描述

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

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

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

不知道你能找到吗？

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

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

复制 
2
)((())))(()())
)(
6
0

#include <iostream>
#include <stack>
#include <string>
#include <cmath>
#include <math.h>
#include <stdio.h>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string a;
        cin>>a;
        stack<int> s;
        s.push(-1);
        s.push(0);
        for(int i = 1;i < a.length(); i++)
        {
            if(a[s.top()] == ‘(‘ && a[i] == ‘)‘)
            {
                s.pop();
            }
            else{
                s.push(i);
            }
        }
        s.push(a.length());
        int falg = s.top();
        s.pop();
        int cmp;
        int M = -1;
        while(!s.empty())
        {
            cmp = s.top();
            s.pop();
            M = max(M,abs(cmp-falg));
            falg = cmp;
        }
        cout<<M-1<<endl;
    }
    return 0;
}

　　

喵哈哈村的括号序列


联系
我们