算法设计:设字符串仅有圆括号、方括号、花括号组成,仅能嵌套;使用顺序栈,编写一个算法判断是否匹配。测试“[{{()}[]}(){[ ]}]”,“{[}]()”。
时间: 2024-05-15 10:16:11 浏览: 65
算法思路:
1. 创建一个空栈。
2. 从左到右扫描字符串中的每一个字符。
3. 如果当前字符是左括号,将其压入栈中。
4. 如果当前字符是右括号,从栈中弹出一个元素,将其与当前字符进行匹配。
5. 如果匹配成功,继续扫描字符串。
6. 如果匹配失败,返回false。
7. 如果扫描完整个字符串后栈为空,返回true,否则返回false。
代码实现:
```python
def is_match(s):
stack = []
for c in s:
if c in "([{":
stack.append(c)
elif c in ")]}":
if not stack:
return False
left = stack.pop()
if (c == ')' and left != '(') or \
(c == ']' and left != '[') or \
(c == '}' and left != '{'):
return False
return not stack
s1 = "[{{()}[]}(){[ ]}]"
s2 = "{[}]()"
print(is_match(s1)) # True
print(is_match(s2)) # False
```
测试结果:
```
True
False
```
阅读全文