寻找最长有效括号的子字符串

在一个字符串中，寻找包含最长的有效括号的子字符串。
如：输入字符串“(a))”最长有效括号为(a)
字符串“()())”最长有效括号为()()
字符串“a)((b)(c)d”最长有效括号为(b)(c)
字符串“a)((b)(c)d)”最长有效括号为((b)((c)d)
想到用栈来做，解决了括号的问题解决不了字母的问题，将字母放进队列中解决不了开头几个字母的问题

你题目的解答代码如下：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str, str2;
    int q[1000], l=0, i, si=9999999,ei=0,ts;
    getline(cin,str);
    for (i = 0; i < str.size(); i++)
    {
        if (str[i]=='(')
        {
            q[l++] = i;
        }
        else if (str[i]==')' && l>0)
        {
            ts = q[--l];
            if (ts < si)
                si = ts;
            ei = i;
        }
    }
    str2 = str.substr(si, ei-si+1);
    cout << str2;
    return 0;
}

如有帮助，请点击我的回答下方的【采纳该答案】按钮帮忙采纳下，谢谢!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;

char s[maxn];
int dp[maxn];

int solve1(int len, char s[]) {
    int Max = 0;
    for(int i = 0; i < len; i++)
        dp[i] = 0;
    for(int i = 1; i < len; i++) {
        if(s[i] == ')') {
            int j = i-1-dp[i-1];
            if(j >= 0 && s[j] == '(') {
                dp[i] = dp[i-1] + 2;
                if(j-1 >= 0) 
                    dp[i] += dp[j-1];
            }
        }
        if(Max < dp[i]) Max = dp[i];
    }
    return Max;
}

int solve2(int len, char s[]) {
    int Max = 0;
    for(int i = 0; i < len; i++) 
        dp[i] = 0;
    for(int i = len-2; i >= 0; i--) {
        if(s[i] == '(') {
            int j = i + 1 + dp[i+1];
            if(j < len && s[j] == ')') {
                dp[i] += dp[i+1] + 2;
                if(j+1 < len)
                    dp[i] += dp[j+1];
            }
            if(Max < dp[i]) Max = dp[i];

        }
    }
    return Max;
}

int main(){
    while(~scanf("%s", s)){
        int len = strlen(s);
        printf("%d\n", solve1(len, s));
        printf("%d\n", solve2(len, s));
    }
    return 0;
}

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int func(string s)
{
    int maxlen = 0;
    stack<int> stk;
    stk.push(-1);
    string res;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] != ')')
        {
            stk.push(i);
        }
        else
        {
            while (!stk.empty() && s[stk.top()]!='(')
            {
                stk.pop();
            }
            if(!stk.empty() && s[stk.top()]=='(')
            {
                stk.pop();
            }
            // stk.pop();
            if (stk.empty())
            {
                stk.push(i);
            }
            else
            {
                if(maxlen < i - stk.top())
                {
                    res="";
                    for(int j=stk.top()+1;j<=i;j++)
                    {
                        res+=s[j];
                    }
                }
                maxlen = max(maxlen, i - stk.top());
                cout << res << endl;
            }
        }
    }
    return maxlen;
}
int main()
{
    string s;
    cin >> s;
    func(s);
    return 0;
}

最后一行是输出结果～

// ConsoleApplication31.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <stack>
using namespace  std;

int main()
{
    string str = "a)((b)(c)d)aaa(aa(aaaaaaaaaaa)((";
    int len = str.size();
    stack<pair<char, int>> st;
    int nl,nr;
    int nmax = -1;
    for (int i = 0; i < len; i++) {
        if (str[i] == '(' ||str[i] == ')') {
            if (st.empty())
            {
                st.push(make_pair(str[i], i));
            }
            else {
                if (st.top().first == '(' && str[i] == ')')
                {
                    int tmp = (i - st.top().second + 1);
                    if (tmp > nmax) {
                        nmax = tmp;
                        nl = st.top().second;
                        nr = i;
                    }
                    st.pop();
                }
                else {
                    st.push(make_pair(str[i], i));
                }

            }
        }
    }
    cout << str.substr(nl, nr - nl + 1);
}

这个思路不是应该去统计字符串内的左右括号'(' ')' '[' '] '{' '}'嘛，成对出现，左右顺序出现就记录输出嘛.