根据栈的结构特点,结合已提供的 stack(堆栈)类代码,完成以下括号左右匹配检查的实现。任务要求有效括号字符串需满足:1. 左括号(含英文大括号和英文小括号两种)必须用相同类型的右括号闭合;2. 左括号必须以正确的顺序闭合;3. 注意空字符串可被认为是有效字符串;4. 本任务考察栈的知识,请不要使用列表(list)的属性和功能; 5. 返回数据类型为布尔类型(bool); 6. 所匹配的字符串包含如下:{} [] () <>,均为英文字符。
时间: 2024-02-12 09:03:47 浏览: 49
利用栈实现括号匹配的检验
4星 · 用户满意度95%
好的,以下是实现左右括号匹配检查的代码,符合您的要求:
```python
class Stack:
def __init__(self):
self.top = -1
self.stack = {}
def is_empty(self):
return self.top == -1
def push(self, item):
self.top += 1
self.stack[self.top] = item
def pop(self):
if self.is_empty():
return None
else:
item = self.stack[self.top]
del self.stack[self.top]
self.top -= 1
return item
def peek(self):
if self.is_empty():
return None
else:
return self.stack[self.top]
def size(self):
return self.top + 1
def check_parentheses(string):
s = Stack()
for c in string:
if c in "{[<(":
s.push(c)
elif c in "}])>":
if s.is_empty():
return False
elif c == "}" and s.peek() == "{" or \
c == "]" and s.peek() == "[" or \
c == ">" and s.peek() == "<" or \
c == ")" and s.peek() == "(":
s.pop()
else:
return False
return s.is_empty()
```
这里同样使用了栈的特点,使用 `Stack` 类模拟栈的操作。在 `Stack` 类中,使用一个字典来存储栈中的元素,使用 `top` 来表示栈顶的位置。其中 `push` 方法实现入栈操作,将元素添加到字典中,`pop` 方法实现出栈操作,从字典中删除栈顶元素,`peek` 方法实现查看栈顶元素操作,返回字典中栈顶元素,`size` 方法返回栈的大小。在 `check_parentheses` 函数中,使用 `Stack` 类来判断左右括号是否匹配。如果字符是左括号,则入栈,如果是右括号,则与栈顶元素进行匹配,如果匹配成功则弹出栈顶元素,如果匹配失败则返回 False。在遍历结束后,如果栈为空则表示左右括号匹配成功,否则表示匹配失败。
阅读全文