This program exercises stacks. # Replace any \"\" comments with you

Hi, There is a big flaw in pop function of arraystack. I went nuts to find that flaw... Basically, the pop function is not removing the element. Here's the correct function of it. Please replace it with correct indentation or else it won't work. 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."""…

# This program exercises stacks. # Replace any \"<your code>\" comments with you

ID: 3786504 • Letter: #

Question

# This program exercises stacks.

# Replace any "<your code>" 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."
# <your code>
print()

# Part 2:
# Remove the top item from stack1, print the removed item, and print stack1:
# <your code>
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."
# <your code>
print()

# Part 4:
# Remove all the items from stack1 until there is only 3 items left in it:
# <your code>
print("After removing all but 3 items from stack1:")
printStack1()

# Part 5:
# Use a single method to empty stack1:
# <your code>
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.
# <your code>
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.
# <your code>
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:
# <your code>
print("The value at the top of stack2:", item)
printStack2()

# Part 10:
# Add the odd single-digit numbers to stack1 with 9 at the top:
# <your code>
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.
# <your code>
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.
# <your code>
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

<variable> = array(<capacity>, <optional fill value>)

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

# 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()

"""

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

Explanation / Answer

Hi,

There is a big flaw in pop function of arraystack. I went nuts to find that flaw... Basically, the pop function is not removing the element. Here's the correct function of it. Please replace it with correct indentation or else it won't work.

return oldItem

Here's the whole code. Thanks for the amazing assignment... Loved it...

#!/usr/bin/env python
# coding=utf-8

from arraystack import ArrayStack
from linkedstack import LinkedStack

def printStack1():
print("stack1:", stack1._items.__str__())
print()

def printStack2():
print("stack2:", stack2._items.__str__())
print()

def print2Stacks():
print("stack1:", stack1._items.__str__())
print("stack2:", stack2._items.__str__())
print()

def print3Stacks():
print("stack1:", stack1._items.__str__())
print("stack2:", stack2._items.__str__())
print("stack3:", stack3.__str__())
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 2:
# Remove the top item from stack1, print the removed item, and print stack1:

print "Popped item is {0}".format(stack1.pop())
print("After removing the top item from stack1:")
printStack1()

print()

# Part 4:
# Remove all the items from stack1 until there is only 3 items left in it:
for i in range(0, len(stack1)-3):
stack1.pop()

print("After removing all but 3 items from stack1:")
printStack1()

# Part 5:
# Use a single method to empty stack1:
stack1.clear()
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.
# <your code>
for i in range(0, len(stack2)):
try:
x = stack2.pop()
if x and x % 2 == 0:
stack1.push(x)
except KeyError:
pass

print("After moving evens to stack1 (in reverse order):")
print2Stacks()

for i in range(0, len(stack1)):
try:
x = stack1.pop()
stack2.push(x)
except KeyError:
pass

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:
# <your code>
# 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.
if stack1.isEmpty() or stack2.isEmpty():
print "it is empty"
if not stack1.isEmpty() and not stack2.isEmpty():
print "it is not empty"

print()

# Part 10:
# Add the odd single-digit numbers to stack1 with 9 at the top:
for i in range(9, 0, -2):
stack1.push(i)

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.
i = 0
j = 0
while(i < len(stack1) and j < len(stack2)):
stack3.push(stack2.pop())
stack3.push(stack1.pop())

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.
for i in range(0, len(stack3)):
ele = stack3.pop()
stack1.push(ele)
stack2.push(ele)
print("After moving each item from stack3 to stacks 1 and 2:")
print3Stacks()

Navigate

# This program exercises bags: # Replace any \"\" comments with your own code st

# This program exercises stacks. # Replace any \"yourcode\" comments with your o

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

# This program exercises stacks. # Replace any \"<your code>\" comments with you

Question

Explanation / Answer

Related Questions

Navigate