1. Stack

stack的準(zhǔn)則：last in first out帮哈。創(chuàng)建stack的class如下：

class StackException(Exception):
    def __init__(self, message):
        self.message = message

class Stack:
    def __init__(self):
        self._data = []
    def peek_at_top(self):
    #因?yàn)閟tack是后入先出的膛檀，所以查看最頂上的元素是最后加入的
        if not self._data:
            raise StackException('Stack is empty')
        return self._data[-1]
    def pop(self):
        if not self._data:
            raise StackException('Stack is empty')
        return self._data.pop()
    def push(self, datum):
        return self._data.append(datum)
    def is_empty(self):
        return self._data == []

1.1 Stack Exercise1

檢查數(shù)學(xué)表達(dá)式的括號是否匹配。因?yàn)槔ㄌ柖际侵饘ζヅ淠锸蹋覂?nèi)側(cè)括號優(yōu)先級高于外側(cè)咖刃，后輸入的括號先匹配，所以適合用stack完成憾筏。

Stack的使用原則非常重要嚎杨，遇到實(shí)際問題時(shí)，判斷問題的解決順訊氧腰，如果符合后進(jìn)先出枫浙，則可以使用Stack。

def check_well_balanced(expression):
    stack = Stack()
    parentheses = {')': '(', ']': '[', '}': '{'}
    #將需要匹配的括號創(chuàng)建一個(gè)key-value字典容贝，方便判斷
    for e in expression:
        if e in '([{':
            stack.push(e)
        #所有遇見的左括號都壓入棧中
        elif e in parentheses:
            try:
                if stack.pop() != parentheses[e]:
                    raise StackException('')
                #無論是否匹配自脯，stack.pop()都已經(jīng)彈出了棧中最外面的括號，不匹配自動(dòng)報(bào)錯(cuò)斤富，匹配則繼續(xù)
            except StackException as e:
                return False
                #如果不匹配膏潮，則返回False，并不拋出Exception的message
    return stack.is_empty()
    #最后還要判斷棧是否為空满力，如果不為空結(jié)果依然是False

1.2 Stack Exercise2

在進(jìn)行數(shù)學(xué)表達(dá)式運(yùn)算時(shí)焕参，括號的處理對計(jì)算機(jī)不友好轻纪，所以創(chuàng)建了一種postfix operation的方式來讓計(jì)算機(jī)清楚要進(jìn)行的運(yùn)算。例如：
(2 + 3) * 5叠纷，寫成postfix operation是2 3 + 5 *刻帚；2 * (3 + 5)，寫成postfix operation是2 3 5 + *
因?yàn)槭呛笾眠\(yùn)算涩嚣，內(nèi)側(cè)括號優(yōu)先級高崇众，和Exercise1的分析一樣，依然適合stack的應(yīng)用航厚。

