### Python 实现泛括号匹配算法 泛括号匹配算法通常涉及多种类型的括号（如圆括号`()`、方括号`[]`和花括号`{}`），并验证这些括号是否成对出现且嵌套正确。以下是基于栈的数据结构来实现这一功能的代码示例： #### 使用栈实现泛括号匹配算法 ```python from pythonds.basic.stack import Stack def is_parentheses_balanced(symbol_string): s = Stack() balanced = True index = 0 while index < len(symbol_string) and balanced: symbol = symbol_string[index] if symbol in "([{": s.push(symbol) elif symbol in ")]}": if s.is_empty(): balanced = False else: top = s.pop() if not matches(top, symbol): balanced = False index += 1 if balanced and s.is_empty(): return True else: return False def matches(open_symbol, close_symbol): opens = "([{" closers = ")]}" return opens.index(open_symbol) == closers.index(close_symbol) # 测试函数 print(is_parentheses_balanced("{[()]}")) # 输出: True print(is_parentheses_balanced("{[(])}")) # 输出: False ``` 上述代码实现了泛括号匹配的功能，其中使用了 `pythonds` 库中的 `Stack` 类[^4]。该类提供了基本的栈操作方法，例如 `push` 和 `pop`。 #### 关键逻辑说明 1. **遍历字符串**：逐字符读取输入字符串，遇到左括号时将其压入栈中。 2. **匹配右括号**：当遇到右括号时，检查栈顶元素是否为其对应的左括号。如果栈为空或不匹配，则返回 `False`。 3. **最终状态检查**：完成遍历后，需确认栈是否为空。只有在栈为空的情况下才表示所有括号均成功匹配[^1]。 #### 示例解释 - 输入 `{[()]}` 的情况下，程序依次处理每个括号并对它们进行匹配，最后返回 `True` 表明括号完全匹配。 - 对于输入 `{[(])}`，由于存在不合法的嵌套关系 `[` 和 `)` 不匹配，因此返回 `False`。 --- ###