Python 3.x

There's a lot to this question:

TStack.py:

 A stack (also called a pushdown or LIFO stack) is a compound # data structure in which the data values are ordered according # to the LIFO (last-in first-out) protocol. # # Implementation: # This implementation was designed to point out when ADT operations are # used incorrectly. def create(): """  Purpose  creates an empty stack  Return  an empty stack  """  return '__Stack__',list() def is_empty(stack): """  Purpose  checks if the given stack has no data in it  Pre-conditions:  stack is a stack created by create()  Return:  True if the stack has no data, or false otherwise  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error : Expected __Stack__ but received '+t return len(s) == 0 else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def size(stack): """  Purpose  returns the number of data values in the given stack  Pre-conditions:  stack: a stack created by create()  Return:  The number of data values in the queue  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t return len(s) else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def push(stack, value): """  Purpose  adds the given data value to the given stack  Pre-conditions:  queue: a stack created by create()  value: data to be added  Post-condition:  the value is added to the stack  Return:  (none)  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t s.append(value) else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def pop(stack): """  Purpose  removes and returns a data value from the given stack  Pre-conditions:  stack: a stack created by create()  Post-condition:  the top value is removed from the stack  Return:  returns the value at the top of the stack  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t return s.pop() else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) def peek(stack): """  Purpose  returns the value from the front of given stack without removing it  Pre-conditions:  stack: a stack created by create()  Post-condition:  None  Return:  the value at the front of the stack  """  if type(stack) is tuple: t,s = stack assert t == '__Stack__', 'Type Error: Expected __Stack__ but received '+t return s[-1] else: assert False, 'Type Error: Expected __Stack__ but received '+str(type(stack)) 

TQueue.py:

def create(): """  Purpose  creates an empty queue  Return  an empty queue  """  return '__Queue__',list() def is_empty(queue): """  Purpose  checks if the given queue has no data in it  Pre-conditions:  queue is a queue created by create()  Return:  True if the queue has no data, or false otherwise  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return len(q) == 0 else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def size(queue): """  Purpose  returns the number of data values in the given queue  Pre-conditions:  queue: a queue created by create()  Return:  The number of data values in the queue  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return len(q) else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def enqueue(queue, value): """  Purpose  adds the given data value to the given queue  Pre-conditions:  queue: a queue created by create()  value: data to be added  Post-condition:  the value is added to the queue  Return:  (none)  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t q.append(value) else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def dequeue(queue): """  Purpose  removes and returns a data value from the given queue  Pre-conditions:  queue: a queue created by create()  Post-condition:  the first value is removed from the queue  Return:  the first value in the queue  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return q.pop(0) else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue)) def peek(queue): """  Purpose  returns the value from the front of given queue without removing it  Pre-conditions:  queue: a queue created by create()  Post-condition:  None  Return:  the value at the front of the queue  """  if type(queue) is tuple: t,q = queue assert t == '__Queue__', 'Type Error: Expected __Queue__ but received '+t return q[0] else: assert False, 'Type Error: Expected __Queue__ but received '+str(type(queue))

Question 2 (16 points): Purpose: To work with ADTs on the ADT programming side. To learn that multiple implementations can have an identical interface Degree of Difficulty: Easy The parentheses in an expression are balanced if an opening parenthesis has a corresponding closing parenthesis ), an opening curly brace has a corresponding closing one l, and an opening square bracket has a closing one For example, (atb) is balanced because it has both an opening and closing parenthesis. On the other hand, the expression \(xty)/(z) is not balanced because it does not have a closing curly brace. Similarly, [atb] (xty)] is not balanced because it does not have an opening square bracket. In addition to the above, every opening parenthesis, curly brace or square bracket must have a corre- sponding closing parenthesis, curly brace or square bracket to its right. For example, [a-b) (c 'dl is not balanced. Though there is one opening parenthesis and one closing parenthesis, this statement is not balanced because the closing parenthesis is not to the right of the opening parenthesis. Furthermore, a parenthesis can only close when all parentheses opened after it are closed. For example [C atb] 5) is not balanced because there has to be a closing parenthesis before the closing square bracket. Every parenthesis, curly brace or square bracket opened last should be closed first. The expres- sion should be (a+b)*5] to be balanced. Your task is as follows: Using the Stack ADT, implement a function that accepts an expression and de- termines if the parentheses in the expression are balanced and prints to the screen if the expression is balanced or not. For example, given the following expression, [ (a blb Ic(d+e) -fl gl the function will return False Using the Stack ADT Download the Stack ADT implementation named TStack.py from the Assignment 4 page on Moodle. To help you avoid errors, this implementation of the Stack ADT does not allow you to violate the ADT in a careless way. You do not need to understand the code in the file TStack.py. You do not even need to look at it. We will study simpler and more accessible implementations later in the course. You should focus on using the Stack ADT operations correctly. TStack.py has the same Stack ADT interface, and has been thoroughly tested. If your script does not use the Stack ADT correctly, or if you violate the ADT Principle, a runtime error will be caused