def evaluate_postfix_expression(expression):
    stack = Stack()
    operators = {'+': lambda x, y: x + y,
                         '-': lambda x, y: y - x,
                         '*': lambda x, y: x * y,
                         '/': lambda x, y: y // x}
    #創(chuàng)建operator的方法顷歌，key對應(yīng)的value是一個(gè)function，因?yàn)闂Ｊ呛筮M(jìn)先出幔睬，所以要注意減法除法的順序眯漩，同時(shí)除法要注意使用//，不然可能會(huì)把int轉(zhuǎn)變?yōu)閒loat麻顶。
    in_number = False
    #因?yàn)閑xpression是逐個(gè)讀取的赦抖，所以數(shù)字不能完整轉(zhuǎn)譯成需要的值，比如234辅肾，先讀入的是2队萤，然后是3，所以要判斷當(dāng)前數(shù)字是否在一個(gè)數(shù)字中宛瞄，default是不在
    for e in expression:
        if e.isdigit():
            if not in_number:
                stack.push(int(e))
                #因?yàn)楹罄m(xù)要做數(shù)字運(yùn)算浮禾，所以要不輸入的string類型轉(zhuǎn)變?yōu)閕nt
                in_number = True
            else:
                stack.push(stack.pop() * 10 + int(e))
                #如果前面已經(jīng)有數(shù)字，則把前面的數(shù)字從棧中推出份汗，10倍后加上當(dāng)前數(shù)字盈电，再壓入棧中。
        else:
            in_number = False
            if e in operators:
                try:
                    arg_1 = stack.pop()
                    arg_2 = stack.pop()
                    stack.push(operators[e](arg_1, arg_2))
                except StackException as e:
                    raise e
    try:
        value = stack.pop()
        if not stack.is_empty():
            raise StackExcpetion('Expression is not correct')
        return value
    except StackException as e:
        raise e

1.3 Stack Exercise3

算法中Depth First Search和stack非常契合杯活，優(yōu)先解決一條路徑上所有可能性匆帚，在當(dāng)下路徑下發(fā)現(xiàn)的新加入的節(jié)點(diǎn)會(huì)優(yōu)先搜索。

Tree

上圖的搜索流程如下旁钧，注意壓棧的順序是從右向左：

No.         1    2     3    4    5    6  ...
Stack       1    2     3    4    5    6 ...
                 4     4    5         11 ...
                 5     5              13 ...
Operation push1 pop1  pop2  pop3 pop4 pop5 ...
                push5 push3           push13
                push4                 push11
                push2                 push6

DFS的代碼實(shí)現(xiàn)基于Stack的方式如下：

T = {1: [2, 4, 5], 2: [3], 5: [6, 11, 13], 6: [7, 8, 10], 8: [9], 11: [12]}

def depth_fisrt_search():
    stack = Stack()
    stack.push([1])
    #將Tree root先壓入棧中
    while not stack.is_empty:
        path = stack.pop()
        #將一個(gè)節(jié)點(diǎn)的值從棧中取出并顯示
        print(path)
        if path[-1] in T:
            for child in reversed(T[path[-1]]):
                stack.push(list(path) + [child])
        #如果該節(jié)點(diǎn)有child吸重，則按照逆序方法把child壓入棧中，不同的是壓入的時(shí)候把前面做過的路徑也儲(chǔ)存了進(jìn)來
depth_first_exploration()
>>>
[1]
[1, 2]
[1, 2, 3]
[1, 4]
[1, 5]
[1, 5, 6]
[1, 5, 6, 7]
[1, 5, 6, 8]
[1, 5, 6, 8, 9]
[1, 5, 6, 10]
[1, 5, 11]
[1, 5, 11, 12]
[1, 5, 13]

上述代碼手動(dòng)輸入了一個(gè)tree T歪今，寫成自動(dòng)代碼是：

from collections import defaultdict

def tree():
    return defaultdict(tree)
#以tree作為type反復(fù)調(diào)用生成一個(gè)tree嚎幸，數(shù)據(jù)結(jié)構(gòu)是defaultdict

T = tree()
T[1][2][3] = None
T[1][4] = None
T[1][5][6][7] = None
T[1][5][6][8][9] = None
T[1][5][6][10] = None
T[1][5][11][12] = None
T[1][5][13] = None
#以每一條可以連通的路徑作為tree的生成過程，最終形成一個(gè)tree
T
>>>
defaultdict(<function __main__.tree>,
            {1: defaultdict(<function __main__.tree>,
                         {2: defaultdict(<function __main__.tree>, {3: None}),
                          4: None,
                          5: defaultdict(<function __main__.tree>,
                                      {6: defaultdict(<function __main__.tree>,
                                                   {7: None,
                                                    8: defaultdict(<function __main__.tree>,
                                                                {9: None}),
                                                    10: None}),
                                       11: defaultdict(<function __main__.tree>,
                                                   {12: None}),
                                       13: None})})})

基于tree的結(jié)構(gòu)update DFS的代碼如下：

def depth_first_exploration():
    stack = Stack()
    stack.push(([1], T[1]))
    #將tree root和后續(xù)的tree壓入棧中
    while not stack.is_empty():
        path, tree = stack.pop()
        #path指向當(dāng)前節(jié)點(diǎn)的值寄猩，tree指向當(dāng)前節(jié)點(diǎn)后續(xù)的tree
        print(path)
        if tree:
            for child in reversed(list(tree))：
                stack.push((list(path) + [child], tree[child]))
        #只要當(dāng)前節(jié)點(diǎn)后面還有枝葉嫉晶，則將其壓入棧中
        #壓入方法和前面一致，把concatenate之前path的child，和該節(jié)點(diǎn)后續(xù)的tree的defaultdict做成一個(gè)tuple壓入棧中替废。

2. Fractal(分形)

引用Wikipedia的解釋：“分形（英語：Fractal）箍铭，又稱碎形、殘形椎镣，通常被定義為“一個(gè)粗糙或零碎的幾何形狀诈火，可以分成數(shù)個(gè)部分，且每一部分都（至少近似地）是整體縮小后的形狀”状答，即具有自相似的性質(zhì)冷守。”
通過定義一個(gè)規(guī)則使得后續(xù)的復(fù)制能夠繼續(xù)剪况，自然界最常見的分形比如樹葉和海岸線教沾。
規(guī)則舉例：

Fractal

（1）原圖案各邊都縮小到原來的1/2
（2）以左下方為坐標(biāo)原點(diǎn)，輸出第1個(gè)新圖案到和原圖案相同的坐標(biāo)點(diǎn)
（3）以左下方為坐標(biāo)原點(diǎn)译断，輸出第2個(gè)新圖案到橫坐標(biāo)的1/2縱坐標(biāo)不變的坐標(biāo)點(diǎn)
（4）以左下方為坐標(biāo)原點(diǎn)，輸出第3個(gè)新圖案到橫坐標(biāo)的1/4縱坐標(biāo)向上移動(dòng)1/2的坐標(biāo)點(diǎn)
每次對圖中所有原圖案都執(zhí)行同樣的操作或悲，就形成了上述的圖片孙咪。
最終的圖案只體現(xiàn)規(guī)則，而不以最初的圖案改變巡语，比如同樣的規(guī)則下會(huì)形成下圖：

Fractal2

3. Queue

queue的準(zhǔn)則：first in first out翎蹈，順序與stack相比是反的。因?yàn)閝ueue只需要不斷改變兩頭的數(shù)據(jù)男公，所以linkedlist是適合queue的數(shù)據(jù)結(jié)構(gòu)荤堪，創(chuàng)建queue的class如下：

