先实现栈的基本操作:初始化,入栈,出栈等。 每读入一个括号,若是右括号,则或者是置于栈顶的左括号得以消解,或者是不合法的情况;若是左括号,则直接入栈。 可用顺序栈或者链栈实现。
时间: 2023-06-01 11:02:41 浏览: 94
栈的顺序实现,入栈、出栈等
以下是使用顺序栈实现括号匹配的示例代码:
```python
class Stack:
def __init__(self):
self.stack = []
def is_empty(self):
return len(self.stack) == 0
def push(self, item):
self.stack.append(item)
def pop(self):
if self.is_empty():
return None
else:
return self.stack.pop()
def top(self):
if self.is_empty():
return None
else:
return self.stack[-1]
def size(self):
return len(self.stack)
def is_valid_parentheses(s: str) -> bool:
stack = Stack()
for c in s:
if c == '(' or c == '[' or c == '{':
stack.push(c)
elif c == ')':
if stack.top() == '(':
stack.pop()
else:
return False
elif c == ']':
if stack.top() == '[':
stack.pop()
else:
return False
elif c == '}':
if stack.top() == '{':
stack.pop()
else:
return False
return stack.is_empty()
```
该代码使用了一个名为 Stack 的类来实现栈的基本操作。is_valid_parentheses 函数接受一个字符串作为参数,遍历字符串中的每一个字符。如果是左括号,则将其入栈;如果是右括号,则与栈顶的左括号匹配,如果匹配成功,则将栈顶元素出栈,否则返回 False。最后,如果栈为空,则表示所有括号都匹配成功,返回 True;否则返回 False。
示例测试代码:
```python
assert is_valid_parentheses('()') == True
assert is_valid_parentheses('()[]{}') == True
assert is_valid_parentheses('(]') == False
assert is_valid_parentheses('([)]') == False
assert is_valid_parentheses('{[]}()') == True
```
阅读全文