COMPSCI代写：CS105 ADT

Introduction

代写几个基础的Python的ADT的Lab小作业，跑过测试即可。

Question 1

A “Stack” is an abstract data type for storing a collection of items, where items are both added and removed from one end of the collection. The methods for adding and removing items from a stack are traditionally called “push()” and “pop()” respectively. A method called “peek()” returns the value on the top of the stack, but does not remove it from the stack. A “size()” method returns the number of items on the stack, and a method “is_empty()” returns a boolean indicating if the stack is empty.
For this exercise, you will provide a complete implementation of the Stack ADT. You can implement the Stack ADT in any way that you like, but using a Python list to store the items is certainly the simplest way.
The method names are given below as a guide to help you:

class Stack:
  def __init__(self):
  def is_empty(self):
  def push(self, item):
  def pop(self):
  def peek(self):
  def size(self):

Question 2

IMPORTANT: For this exercise, you will be defining a function that USES the Stack ADT. A stack implementation is provided to you as part of this exercise - you should not use your own Stack class. Instead, simply use the functions: Stack(), push(), pop() and is_empty() where necessary inside your function definition.

For this exercise, you must write a function called balanced_brackets(). This function will be passed a string as an input, and you must check that any parentheses or angled brackets in the string.
Here are a few examples of strings where brackets are correctly balanced:

a(<bcd>ef)g
abcde
a(b)c<<d>e(fg)>

and here are a few examples where the brackets are not balanced:

ab(cde>
a<bc>)def<g>
ab)c

Your balanced_brackets() function should return True if the input string is balanced, and False otherwise. Remember, you can assume that an implementation of the Stack ADT is available to you. It is likely that your function definition will begin as follows:

def balanced_brackets(text):
  s = Stack()
  ...

Question 3

IMPORTANT: For this exercise, you will be defining a function that USES the Stack ADT. A stack implementation is provided to you as part of this exercise - you should not use your own Stack class. Instead, simply use the functions: Stack(), push() and pop() where necessary inside your function definition.

For this exercise, you must write a function called evaluate_postfix(). This function will be passed a list of operators and operands, representing a postfix expression, and your function should evaluate it. In addition to the usual +, -, *, / operators, your function should also support a new operator: ^. This new operator has the same meaning as Python’s exponentiation operator **.
As an example, the postfix expression: 2 4 3 * ^ would evaluate to 4096.
You will probably find it useful to also define a ‘compute()’ function, which is passed two operands and an operator and which returns the result of applying the operator to the operands.
Include both the evaluate_postfix() and compute() function in your solution below. You can assume the input expression will be valid.
Remember, you can assume that an implementation of the Stack ADT is available to you. It is likely that your function definition will begin as follows:

def evaluate_postfix(text):
  s = Stack()
  ...

Question 4

IMPORTANT: In this exercise, implementations of both the Stack and Queue ADTs are available to you. You can use the functions Stack(), push(), pop() as well as Queue(), enqueue() and dequeue() as necessary in your function definition.

For this exercise, you must write a function called mirror() which is passed a Queue as an input. Your function must modify the Queue, so that the queue items appear in their original order followed by a copy of the queue items in reverse order.
HINT: It will be useful to make use of a Stack and a Queue to help you mirror the elements in the queue.

Question 5

A “Queue” is an abstract data type for storing a collection of items, where items are added to one end and removed from the opposite end of the collection. The methods for adding and removing items from a queue are traditionally called “enqueue()” and “dequeue()” respectively.

IMPORTANT: In this exercise, implementations of both the Stack and Queue ADTs are available to you. You can use the functions Stack(), push(), pop() as well as Queue(), enqueue() and dequeue() as necessary in your function definition.

For this exercise, you must write a function called reverse() which is passed a Queue as an input. Your function must modify the Queue, so that the elements in the queue are rearranged into reverse order.
HINT: It will be useful to make use of a Stack to help you reverse the elements in the queue.