Short paragraphs of OOP and Recursion.

        There are several reasons why programming languages such as python enable developers to define new classes. Classes that are custom-built for a particular application will make the application program more intuitive and easier to develop, debug, read, and maintain. The ability to create new classes also enables a new approach to structuring application programs. A class exposes to the computer scientist the methods that can be applied to objects of the class but encapsulate how the data contained in the objects is stored and how the classmethods are implemented. OOP is a software development paradigm that achieves modularity and code portability by organizing application programs around components that are classes and objects.
Recursion is a problem-solving technique that expresses the solution to a problem in terms of solutions to subproblems of the original problem. Recursion can be used to solve problems that might otherwise be quite challenging. The function developed by solving a problem recursively will naturally call themselves, and we refer to them as recursive functions. In some instances, recursive thinking offers insights that lead to solutions that are more efficient than the obvious or original solution. In other instances, it will lead to a solution that is far worse.

Week 7

      In this week class, we learn about linked lists, which is example of attributes that refer to other objects. Linked lists are made up of nodes, where each ode contains a reference to the next node in the list. In addition, each node contains a unit of data called the cargo. A linked list is considered a recursive data structure because it has a recursive definition. And Recursive data structures lend themselves to recursive methods.

class Node:
    def __init__(self, cargo = None, next = None):
        self.cargo = cargo
        self.next  = next

    def __str__(self):
        return str(self.cargo)

    def print_backward(self):
        if self.next is not None:
            tail = self.next
            tail.print_backward()
        print(self.cargo, end=" ")



node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

node1.next = node2
node2.next = node3
#node3.next = node1

#print(node3.next)


def print_list(node):
    while node is not None:
        print(node, end=" ")
        node = node.next
    print()

#print_list(node1)

def print_backward(list):
    if list is None:
        return
    head = list
    tail = list.next
    print_backward(tail)
    print(head, end=" ")
     

#print_backward(node1)

def remove_second(list):
    if list is None:
        return
    else:
        first = list
        second = list.next
        #make first.next point to third node by skip node 2
        first.next = second.next
        #however node 2 still there
        #so second.next still be the node 3
        #unless we give second.next point none
        second.next = None
        return second


'''
print_list(node1)
removed = remove_second(node1)
print_list(removed)
print_list(node1)
'''

class LinkedList:
    def __init__(self):
        self.length = 0
        self.head = None

    def print_backward(self):
        print("[",end = " ")
        if self.head is not None:
            self.head.print_backward()
            print("]", end = " ")

    def print_list(self):
        if self.head is not None:
            print(self.head)

    def add_first(self,cargo):
        node = Node(cargo)
        node.next =  self.head
        self.head = node
        self.length += 1

    def get_length(self):
        return self.length

'''
x = LinkedList()
x.add_first(1)
x.add_first(2)
x.add_first(3)
x.add_first(4)
x.add_first(5)
x.add_first(6)
x.add_first(7)
x.print_backward()
print(x.get_length())
x.print_list()
'''


class LListNode:
    def __init__(self, value = None, nxt = None):
        self.value, self.nxt = value, nxt
     
    def __repr__(self):
        return 'LListNode(' + str(self.value) + ',' + str(self.nxt) + ')'

#x=LListNode(5556, 2)
#print(x)



class TreeNode:
    #initial value of value here is an object that can be define as anything,
    #and give the list initial type of list and value none, so when children
    #is none them return empty list
    #example can be seem @1
    def __init__(self: 'TreeNode',
                 value: object =None, children: list =None):
        self.value = value
        if not children:
        #=if children == None:
            self.children = []
        else:
            self.children = children[:]

    def __repr__(self: 'TreeNode'):
        return ('TreeNode(' + str(self.value) + ',' +
                repr(self.children) + ')' )

'''
#@1
test_list1 = [1,2,3,4,5]
#x=LListNode(5556, 2)
x='xxxx'
y=TreeNode(x,test_list1)
#y = TreeNode(x)
print(y)
'''


class Tree:
    def __init__(self, root = None):
     
        self.root = root
     
    def arity(self: 'Tree') -> int:
        pass
     