class Node:
    def __init__(self, value):
        self.value = value
        self.next_node = None

class QueueException(Exception):
    def __init__(self, message):
        self.message = message

class Queue:
    def __init__(self):
        self.head = None
        self.tail = None
    #Queue只對頭尾操作，所以initiation只需要定義head和tail
    
    def enqueue(self, value):
        new_node = Node(value)
        if not self.tail:
            self.tail = new_node
            self.head = self.tail
            return
        #判斷如果queue為空枢赔，tail指向新加入的點(diǎn)澄阳，head與其相同
        self.tail.next_node = new_node
        self.tail = new_node
        #在linkedlist尾端增加一個(gè)點(diǎn)，比如a - > b踏拜，加入新點(diǎn)c碎赢，這個(gè)時(shí)候先讓b的next等于c，然后tail指向c

    def dequeue(self):
        if not self.head:
            raise QueueException('Queue is empty)
        value = self.head.value
        self.head = self.head.next_node
        if not self.head:
            self.tail = None
        #每次從隊(duì)列中取走一個(gè)點(diǎn)速梗，head后移一位肮塞，如果head是None，那么tail是None姻锁，否則tail的指向不變
        return value

    def is_empty(self):
        return self.head is None

3.1 Queue Exercise

廣度優(yōu)先搜索是先進(jìn)入的先處理枕赵，符合queue的思路。

Tree

上圖的搜索流程如下位隶，注意壓棧的順序是從右向左：

No.         1    2     3    4    5    6  ...
Queue       1    2     4    5    3    6 ...
                 4     5    3    6      11 ...
                 5     3         11    13 ...
                                 13
Operation push1 pop1  pop2  pop4 pop5 pop3 ...
                push2 push3      push6    
                push4            push11 
                push5            push13