In
the second week class, we talking about ADTs, Stacks and little bit about
recursive. The ADTs stand for abstract data types, specifies a set of operations
(or methods ) and the semantics of the operation, but it does not specify the
implementation of the operations. The Stacks is a common ADT. The stack is a
collection, which contains multiple elements. And we did some example about
calculate the sum of the all elements in a nested list by use recursion.
#create the new class called Stack(ADT)
class Stack:
#Inittialize a new empty stack.
def __init__(self: 'Stack' ) -> None:
self.items = []
#Add a new item in top of stack.
def push(self: 'Stack', item: object) -> None:
self.items.append(item)
#self.items.insert(0,item)
#remove and return the last item in the stack.FIFO
def pop(self: 'Stack') -> None:
return self.items.pop()
#campare stack to a empty to check the stack is empty or not.
#which is boolean.
def is_empty(self: 'Stack') -> bool:
return (self.items == [])
#return (len(self.items) == 0)
#empty the stack and return a empty stack.
def empty_list(self: 'Stack') -> "empty list":
if ((self.items==[])==True):
return self.items
else:
self.items = []
return self.items
#conver the stack to String, which we can use print method
def __str__(self: 'Stack') -> 'String':
return ("{}".format(self.items))
#Stack is generic data structure,which mean we can add any type of item to it.
'''
x=Stack()
x.push(1)
x.push(2)
print(x)
print(x.pop())
print(x)
print(x.is_empty())
print(x)
x.empty_list()
print(x)
'''
#infix and postfix
#infix: 1 + 2
#postfix: 1 2 +
'''
print("mother fuck".split(" "))
import re
print(re.split("([^0-90])", "123+456*/"))
'''
def eval_postfix(expr: object) -> int:
token_list = re.split("([^0-9])", expr)
stack = Stack()
for token in token_list:
if token == "" or token == " ":
continue
elif token == "+":
sum = stack.pop() + stack.pop()
stack.push(sum)
elif token == "*":
product = stack.pop() * stack.pop()
stack.push(product)
elif token == "-":
defrent = stack.pop() - stack.pop()
stack.push(defrent)
elif token == "/":
devide = stack.pop() - stack.pop()
stack.push(devide)
else:
stack.push(int(token))
return stack.pop()
'''
test_postfix="10 10 + 2 * 10 - 5 / "
print(eval_postfix(test_postfix))
'''
# account time for push and pop 100 object in the stock
if __name__ == '__main__':
import time
s = Stack()
items = range(1)
#start account
start = time.time()
for i in items:
s.push(i)
# print(s)
for i in items:
x=s.pop()
# print(x)
#end account
end = time.time()
#print (end-start)
#Test
import unittest
#My test case
class StackEmptyTestCase(unittest.TestCase):
#test a empty stack
def setUp(self):
#set up a empty stack
self.stack = Stack()
def tearDown(self):
#clean up
self.stack = None
def testIsEmpty(self):
assert self.stack.is_empty(),\
'is_empty returned False on an empty Stack'
def testPush(self):
self.stack.push("foo")
assert self.stack.pop() == "foo",\
'Wrong item on top od the Stack! Expected "foo" here.'
class StackAllTestCase(unittest.TestCase):
#test non-empty stack
def setUp(self):
#set up a non-empty stack
self.stack = Stack()
def tearDown(self):
self.stack = None
def testAll(self):
for item in range(20):
self.stack.push(item)
assert not self.stack.is_empty(),\
' return ture for non- empty stack'
expect = 19
while not self.stack.is_empty():
assert self.stack.pop() == expect,\
('Something wrong on top of the Stack! Expected ' +
str(expect) + '.')
expect = expect - 1
def empty_suite():
return unittest.TestLoader().loadTestsFromTestCase(StackEmptyTestCase)
def all_suite():
return unittest.TestLoader().loadTestsFromTestCase(StackAllTestCase)
runner = unittest.TextTestRunner()
runner.run(empty_suite())
runner.run(all_suite())
'''
#prof test case
import unittest
class StackEmptyTestCase(unittest.TestCase):
"""Test behaviour of an empty Stack."""
def setUp(self):
"""Set up an empty stack."""
self.stack = Stack()
def tearDown(self):
"""Clean up."""
self.stack = None
def testIsEmpty(self):
"""Test is_empty() on empty Stack."""
assert self.stack.is_empty(),\
'is_empty returned False on an empty Stack!'
def testPush(self):
"""Test push to empty Stack."""
self.stack.push("foo")
assert self.stack.pop() == "foo",\
'Wrong item on top of the Stack! Expected "foo" here.'
class StackAllTestCase(unittest.TestCase):
"""Comprehensive tests of (non-empty) Stack."""
def setUp(self):
"""Set up an empty stack."""
self.stack = Stack()
def tearDown(self):
"""Clean up."""
self.stack = None
def testAll(self):
"""Test pushing and popping multiple elements."""
for item in range(20):
self.stack.push(item)
assert not self.stack.is_empty(),\
'is_empty() returned True on a non-empty Stack!'
expect = 19
while not self.stack.is_empty():
assert self.stack.pop() == expect,\
('Something wrong on top of the Stack! Expected ' +
str(expect) + '.')
expect = expect - 1
def empty_suite():
"""Return a test suite for an empty Stack."""
return unittest.TestLoader().loadTestsFromTestCase(StackEmptyTestCase)
def all_suite():
"""Return a comprehensive test suite for a non-empty Stack."""
return unittest.TestLoader().loadTestsFromTestCase(StackAllTestCase)
# go!
runner = unittest.TextTestRunner()
runner.run(empty_suite())
runner.run(all_suite())
'''
# recursion
def sum_list(L: list) -> float:
return sum([sum_list(x) if isinstance(x,list) else x for x in L])
print(sum_list([1,2,3,[2,3,[3,4,5,[6,[7]]]]]))
class s2(Stack):
pass