class b(object):
    def __init__(self, item, left=None, right=None):
        self.item = item
        self.left = left
        self.right = right
        self.depth = 0


    def __str__(self):
        if self.right:
            str_right = "\t" + str(self.right).replace("\n","\n\t") + "\n"
        else:
            str_right = ""
        if isinstance(self.item, str):
            str_item = repr(self.item)
        else:
            str_item = str (self.item)
        if self.left:
            str_left = "\n\t" + str(self.left).replace("\n","\n\t")
        else:
            str_left = ""
        return str_right + str_item + str_left


    def set_depth(self,depth):
        if self.left == None and self.right == None:
            self.depth = depth
        if self.left:
            self.depth = depth
            self.left.set_depth(self.depth+1)
        if self.right:
            self.depth = depth
            self.right.set_depth(self.depth+1)
         
    def leaves_and_internals(self):
        i = [[],[]]
        def insidelai(node):
            if node.left == None and node.right == None:
                i[1].append(node.item)
            else:
                if node.left is None:
                    i[0].append(node.item)
                    insidelai(node.right)
                elif node.right is None:
                    i[0].append(node.item)
                    insidelai(node.left)
                else:
                    i[0].append(node.item)
                    insidelai(node.left)
                    insidelai(node.right)
            return i
        return insidelai(self)
 
'''          
    def leaves_and_intenals(self)：
        leaves = []
        internals = []
        if (not self.left) and (not self.right):          
            leaves.append(self.item)
        else:
            internals.append(self.item)
            left = self.left.leaves_and_internals()
            right = self.right.leaves_and_internals()
            leaves = left[0] + right[0]
            internals = internals + left[1] + right[1]
        return (leaves, internals)
'''

#x=b(1,b(2,None,b(4)),b(5,b(6),b(7)))
#print(x.leaves_and_internals())

def cd(node,depth):
    temp = depth
    if node.left == None and node.right == None:
        return temp
    else:
        #if not node.left == None:
        temp = temp+1
        return cd(node.left,temp)
'''
x.set_depth(1)
print(x)
#print(cd(x.left,1),cd(x.left.left,1))
print(x.right.depth)
#y=BTNode(2,x,x)
#print(y)
#z=BTNode(2,y,y)
#print(z)
'''

Week 6

      University closed and test....

Week 5

       In this week class, we learn about treelist with preoder, postorder and inorder. We learn about how to create a binary tree. The tree just like a combination of nodes, has leaf: node with no children, internal node: node with one or more children, subtree: tree formed by any tree node together with its descendants and the edges leading to them. And there is a unique path from root to each node. And again, we learn how to do it by using recursion.
def preorder(tl: 'TreeLIst') -> list:
    if tl == None:
        return []
    else:
        return [tl[0]] + preorder(tl[1]) + preorder(tl[2])
 
#print(preorder([5, [4, [2, None, [3, None, None]],[6, [7, None, None], None]], [3, [2, None, None], [1, None, None]]]))
#print(preorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))

'''
                       5
                 4           3
              2    6       2   1
            N   3        N  N N N
               N N
                       5
                 4           3
               2   N       9   1
              8 3
               N  6
                 7  N

postorder [6 3 2 4 2 1 3 5]
inorder [2 3 6 4 5 2 3 1]

[10, 6, 8, 12, 11, 15]
                         10
                      6     11
                    8  12     15
[8, 6, 12, 10, 11, 15]
                         
'''
'''
def inorder(tl: 'TreeList') -> list:

    return ((inorder(tl[1]) if tl[1] else []) + [tl[0]] +
            (inorder(tl[2]) if tl[2] else []))
'''
def inorder(tl: 'TreeList') -> list:
    """
    Return a list of values of tl inorder

    >>> inorder([5, [4, None, None], [3, [2, None, None], [1, None, None]]])
    [4, 5, 2, 3, 1]
    """

    return ((inorder(tl[1]) if tl[1] else []) +
            [tl[0]] +
            (inorder(tl[2]) if tl[2] else []))


print(inorder([5, [4, [2, [8, None, None], [3, None, [6, [7, None, None], None]]], None], [3, [9, None, None],
                                                          [1, None, None]]]))


def postorder(tl:list):
    return ((postorder(tl[1]) if tl[1] else []) + (postorder(tl[2]) if tl[2] else []) + [tl[0]])

