试编写一个算法,检查一个程序中的花括号、方括号和圆 括号是否配对,若能够全部配对则返回1,否则返回0。
时间: 2024-10-16 20:12:38 浏览: 34
为了编写一个检查括号配对的算法,我们可以采用栈数据结构。这个算法的基本步骤如下:
1. 初始化一个空栈。
2. 遍历输入的字符串,对于每个字符:
- 如果遇到 '(', '[', '{',将其压入栈中。
- 如果遇到 ')',']', '}':
- 如果栈为空,说明已经遇到闭合括号但找不到对应的开括号,返回 0(表示不匹配)。
- 否则,弹出栈顶元素,判断是否与当前闭合括号匹配。如果不匹配,同样返回 0。
3. 遍历结束后,如果栈非空,则意味着还有未找到对应开括号的闭合括号,返回 0。
4. 若栈为空,则所有括号都已配对,返回 1。
这是一个简单的线性时间复杂度 O(n) 的算法,其中 n 是输入字符串的长度。
以下是Python代码实现:
```python
def is_bracket_pair(s):
bracket_map = {')': '(', ']': '[', '}': '{'}
stack = []
for char in s:
if char in '([{':
stack.append(char)
elif not stack or stack.pop() != bracket_map[char]:
return 0
return 1 if not stack else 0
# 示例
print(is_bracket_pair("{[]()}")) # 输出: 1
print(is_bracket_pair("({[})")) # 输出: 0
```
阅读全文