Impression of Week 5

     This week, we learned more on recursion.
     It was snowing heavily on Monday and the TTC was delayed again. But I luckily made it to 148's lecture ;)
     On Monday, we did the quick sort using recursion first. The basic process is picking the first element and sort those greater than or equal to it to the right and those less than it to the left and repeat this process until all the elements are in the right position.
    Here's the code:

def quick_sort(L):
    ''' (list) -> list

    Return a list containing the same elements as L in ascending order.

    >>> quick_sort([])
    []
    >>> quick_sort([5])
    [5]
    >>> import random
    >>> L = [1, 2, 3, 4, 5, 6, 7]
    >>> random.shuffle(L)
    >>> quick_sort(L)
    [1, 2, 3, 4, 5, 6, 7]
    '''
    if len(L) < 2: # there's nothing to sort
        return L
    else:
        return (quick_sort([x for x in L if x < L[0]]) + 
                [L[0]] + 
                quick_sort([x for x in L[1:] if x >= L[0]]))

The recursion here is for those lists who have more than 1 element that is to say can be sorted. But in this code, we are not checking the order of the sequence but we keep sort things and dividing list up until the length of the list remains is 1.
      After that, we did the parenthesizetion using the ADT we coded before. Noticing that the computer can only see one character at a time, we are using Stack to store the parenthesis we see so far and check to see if they are in the correct position.
     Here's the code:

def balanced_delimiters(s):
    ''' (str) -> bool

    Return whether the brackets in string s are balanced.

    Assume: Only delimiters are brackets
    >>> balanced_delimiters('[({])}')
    False
    >>> balanced_delimiters('[({})]]')
    False
    >>> balanced_delimiters('[[]')
    False
    >>> balanced_delimiters('[(){}]')
    True
    '''
    st = stack.Stack()
    for c in s:
        if not c in '(){}[]':
            pass
        elif c in '({[':
            st.push(c)
        # now must have c in ')}]'
        elif not st.is_empty():
            c2 = st.pop()
            if ((c == ')' and not c2 == '(') or
                (c == '}' and not c2 == '{') or
                (c == ']' and not c2 == '[')):
                return False
        else: # prematurely empty stack!
            return False
    return st.is_empty() # better be empty at the end

Basically we are checking the type and the order at the same time, so using a stack which is a first in last out thing is reasonable as the first half of parenthesis should appear last in the application.

     Wednesday was the term test, so no lectures.