'''
print(postorder([5, [4, [2, None, [3, None, [6, None, None]]], None], [3, [2, None, None],
                                                          [1, None, None]]]))

print(inorder([10, [6, [8, None, None], None], [12, [11, None, None], [15, None, None]]]))
print(preorder([10, [8, [6, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(inorder([10, [6, [8, None, None], [12, None, None]], [11, None, [15, None, None]]]))
print(preorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(inorder([10, [6, None, None], [8, None, [12, [11, None, None], [15, None, None]]]]))
print(preorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
print(inorder([10,[6,[8,None,None],[12,None,None]],[11,None,[15,None,None]]]))
    #10,6,8,12,11,15
    '''

Week4

         In this week class, we learn about recursion and testing function that mutate values. A recursive function is a function that calls itself. We also introduce recursive thinking as an approach to problem solving (Tower of Hanoi). For testing function that mutate values, we learn about unittest, basically we do test by compare the output of the function with the expected output by using some bulif-in function like ‘asserequal’.

def r_sum(l:list) -> int:
    if l == []:
        return 0
    else:
        temp = 0
        for i in l:
            if isinstance(i,list):
                temp = temp + r_sum(i)
            else:
                temp = temp + i
        return temp



#print(r_sum([1,2,[2]]))
#print(sum([1,2,3]))

def remove_shared(l1, l2):
    for v in l2:
        if v in l1:
            l1.remove(v)


l1=[1,2,3,4]
l2=[3,4,5,6]
remove_shared(l1,l2)
print(l1,l2)

import unittest

class TestRemoveShared(unittest.TestCase):
    def test_genereal_case(self):
        list_1 = [1, 2, 3, 4, 5, 6]
        list_2 = [2, 4, 6, 7]
        list_1_expected = [1, 3, 5]
        list_2_expected = [2, 4, 6, 7]

        remove_shared(list_1,list_2)

        self.assertEqual(list_1, list_1_expected)
        self.assertEqual(list_2, list_2_expected)

if __name__ == '__main__':
    unittest.main(exit=False)

Week 3 2013

In this week class, we learn about inheritance and exception. Inheritance is the ability to define a new class that is a modified version of an existing class. The new class inherits all of the methods of the existing lass and if we add the new method in child class will not affect the parent class. We also learn about exception, Whenever a runtime error occurs, it creates an exception object. The program stops running at this point and Python prints out the trace back, which ends with a message describing the exception that occurred.

import time
from week2test import Stack
def get_age():
    age = int(input("please enter your age:"))
    if age < 0:
        my_error = ValueError("{0} is not a valid age".format(age))
        raise my_error
    return age

'''
for i in range (1,101):
    print (i)
'''

def error_try():
    start = time.time()
 
    results_list = []
    errors_list = []

    for i in range(-10,10):
        try:
            val = 100/i
            print(val)
        except ZeroDivisionError as Err:
            errors_list.append('Expected Error :' + str(Err))
            print('Error on number :' + str(i))
        except Exception as Err:
            errors_list.append('Unexpected Error :' + str(Err))
            print('Error on number :' + str(i))
        else:
            results_list.append(val)

    print(results_list)
    print(errors_list)

    end = time.time()

    print (end-start)
         
#error_try()

class IntStack(Stack):
    '''
    a sub class of Stack only accept integer
    '''

    def push(self: 'IntStack', n: int) -> None:
        if isinstance(n, int):
            Stack.push(self,n)
        else:
            raise PushNonIntegerException('not a integer')

    def pop(self: 'IntStack') -> int:
        #note for the empty list
        if self.is_empty():
            raise PopEmptyStackException
        else:
            Stack.pop(self)
            #use super class method

class PushNonIntegerException(Exception):
    pass

class PopEmptyStackException(Exception):
    pass

'''
its = IntStack()

try:
 
    its.push(1)
    print(its)
    its.push(2)
    print(its)
    its.push('2')
    print(its)
    its.push('sd')
    its.pop()
    print(its)

except PushNonIntegerException as Err:
    print('Error1')
except PopEmptyStackException as Err:
    print('Error2')
except Exception as Err:
    print('Unknown Error')
'''


class SpecialException(Exception):
    pass

class ExtremeException(SpecialException):
    pass


if __name__ == '__main__':
    try:
        raise ExtremeException('i m an extremeexception')
        raise SpecialException('i m a specialexception')
        #raise Exception('I am an Exception')

    except ExtremeException as ee:
        print(ee)
        print ('caugh as extremeexception')
        raise

    except SpecialException as se:
        print (se)
        print ('caught as specialexcetion')
        raise
    except Exception as ep:
        print(ep)
        print('caugh as excetion')
        raise      

Week 2 2013

         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