东大15春学期《数据结构与算法》在线作业3答案
- 格式：docx
- 大小：36.71 KB
- 文档页数：4
东大15春学期《数据结构与算法》在线作业3答案
本文档是东大15学期《数据结构与算法》在线作业3的答案。在这份答案中，我们将讨论作业中的题目并给出相应的解答。
题目1
题目描述：
题目1要求我们实现一个栈的数据结构，并完成入栈(push)和出栈(pop)的操作。
解答：
我们可以使用数组来实现栈的数据结构。具体实现如下：
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return None
def is_empty(self):
return len(self.stack) == 0
题目2
题目描述：
题目2要求我们判断一个字符串是否是有效的括号序列。即括号的开闭必须是匹配的。
解答：
我们可以使用栈来判断括号序列的有效性。遍历字符串，如果遇到左括号，则将其入栈；如果遇到右括号，则判断栈顶元素是否与之匹配，若匹配则继续遍历，若不匹配则返回False。遍历完字符串后，若栈为空，则返回True，否则返回False。
具体实现如下：
def is_valid_brackets(s):
stack = []
brackets = {'(': ')', '[': ']', '{': '}'}
for char in s:
if char in brackets.keys():
stack.append(char)
else:
if not stack or brackets[stack.pop()] != char:
return False
return len(stack) == 0
以上就是《数据结构与算法》在线作业3的答案，希望能对你有所帮助。
