Implementing a Stack ADT using a linked solution. The implementations are linked Nodes. class Node: def __init__(self, data, node=None): # Initialize this node, insert data, and set the next node if any self.data = data self.chain = node class SubSetStack: def __init__(self, data=None): # Initialize this stack, and store data if it exists def push(self, data): # Add data to the beginning of the stack def pop(self): # Remove the element at the beginning of the stack. # Return the data in the element at the beginning of the stack, or None if the stack is empty def top(self): # Return the data in the element at the beginning but does not remove it. # Return None if stack is empty. def __len__(self): # Return the number of elements in the stack def subset_sum(target, sub_list): # Returns True if Target can be formed from sub_list repeated # some arbitrary number of times. In the above function a Node class is given. A class called SubSetStack is given. Have to implement the methods push(), pop(), top() and the over loaded __len__() method. Push should add an item to the stack. Pop should remove an item from the stack. Top should return the data of the top item of the stack but does not remove the item. The function ___len__() should return the number of items in the stack. All methods MUST be O(1). Have to create a combination out of 'list of sub_list' to check if the combination equals to given 'target' i.e. determine if there is a subset of the given set with sum equal to given target, the 'sub_set' function needs to be implemented using an iterative method that utilize a Stack. For example:- a) if target=8, sub_list=[2,4], then 2+2+2+2 = 8 is True. b) If target = 4, sub_list = [], i.e. empty list then the result is True. c) If target = 8, sub_list = [3,6], then are no combination which will equal it to '8' then the result is False. d) If target=7, sub_list = [2,3,1], then combination can be 2+2+3, which is True because the combination sum equals to target '7'.
Implementing a Stack ADT using a linked solution. The implementations are linked Nodes.
class Node:
def __init__(self, data, node=None):
# Initialize this node, insert data, and set the next node if any
self.data = data
self.chain = node
class SubSetStack:
def __init__(self, data=None):
# Initialize this stack, and store data if it exists
def push(self, data):
# Add data to the beginning of the stack
def pop(self):
# Remove the element at the beginning of the stack.
# Return the data in the element at the beginning of the stack, or None if the stack is empty
def top(self):
# Return the data in the element at the beginning but does not remove it.
# Return None if stack is empty.
def __len__(self):
# Return the number of elements in the stack
def subset_sum(target, sub_list):
# Returns True if Target can be formed from sub_list repeated
# some arbitrary number of times.
In the above function a Node class is given. A class called SubSetStack is given. Have to implement the methods push(), pop(), top() and the over loaded __len__() method. Push should add an item to the stack. Pop should remove an item from the stack. Top should return the data of the top item of the stack but does not remove the item. The function ___len__() should return the number of items in the stack. All methods MUST be O(1).
Have to create a combination out of 'list of sub_list' to check if the combination equals to given 'target' i.e. determine if there is a subset of the given set with sum equal to given target, the 'sub_set' function needs to be implemented using an iterative method that utilize a Stack.
For example:-
a) if target=8, sub_list=[2,4], then 2+2+2+2 = 8 is True.
b) If target = 4, sub_list = [], i.e. empty list then the result is True.
c) If target = 8, sub_list = [3,6], then are no combination which will equal it to '8' then the result is False. d) If target=7, sub_list = [2,3,1], then combination can be 2+2+3, which is True because the combination sum equals to target '7'.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
