Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

Instructions Adding, removing, and moving items ---------------------------------- Wherever you are instructed to add an item to a stack, you are to add it to the

Instructions 
 
Adding, removing, and moving items ---------------------------------- Wherever you are instructed to add an item to a stack, you are to add it to the top of the stack. Wherever you are instructed to remove an item from a stack, you are to remove it from the top of the stack. Wherever you are instructed to move an item from one stack to another, you are to remove it from the one stack and then add it to the other stack. Part 1 ------ Many of the output statements are already provided in the starter file. Some parts, such as this one, require you to provide some of the output statements. Make sure your output matches that shown in "Programming Activity 4 - Expected Output" document. Part 4 ------ You can use a while loop with a condition based on the stack's length. Part 6 ------ You can use a while loop with a controller of the form: while (True): Within the loop, you will need a "try" and corresponding "except" block. The "except" block needs to catch a KeyError exception. The "except" block should simply "break" out of the loop. The general form then will be: while (True): try: #  except KeyError: break This is a useful pattern that you can reuse for some of the other parts. Part 10 ------- You can use a "for" loop with a controller of the form: for i in range(start, stop, step): where you supply the proper values for start, stop, and step. Part 11 ------- Alternating interleaving means to follow a pattern of the form: Remove an item from stack2 and put it on stack3. Remove an item from stack1 and put it on stack3. repeating this in a loop.  
~~~~~~~~~~~~~~~~
# This program exercises stacks.
 
# Replace any "" comments with your own code statement(s)
# to accomplish the specified task.
# Do not change any other code.
 
# The following files must be in the same folder:
# abstractcollection.py
# abstractstack.py
# arraystack.py
# arrays.py
# linkedstack.py
# node.py
 
from arraystack import ArrayStack
from linkedstack import LinkedStack
 
def printStack1():
 print("stack1:", stack1)
 print()
 
def printStack2():
 print("stack2:", stack2)
 print()
 
def print2Stacks():
 print("stack1:", stack1)
 print("stack2:", stack2)
 print()
 
def print3Stacks():
 print("stack1:", stack1)
 print("stack2:", stack2)
 print("stack3:", stack3)
 print()
 
