Python栈的应用：最长有效括号子串的求解
最长有效括号子串是指在一个字符串中，包含的最长的合法的括号子串的长度。合法的括号子串是指括号必须是成对出现，并且左括号在右括号之前闭合的子串，如“(()())”就是一个合法的括号子串。
利用栈可以有效地解决这个问题。遍历整个字符串，如果遇到左括号，就将其压入栈中。如果遇到右括号，就将栈顶元素弹出，并计算当前子串的长度。如果当前栈为空，说明前面的所有括号都已匹配，就可以将当前子串的长度和已知的最长子串的长度进行比较，并记录下较大的那个值。
接下来，让我们看一下Python代码实现：
def longest_valid_parentheses(s):
stack = [-1] # 栈中初始值为-1
max_length = 0 # 初始化最长子串长度为0
for i in range(len(s)):
if s[i] == '(':
stack.append(i) # 将左括号位置压入栈中
else:
if len(stack) > 1: # 如果栈不为空
stack.pop() # 弹出栈顶元素
max_length = max(max_length, i - stack[-1]) # 计算当前子串长度并更新最长子串长度
else:
stack[0] = i # 更新栈中元素的位置
return max_length
在这个实现中，栈的初始值为-1，这是为了处理特殊情况，比如字符串全是右括号的情况，这样可以让程序正确处理。在每次遇到右括号时，先判断栈是否为空。如果栈不为空，则弹出栈顶元素，计算当前子串的长度，并更新最长子串的长度。如果栈为空，则说明前面的括号都已经匹配，需要更新栈中元素的位置，因为之前的子串已经不再合法。
下面是一个例子，使用“pidancode.com”作为输入字符串：
s = 'pidancode.com' print(longest_valid_parentheses(s)) # 输出结果为2
在这个例子中，最长的有效括号子串是“()”，长度为2。
相关文章