平衡括号问题 python
时间: 2024-10-19 15:14:13 浏览: 5
平衡括号问题是计算机科学中的一种经典问题,通常涉及检查给定的字符串是否仅包含有效的平衡括号序列。例如,"()"、"[]"、"{}"被认为是平衡的,而")("、"]{"则不是。在Python中,可以使用栈数据结构来解决这个问题。基本的算法步骤如下:
1. 创建一个空栈。
2. 遍历输入字符串的每个字符,如果是左括号(如'('、'{'、'['),将其压入栈中。
3. 如果遇到右括号(如')'、'}'、']'),检查栈顶元素是否与其匹配。如果匹配,弹出栈顶元素;如果不匹配,则返回False,表示括号不平衡。
4. 循环结束后,如果栈为空,说明所有括号都已配对,返回True;否则返回False。
以下是一个简单的Python函数示例:
```python
def is_balanced(s):
stack = []
pairs = {')': '(', '}': '{', ']': '['}
for char in s:
if char in pairs.values():
stack.append(char)
elif char in pairs.keys() and not stack or stack.pop() != pairs[char]:
return False
return not stack # 返回栈是否为空
# 示例
print(is_balanced("({[()]})")) # True
print(is_balanced("([)]")) # False
```
阅读全文