# Here are 2 starting stacks: 
stack1 = ArrayStack([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
stack2 = ArrayStack([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
 
# Print the stacks:
print2Stacks()
 
# Part 1:
# Use the == comparison operator to determine if the 2 stacks are equal.
# If they are equal print "The stacks are equal.".
# If they are not equal print "The stacks are not equal."
# 
print()
 
# Part 2:
# Remove the top item from stack1, print the removed item, and print stack1:
# 
print("After removing the top item from stack1:")
printStack1()
 
# Part 3:
# Use the == comparison operator to determine if the 2 stacks are equal.
# If they are equal print "The stacks are equal.".
# If they are not equal print "The stacks are not equal."
# 
print()
 
# Part 4:
# Remove all the items from stack1 until there is only 3 items left in it:
# 
print("After removing all but 3 items from stack1:")
printStack1()
 
# Part 5:
# Use a single method to empty stack1:
# 
print("After emptying stack1:")
printStack1()
 
# Part 6:
# Use pop() and push() to move all even valued items from stack2 to stack1.
# This will leave stack2 empty.
# This will leave stack1 with only even valued items.
# stack1 will be in the reverse order from the original stack2 order.
# When popping, use a try/except block to catch and ignore the KeyError exception.
# 
print("After moving evens to stack1 (in reverse order):")
print2Stacks()
 
# Part 7:
# Use pop() and push() to move all the stack1 items back to stack2.
# This will leave stack1 empty.
# This will leave stack2 with the even valued items back in their original order.
# You have effectively removed all the odd valued items from stack2.
# You will again need a try/except block.
# 
print("After moving evens back to stack2 (in original order):")
print2Stacks()
 
# Part 8:
# Get and print the value at the top of stack2 without removing it:
# 
print("The value at the top of stack2:", item)
printStack2()
 
# Part 9:
# Use isEmpty() to check whether stack1 and stack2 are empty.
# If either is empty, print a message saying it is empty.
# If either is not empty, print a message saying it is not empty.
# 
print()
 
# Part 10:
# Add the odd single-digit numbers to stack1 with 9 at the top:
# 
print("After adding the odd single-digit numbers to stack1:")
print2Stacks()
 
# Part 11:
# Create a new empty stack of type LinkedStack called stack3:
stack3 = LinkedStack()
# Alternate popping items from stack2 and stack1, interleaving them onto stack3.
# Both stacks 1 and 2 will be left empty.
# As usual, handle or avoid exceptions.
# 
print("After moving items from stack1 and stack2 (interleaved) to stack3:")
print3Stacks()
 
# Part 12:
# Move each item from stack3 to both stack1 and stack2.
# Stacks 1 and 2 will be left in their original starting order.
# stack3 will be left empty.
# 
print("After moving each item from stack3 to stacks 1 and 2:")
print3Stacks()
~~~~~~~~~~~~~~~~~
""" File: abstractcollection.py Copyright 2015 by Ken Lambert """ class AbstractCollection(object): """An abstract collection implementation.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._size = 0 self._modCount = 0 if sourceCollection: for item in sourceCollection: self.add(item) # Accessor methods def isEmpty(self): """Returns True if len(self) == 0, or False otherwise.""" return len(self) == 0 def __len__(self): """Returns the number of items in self.""" return self._size def __str__(self): """Returns the string representation of self, using [] as delimiters.""" return "[" + ", ".join(map(str, self)) + "]" def __eq__(self, other): """Returns True if self equals other, or False otherwise. Compares pairs of items in the two sequences generated by the iterators on self and other.""" if self is other: return True if type(self) != type(other) or \ len(self) != len(other): return False otherIter = iter(other) for item in self: if item != next(otherIter): return False return True def __add__(self, other): """Returns a new collection containing the contents of self and other.""" result = type(self)(self) for item in other: result.add(item) return result def count(self, item): """Returns the number of instance of item in self.""" counter = 0 for nextItem in self: if item == nextItem: counter += 1 return counter # These methods track and update the modCount, which is used to # prevent mutations within the context of an iterator (for loop) def getModCount(self): """Returns the number of modifications to the collection.""" return self._modCount def incModCount(self): """Increments the number of modifications to the collection.""" self._modCount += 1 
~~~~~~~~~~
""" File: abstractstack.py Copyright 2015 by Ken Lambert """ from abstractcollection import AbstractCollection class AbstractStack(AbstractCollection): """Represents an abstract stack.""" def __init__(self, sourceCollection): """Initializes the stack at this level.""" AbstractCollection.__init__(self, sourceCollection) def add(self, item): """For compatibility with other collections.""" self.push(item) 
~~~~~~~~~~~
""" File: arraystack.py Copyright 2015 by Ken Lambert """ from arrays import Array from abstractstack import AbstractStack class ArrayStack(AbstractStack): """An array-based stack implementation.""" # Class variable DEFAULT_CAPACITY = 10 # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._items = Array(ArrayStack.DEFAULT_CAPACITY) AbstractStack.__init__(self, sourceCollection) # Accessor methods def __iter__(self): """Supports iteration over a view of self. Visits items from bottom to top of stack.""" modCount = self.getModCount() cursor = 0 while cursor < len(self): yield self._items[cursor] if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor += 1 def peek(self): """Returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty.""" if self.isEmpty(): raise KeyError("The stack is empty") return self._items[len(self) - 1] # Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._modCount = 0 self._items = Array(ArrayStack.DEFAULT_CAPACITY) def push(self, item): """Inserts item at top of the stack.""" # Resize array here if necessary if len(self) == len(self._items): tempArray = Array(len(self) * 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray self._items[len(self)] = item self._size += 1 self.incModCount() def pop(self): """Removes and returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty. Postcondition: the top item is removed from the stack.""" if self.isEmpty(): raise KeyError("The stack is empty") oldItem = self._items[len(self) - 1] self._size -= 1 self.incModCount() # Resize the array here if necessary if len(self) <= .25 * len(self._items) and \ ArrayStack.DEFAULT_CAPACITY <= len(self._items) // 2: tempArray = Array(len(self._items) // 2) for i in range(len(self)): tempArray[i] = self._items[i] self._items = tempArray return oldItem ~~~~~~~~~~~
""" File: arrays.py Copyright 2015 by Ken Lambert An Array is a restricted list whose clients can use only [], len, iter, and str. To instantiate, use  = array(, ) The fill value is None by default. """ class Array(object): """Represents an array.""" def __init__(self, capacity, fillValue = None): """Capacity is the static size of the array. fillValue is placed at each position.""" self._items = list() for count in range(capacity): self._items.append(fillValue) def __len__(self): """-> The capacity of the array.""" return len(self._items) def __str__(self): """-> The string representation of the array.""" return str(self._items) def __iter__(self): """Supports iteration over a view of an array.""" return iter(self._items) def __getitem__(self, index): """Subscript operator for access at index.""" return self._items[index] def __setitem__(self, index, newItem): """Subscript operator for replacement at index.""" self._items[index] = newItem 
~~~~~~~~~~~~~~~
""" File: linkedstack.py Copyright 2015 by Ken Lambert """ from abstractstack import AbstractStack from node import Node class LinkedStack(AbstractStack): """Represents a link-based stack.""" # Constructor def __init__(self, sourceCollection = None): """Sets the initial state of self, which includes the contents of sourceCollection, if it's present.""" self._head = None AbstractStack.__init__(self, sourceCollection) # Accessor methods def __iter__(self): """Supports iteration over a view of self. Visits items from bottom to top of stack.""" lyst = list() probe = self._head while probe != None: lyst.append(probe.data) probe = probe.next lyst.reverse() modCount = self.getModCount() cursor = 0 while cursor < len(lyst): yield lyst[cursor] if modCount != self.getModCount(): raise AttributeError("Illegal modification of backing store") cursor += 1 def peek(self): """Returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty.""" if self.isEmpty(): raise KeyError("The stack is empty") return self._head.data # Mutator methods def clear(self): """Makes self become empty.""" self._size = 0 self._head = None self._modCount = 0 def push(self, item): """Inserts item at top of the stack.""" self._head = Node(item, self._head) self._size += 1 self.incModCount() def pop(self): """Removes and returns the item at the top of the stack. Precondition: the stack is not empty. Raises: KeyError if stack is empty. Postcondition: the top item is removed from the stack.""" if self.isEmpty(): raise KeyError("The stack is empty") self._size -= 1 self.incModCount() data = self._head.data self._head = self._head.next return data 
~~~~~~~~~~~~~~
""" File: node.py Copyright 2015 by Ken Lambert """ class Node(object): """Represents a singly linked node.""" def __init__(self, data, next = None): self.data = data self.next = next class TwoWayNode(Node): """Represents a doubly linked node.""" def __init__(self, data = None, previous = None, next = None): Node.__init__(self, data, next) self.previous = previous ~~~~~~~~~~~~~~~
 
Output
stack1: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] stack2: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] The stacks are equal. Removed item: 10 After removing the top item from stack1: stack1: [1, 2, 3, 4, 5, 6, 7, 8, 9] The stacks are not equal. After removing all but 3 items from stack1: stack1: [1, 2, 3] After emptying stack1: stack1: [] After moving evens to stack1 (in reverse order): stack1: [10, 8, 6, 4, 2] stack2: [] After moving evens back to stack2 (in original order): stack1: [] stack2: [2, 4, 6, 8, 10] The value at the top of stack2: 10 stack2: [2, 4, 6, 8, 10] stack1 is empty. stack2 is not empty. After adding the odd single-digit numbers to stack1: stack1: [1, 3, 5, 7, 9] stack2: [2, 4, 6, 8, 10] After moving items from stack1 and stack2 (interleaved) to stack3: stack1: [] stack2: [] stack3: [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] After moving each item from stack3 to stacks 1 and 2: stack1: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] stack2: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] stack3: [] 
 

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image_2

Step: 3

blur-text-image_3

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Practical Database Programming With Visual C# .NET

Authors: Ying Bai

1st Edition

0470467274, 978-0470467275

More Books

Students also viewed these Databases questions

Question

2. Compare the sales and service departments at Auto World.

Answered: 1 week ago

Question

Prepare a short profile of Henry words worth Longfellow?

Answered: 1 week ago

Question

What is RAM as far as telecommunication is concerned?

Answered: 1 week ago

Question

Question 1: What is reproductive system? Question 2: What is Semen?

Answered: 1 week ago

Question

Describe the sources of long term financing.

Answered: 1 week ago

Question

What is the Definition for Third Normal Form?

Answered: 1 week ago

Question

Provide two examples of a One-To-Many relationship.

Answered: 1 week ago