Due Monday Feb 27 at 9pm. Upload to Desire 2 Learn dropbox for homework 6.
You are going download the linked_stack_hw6.py source code file. It contains a definition of a stack ADT implemented as a linked list. This file also contains a set of unit tests that test each method of the LinkedStack class. Your task is the following:
A. Implement the following LinkedStack methods (please note the comments indicating HOW these should be implemented):
push_seq(self, seq)as_string(self)B. Implement the following TestLinkedStackMethods methods:
def test_is_empty(self)def test_push(self)def test_push_seq(self)def test_top(self)def test_pop(self)def test_pop_exception(self)def test_as_string(self, s)C. Run your file to run the unit tests. All tests should pass for full credit. Recursion REQUIRED where noted.
DSAP Chapter 4 & 7 (to a lesser extent)
Your submission your source code file named according to syllabus.
# hw 6 solution.py
import unittest
class EmptyStack(Exception):
"""Custom Exception"""
def __init__(self, value):
self.value = value
def __str__(self):
return repr(self.value)
class LinkedStack:
"""LIFO Stack implementation using a singly linked list for storage."""
#-------------------------- nested _Node class --------------------------
class _Node:
"""Lightweight, nonpublic class for storing a singly linked node."""
__slots__ = '_element', '_next' # streamline memory usage
def __init__(self, element, next): # initialize node's fields
self._element = element # reference to user's element
self._next = next # reference to next node
#------------------------------- stack methods -------------------------------
def __init__(self):
"""Create an empty stack."""
self._head = None # reference to the head node
self._size = 0 # number of stack elements
def __len__(self):
"""Return the number of elements in the stack."""
return self._size
def is_empty(self):
"""Return True if the stack is empty."""
return self._size == 0
def push(self, e):
"""Add element e to the top of the stack."""
self._head = self._Node(e, self._head) # create and link a new node
self._size += 1
def push_seq(self, seq):
"""Iteratively push each element in seq to stack."""
for i in seq:
self.push(i)
def top(self):
"""Return (but do not remove) the element at the top of the stack.
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise EmptyStack('Stack is empty')
return self._head._element # top of stack is at head of list
def pop(self):
"""Remove and return the element from the top of the stack (i.e., LIFO).
Raise Empty exception if the stack is empty.
"""
if self.is_empty():
raise EmptyStack('Stack is empty')
answer = self._head._element
self._head = self._head._next # bypass the former top node
self._size -= 1
return answer
def as_string(self, s): # s is NODE
if not s: # base case is null node
return ''
return str(s._element) + ' ' + self.as_string(s._next) # tail recursion...
class TestLinkedStackMethods(unittest.TestCase):
"""Unit tests for LinkedStack"""
def test_init(self):
stack = LinkedStack()
self.assertEqual(len(stack), 0)
def test_is_empty(self):
stack = LinkedStack()
self.assertEqual(len(stack), 0)
def test_push(self):
stack = LinkedStack()
stack.push(9)
stack.push(4)
self.assertEqual(len(stack), 2)
def test_push_seq(self):
stack = LinkedStack()
stack.push_seq([9, 4, 24, 10])
self.assertEqual(len(stack), 4)
def test_top(self):
stack = LinkedStack()
stack.push_seq([9, 4, 24, 10])
self.assertEqual(stack.top(), 10)
def test_top_exception(self):
stack = LinkedStack()
with self.assertRaises(EmptyStack):
stack.top()
def test_pop(self):
stack = LinkedStack()
stack.push_seq([9, 4, 24, 101])
self.assertEqual(stack.pop(), 101)
self.assertEqual(stack.top(), 24)
def test_pop_exception(self):
"""Tests whether pop correctly raises EmptyStack exception."""
stack = LinkedStack()
with self.assertRaises(EmptyStack):
stack.pop()
def test_as_string(self):
"""Tests that as_string correctly lists the contents of the stack."""
stack = LinkedStack()
stack.push_seq([9, 4, 24, 10])
self.assertEqual(stack.as_string(stack._head), '10 24 4 9 ')
"""Run the unit tests on invocation of this file with python interpreter.
> python <name of this file>.py
"""
if __name__ == '__main__':
unittest.main()