7-8 最长有效括号串 (20 分)

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

输入格式:

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

输出格式:

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

输入样例:

())(()())

输出样例:

在这里给出相应的输出。例如：

( ( ) ( ) )

 

挂掉的代码

#include<iostream>
using namespace std;
int main(){
	string s;
	char c;
	while(c!='\n'){
		c=getchar();
		if(c=='('||c==')'){
			s+=c;
		}
	}
	int max=-1;
	int num=0;
	int maxid=0;
	for(int i=0;i<s.length();i++){
		string s2=s.substr(i);
		int flag=0;
		for(int l=0;l<s2.length();l++){
			if(s2[l]=='('){
				flag++;
			}else{
				flag--;
				if(flag==0){
					if(num>max){
					maxid=i;
					max=num;
					}
				}
				if(flag<0){break;}
				num+=2;
			}
		}
		if(flag>0){
			num=0;
		}
		if(num>max){
			maxid=i;
			max=num;
		}num=0;
		//cout<<maxid<<max<<endl;
	}
	int k=0;
	for(int i=0;i<max&&max>1;i++){
		cout<<s[maxid+i]<<" ";
	}
	cout<<endl;
	return 0;
}

这道题刚好是LeetCode的原题

https://leetcode-cn.com/problems/longest-valid-parentheses/

32. Longest Valid Parentheses

查到的一种力扣的解法

class Solution {  
public:
    int longestValidParentheses(string s) {
        int ans = 0;
        int idx = 0;
        stack<pair<char, int>> sk;
        sk.push(make_pair<char, int>('b', 0));
        for (char c : s){
            idx++;
            if (c == '(')
                sk.push(make_pair(c, idx));
            else{
                pair<char, int> p = sk.top();
                if (p.first == '('){
                    sk.pop();
                    ans = max(ans, idx - sk.top().second); 
                }
                else{
                    assert(p.first == 'b');
                    sk.top().second = idx;
                }
            }
        }
        return ans;
    }
};