题目描述

       给你一个包含'('和')'的字符串，找出最长有效（格式正确且连续）括号子串的长度。

解题思路：采用数据结构-栈。遍历字符串，当遇到"("时，将下标压入栈中；遇到右括号，则弹出栈顶的左括号，并用当前右括号的下标离栈顶元素（弹出后的栈顶元素）下标的距离来更新最大的有效程度。

代码

#include <iostream>
#include <string>
#include <stack>int max_parenthesis_len(const std::string& str) {int max_len = 0;int n = str.size();std::stack<char> s;int start = 0;//记录第一个有效括号的位置for (int i = 0; i < n; i++) {if (str[i] == '(') {s.push(i); //stack里面只会保存左括号的下标} else {if (s.empty()) { //如果当前为右括号，且没有左括号与之匹配,则直接忽略该右括号start = i + 1;} else {s.pop();//弹出与右括号匹配的左括号int len = 0;if (s.empty()) { //表示stack中有且只有一个左括号与当前右括号匹配len = i - start + 1;} else { //表示stack中有多个左括号可以与当前右括号匹配len = i - s.top(); //这里不加1的原因是，不包含栈顶元素}max_len = std::max(max_len ,len);}}}return max_len;
}void print_result(const std::string& str, int len) {std::cout << "input:" << str << std::endl;std::cout << "output:" << len << std::endl;
}int main()
{// case1: "(()" == >2std::string str = "(()";int len = max_parenthesis_len(str);print_result(str, len);// case2: ")()())" ==> 4str = ")()())";len = max_parenthesis_len(str);print_result(str, len);// case3: "" ==> 0str = "";len = max_parenthesis_len(str);print_result(str, len);return 0;
}

代码输出结果如下

input:(()
output:2
input:)()())
output:4
input:
output:0