算法设计:设字符串仅有圆括号、方括号、花括号组成,仅能嵌套;使用顺序栈,编写一个算法判断是否匹配。测试“[{{()}[]}(){[ ]}]”,“{[}]()”。
时间: 2024-05-05 13:15:11 浏览: 17
算法步骤如下:
1. 初始化一个空的顺序栈stack;
2. 遍历字符串中的每个字符char:
1. 如果char是左括号(即圆括号、方括号、花括号中的一种),则将其压入stack中;
2. 如果char是右括号,分以下情况讨论:
1. 如果stack为空,则返回False,因为此时无法匹配;
2. 如果stack的栈顶元素与char不匹配,则返回False;
3. 如果stack的栈顶元素与char匹配,则将栈顶元素弹出;
3. 如果遍历完整个字符串后,stack不为空,则返回False;
4. 否则返回True。
实现代码如下:
```python
def is_matched(s):
stack = [] # 初始化一个空的顺序栈
for char in s:
if char in ['(', '[', '{']:
stack.append(char) # 如果char是左括号,则将其压入stack中
elif char in [')', ']', '}']:
if not stack: # 如果stack为空,则返回False
return False
top = stack.pop() # 取出stack的栈顶元素
if (char == ')' and top != '(') or \
(char == ']' and top != '[') or \
(char == '}' and top != '{'): # 如果栈顶元素与char不匹配,则返回False
return False
if stack: # 如果遍历完整个字符串后,stack不为空,则返回False
return False
return True # 否则返回True
# 测试
s1 = "[{{()}[]}(){[ ]}]"
s2 = "{[}]()"
print(is_matched(s1)) # 输出True
print(is_matched(s2)) # 输出False
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)