t0ur1st

题目描述：

给定一个只含左右小括号的括号串序列exp，找出其中最长的有效括号串。

输入描述:

输入一个只含左右小括号的括号字符串，以换行结束。

输出描述:

输出其中最长的有效括号串。输出的每个括号之后均有空格。

输入样例:

())(()())

输出样例:

( ( ) ( ) )

解题思路：

自定义函数matched用来判断括号是否匹配，然后双重for循环暴力破解找最长有效括号串即可。

AC代码：

#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
bool matched(string str)
{
    stack<char> s;
    Up(i,0,str.length()-1)
    {
        if(str[i] == '(')
        {
            s.push(str[i]);
        }
        else  //str[i]==')'
        {
            if(s.empty() || s.top()!='(')
            {
                return false;
            }
            else s.pop();
        }
    }
    return s.empty();
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    string str;
    getline(cin,str);
    int len = str.length()-1;
    int bg = -1,ed = -1,cnt = 0;   //最长有效括号的起点、终点和长度
    Up(i,0,len)
    {
        Up(j,i+1,len)
        {
            int _ = j-i+1;   //当前字符串长度
            if(matched(str.substr(i,_)))   //判断是否有效
            {
                if(_ > cnt)
                {
                    cnt = _;
                    bg = i;
                    ed = j;
                }
            }
        }
    }
    if(bg!=-1 && ed!=-1)
    {
        Up(i,bg,ed)
        {
            cout << str[i] << " ";
        }
    }
    return 0;
}