1. 括号匹配问题 算法思路: 算法实现(Python):
时间: 2024-01-07 17:06:03 浏览: 91
这是一个经典的栈应用题目,算法思路如下:
1. 遍历字符串中的每个字符,若是左括号,则将其入栈;
2. 若是右括号,则判断栈是否为空,若为空,则括号不匹配,直接返回False;若不为空,则将栈顶元素出栈,并判断是否与当前右括号匹配,若不匹配,则返回False;
3. 遍历完字符串后,如果栈为空,则括号匹配,返回True;否则,括号不匹配,返回False。
下面是算法的 Python 实现代码:
```python
def is_valid_parentheses(s: str) -> bool:
stack = []
for ch in s:
if ch == '(' or ch == '[' or ch == '{':
stack.append(ch)
else:
if not stack:
return False
if ch == ')' and stack[-1] != '(':
return False
if ch == ']' and stack[-1] != '[':
return False
if ch == '}' and stack[-1] != '{':
return False
stack.pop()
return not stack
```
这个函数的输入参数是一个字符串,表示待检验的括号序列,返回值为True或False,分别表示括号序列是否匹配。
阅读全文