理解算法：有效括号的判定方法

"合法括号判定" 在编程中，合法括号的判定是一个基础但重要的问题，它涉及到字符串处理和栈数据结构的应用。通常，我们需要判断一个由括号组成的字符串是否按照正确的规则闭合，例如在代码编辑器或编译器中检查语法错误。这篇文章将介绍如何使用算法来判断括号的合法性，并关联到LeetCode上的相关问题——[20.有效的括号](https://leetcode-cn.com/problems/valid-parentheses)。 首先，我们需要理解括号的匹配规则：'('与')'、'['与']'、'{'与'}'是成对出现的。一个合法的括号序列必须满足以下条件： 1. 空字符串是合法的。 2. 如果`s`是一个合法的括号序列，那么`(` + `s` + `)`也是合法的。 3. 如果`s`和`t`都是合法的括号序列，那么`s` + `t`也是合法的。 解决这个问题的一个经典方法是使用栈数据结构。我们可以遍历输入的括号字符串，遇到每个左括号时将其压入栈中，遇到右括号时检查栈顶元素是否是对应左括号，如果是则出栈，如果不是或者栈为空，则返回非法。遍历完成后，如果栈为空，则说明括号序列合法；否则，非法。 以下是使用栈解决该问题的Python代码实现： ```python def isValid(s): stack = [] mapping = {")": "(", "}": "{", "]": "["} for char in s: if char in mapping: # 如果栈顶元素存在且为对应左括号，出栈 if stack and stack[-1] == mapping[char]: stack.pop() else: return False else: # 遇到左括号，压入栈 stack.append(char) return not stack # 栈为空，合法；否则，非法 ``` 在实际应用中，这个方法不仅可以用于括号，还可以扩展到其他类似的匹配问题，如HTML标签的匹配、XML标签的解析等。对于LeetCode的[20.有效的括号](https://leetcode-cn.com/problems/valid-parentheses)问题，这个解决方案已经足够高效，具有O(n)的时间复杂度和O(1)的空间复杂度，其中n是输入字符串的长度。 此外，还可以使用其他数据结构，如双端队列（deque）来解决此问题，但基本思路仍然是利用栈或队列的特性来跟踪和匹配括号。 理解和掌握合法括号的判定方法是编程基础中的重要一环，对于编写和调试代码有着至关重要的作用。通过学习和实践，我们可以提高编程技能，更好地应对类似问题。