Emulate the stack behaviour using the list data structure.

a) Complete the methods of the following Stack class according to their description

In [ ]:

class Stack: def __init__(self): """ Initialize a new stack """ self.elements = [] def push(self, new_item): """ Append the new item to the stack """ ## CODE HERE ### def pop(self): """ Remove and return the last item from the stack """ ## CODE HERE ### def size(self): """ Return the total number of elements in the stack """ ## CODE HERE ### def is_empty(self): """ Return True if the stack is empty and False if it is not empty """ ## CODE HERE ### def peek(self): """ Return the element at the top of the stack or return None if the stack is empty """ ## CODE HERE ###

b) Use the Stack class that you defined in Q3a to complete the code of the is_valid() function, which checks whether the order of the brackets of an arithmetic expression is correct. Some examples are given below:

In [18]:

exp1 = "(2+3)+(1-5)" # True exp2 = "((3*2))*(7/3))" # False exp3 = "(3*5))]" # False

In [17]:

def is_valid(exp): """ Check the order of the brackets Returns True or False """ opening = ['(', '[', '{'] closing = [')', ']', '}'] ## CODE HERE ## return ## CODE HERE ## is_valid(exp1) is_valid(exp2) is_valid(exp3)

c) Use the Stack class that you defined in Q3a to complete the code of the count_pairs() function, which returns the number of the valid bracket pairs of an arithmetic expression. Some examples are given below:

In [13]:

exp1 = "(2+3)+(1-5)" # 2 pairs exp2 = "((([()])))" # 5 pairs exp3 = "[([])" # 2 pairs

In [12]:

def count_pairs(exp): """ Count the valid number of brackets Returns the total number of valid brackets in the string """ opening = ['(', '[', '{'] closing = [')', ']', '}'] ## CODE HERE ## return ## CODE HERE ## count_pairs(exp1) count_pairs(exp2) count_pairs(exp3)

class Stack:

 def __init__(self):

  """ Initialize a new stack """

  self.elements = []

 def push(self, new_item):

  """ Append the new item to the stack """

  self.elements.append(new_item)

 def pop(self):

  """ Remove and return the last item from the stack """

  return self.elements.pop()

 def size(self):

  """ Return the total number of elements in the stack """

  return len(self.elements)

 def is_empty(self):

  """ Return True if the stack is empty and False if it is not empty """

  return self.size() == 0

 def peek(self):

  """ Return the element at the top of the stack or return None if the stack is empty """

  if(self.is_empty()):

    return None

  else:

    return self.elements[0]

 

 

def is_valid(exp):

 """ Check the order of the brackets

   Returns True or False

 """

 opening = ['(', '[', '{']

 closing = [')', ']', '}']

 

 is_exp_valid = True

 stack = Stack()

 

 #save all brackets on stack

 for i in exp:

   if i in opening or i in closing:

     stack.push(i)

 

 #check if even, if not mean this is not valid

 if stack.size() % 2 == 1:

    is_exp_valid = False

 else:

   while not stack.is_empty(): #while there's an element in the stack

     first_elem = stack.peek() 

     poped_elem = stack.pop() #last element on stack; also removed the last elem on stack

     opening_index = None

     closing_index = None

 

     #check if the first elem and last elem on the stack is opening or closing bracket

     if first_elem in opening:

       opening_index = opening.index(first_elem)

       closing_index = closing.index(poped_elem)

     elif first_elem in closing:

       opening_index = opening.index(poped_elem)

       closing_index = closing.index(first_elem)

 

     #compare if they are pair

     if opening_index != closing_index:

       is_exp_valid = False

       break

     else:

       stack.elements.pop(0) #remove the first elem on stack

 

 return is_exp_valid

 

 

def count_pairs(exp):

 """ Count the valid number of brackets

   Returns the total number of valid brackets in the string

 """

 opening = ['(', '[', '{']

 closing = [')', ']', '}']

 is_exp_valid = True

 stack_opening = Stack()

 

 #save all opening brackets

 for ii in exp:

  if ii in opening:

    stack_opening.push(ii)

 

 #save all closing brackets

 stack_closing = Stack()

 for ii in exp:

  if ii in closing:

    stack_closing.push(ii)

 

 count = 0

 

 while not (stack_opening.is_empty() or stack_closing.is_empty()):

   pop_elem = stack_opening.pop() #get the last elem on list of opening brackets and remove

    #check if the last elem of opening list is same with the first elem of the closing list

   if opening.index(pop_elem) == closing.index(stack_closing.peek()):

     count = count + 1 #count if pairs

   stack_closing.elements.pop(0) #remove the first elem of closing list

 

 return count

 

 

if __name__ == "__main__":

   exp1 = "(2+3)+(1-5)"

   exp2 = "((3*2))*(7/3))"

   exp3 = "(3*5))]"

 

   print(is_valid(exp1))

   print(is_valid(exp2))

   print(is_valid(exp3))

 

 

   c_exp1 = "(2+3)+(1-5)" # 2 pairs

   c_exp2 = "((([()])))" # 5 pairs

   c_exp3 = "[([])" # 2 pairs

   print(count_pairs(c_exp1))

   print(count_pairs(c_exp2))

   print(count_pairs(c_exp3))