### 使用 Python 栈实现括号匹配的解决方案 #### 1. 栈的概念及其应用 栈是一种遵循“先进后出”（LIFO, Last In First Out）原则的数据结构，在处理嵌套关系时特别有用。对于括号匹配问题，可以通过栈来跟踪未闭合的左括号位置。 当遇到左括号 `(` 或 `[` 时将其索引入栈；当遇到右括号 `)` 或 `]` 时弹出栈顶元素并验证其是否与当前右括号匹配。如果不匹配，则说明存在非法括号组合[^3]。 --- #### 2. 示例代码：基于栈的括号匹配算法 以下是完整的 Python 示例代码： ```python def is_valid_parentheses(s: str) -> bool: # 定义一个字典用于存储括号之间的映射关系 parentheses_map = {')': '(', '}': '{', ']': '['} # 创建一个空栈 stack = [] # 遍历输入字符串中的每一个字符 for char in s: if char in parentheses_map.values(): # 如果是左括号，压入栈中 stack.append(char) elif char in parentheses_map.keys(): # 如果是右括号，检查栈顶是否有对应的左括号 if not stack or stack.pop() != parentheses_map[char]: return False else: # 忽略其他无关字符 continue # 最终检查栈是否为空 return len(stack) == 0 ``` 上述代码实现了以下逻辑： - **初始化**：定义了一个字典 `parentheses_map` 来记录每种右括号对应哪种左括号。 - **遍历字符串**：逐一遍历输入字符串中的每个字符。 - **操作栈**：如果是左括号则压入栈中；如果是右括号，则尝试从栈中弹出顶部元素并与之匹配。 - **返回结果**：最后检查栈是否为空。如果为空，则表明所有括号都已成功配对[^4]。 --- #### 3. 测试案例 为了验证该函数的功能，可以运行如下测试用例： ```python test_cases = [ ("()", True), # 正确的简单括号 (")(", False), # 错误顺序的括号 ("(())", True), # 多层嵌套的正确括号 ("(()", False), # 不完全闭合的括号 ("{[]}", True), # 含有多种类型的括号 ("([)]", False) # 混乱的括号序列 ] for i, (input_str, expected_output) in enumerate(test_cases): result = is_valid_parentheses(input_str) print(f"Test Case {i + 1}: {'Pass' if result == expected_output else 'Fail'}") ``` 此部分展示了不同场景下的表现情况，并帮助确认程序能够正常工作。 --- #### 4. 扩展功能：寻找最长的有效括号子串长度 除了简单的括号合法性校验外，还可以进一步扩展到计算最长有效括号子串的长度。具体做法已在 LeetCode 的题目中有详细介绍。下面是一个简化版的例子： ```python def longest_valid_parentheses(s: str) -> int: max_length = 0 stack = [-1] # 初始化栈底为 -1 表示起始位置 for i, char in enumerate(s): if char == '(': stack.append(i) # 左括号索引进栈 else: stack.pop() # 右括号触发弹栈 if not stack: stack.append(i) # 若栈空重新设置起点 else: current_length = i - stack[-1] max_length = max(max_length, current_length) return max_length ``` 这段代码通过维护一个特殊的栈结构解决了更复杂的需求。 ---