设字符串仅有圆括号、方括号、花括号组成,仅能嵌套;使用顺序栈,编写一个算法判断是否匹配。测试“[{{()}[ ]}(){[ ]}]”, “{ [ } ]()”。
时间: 2024-01-12 07:03:35 浏览: 14
算法思路:
1. 遍历字符串,遇到左括号就将其入栈。
2. 遇到右括号,判断栈顶元素是否与之匹配,若匹配则将栈顶元素出栈,否则返回匹配失败。
3. 遍历结束后,如果栈为空,则匹配成功,否则匹配失败。
代码实现:
```python
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[-1]
def size(self):
return len(self.items)
def is_matched(s):
stack = Stack()
for ch in s:
if ch in '([{':
stack.push(ch)
elif ch in ')]}':
if stack.is_empty():
return False
if ch == ']' and stack.peek() == '[' or \
ch == ')' and stack.peek() == '(' or \
ch == '}' and stack.peek() == '{':
stack.pop()
else:
return False
return stack.is_empty()
# 测试
print(is_matched("[{{()}[ ]}(){[ ]}]")) # True
print(is_matched("{ [ } ]()")) # False
```
输出结果:
```
True
False
```
注:本题使用栈可以直接实现,无需使用递归或其他数据结构。
阅读全文