歡迎光臨
每天分享高質量文章

Python 演算法實戰系列:棧

學Python最簡單的方法是什麼?推薦閱讀:Python開發工程師成長魔法


棧(stack)又稱之為堆棧是一個特殊的有序表,其插入和刪除操作都在棧頂進行操作,並且按照先進後出,後進先出的規則進行運作。

如下圖所示

例如槍的彈匣,第一顆放進彈匣的子彈反而在發射出去的時候是最後一個,而最後放入彈匣的一顆子彈在打出去的時候是第一顆發射出去的。

棧的接口

如果你創建了一個棧,那麼那麼應該具有以下接口來進行對棧的操作

知道棧需要上述的接口後,那麼在Python中,串列就類似是一個棧,提供接口如下:

Python中的棧接口使用實體:

# 創建一個棧

In [1]: s = []

# 往棧內添加一個元素

In [2]: s.append(1)

In [3]: s

Out[3]: [1]

# 刪除棧內的一個元素

In [4]: s.pop()

Out[4]: 1

In [5]: s

Out[5]: []

# 判斷棧是否為空

In [6]: not s

Out[6]: True

In [7]: s.append(1)

In [8]: not s

Out[8]: False

# 獲取棧內元素的數量

In [9]: len(s)

Out[9]: 1

In [10]: s.append(2)

In [11]: s.append(3)

# 取棧頂的元素

In [12]: s[1]

Out[12]: 3

一大波實體

在瞭解棧的基本概念之後,讓我們再來看幾個實體,以便於理解棧。

括號匹配

題目

假如運算式中允許包含三中括號()、[]、{},其嵌套順序是任意的,例如:

正確的格式

{()[()]},[{({})}]

錯誤的格式

[(]),[()),(()}

編寫一個函式,判斷一個運算式字串,括號匹配是否正確

思路

  1. 創建一個空棧,用來儲存尚未找到的左括號;

  2. 便利字串,遇到左括號則壓棧,遇到右括號則出棧一個左括號進行匹配;

  3. 在第二步驟過程中,如果空棧情況下遇到右括號,說明缺少左括號,不匹配;

  4. 在第二步驟遍歷結束時,棧不為空,說明缺少右括號,不匹配;

解決代碼

建議在pycharm中打斷點,以便於更好的理解

#!/use/bin/env python

# _*_ coding:utf-8 _*_

LEFT = {‘(‘, ‘[‘, ‘{‘}  # 左括號

RIGHT = {‘)’, ‘]’, ‘}’}  # 右括號

def match(expr):

    “””

    :param expr:  傳過來的字串

    :return:  傳回是否是正確的

    “””

    stack = []  # 創建一個棧

    for brackets in expr:  # 迭代傳過來的所有字串

        if brackets in LEFT:  # 如果當前字符在左括號內

            stack.append(brackets)  # 把當前左括號入棧

        elif brackets in RIGHT:  # 如果是右括號

            if not stack or not 1 <= ord(brackets)ord(stack[1]) <= 2:

                # 如果當前棧為空,()]

                # 如果右括號減去左括號的值不是小於等於2大於等於1

                return False  # 傳回False

            stack.pop()  # 刪除左括號

    return not stack  # 如果棧內沒有值則傳回True,否則傳回False

result = match(‘[(){()}]’)

print(result)

迷宮問題

題目

用一個二維陣列表示一個簡單的迷宮,用0表示通路,用1表示阻斷,老鼠在每個點上可以移動相鄰的東南西北四個點,設計一個演算法,模擬老鼠走迷宮,找到從入口到出口的一條路徑。

如圖所示

出去的正確線路如圖中的紅線所示

思路

  1. 用一個棧來記錄老鼠從入口到出口的路徑

  2. 走到某點後,將該點左邊壓棧,並把該點值置為1,表示走過了;

  3. 從臨近的四個點中可到達的點中任意選取一個,走到該點;

  4. 如果在到達某點後臨近的4個點都不走,說明已經走入死衚衕,此時退棧,退回一步嘗試其他點;

  5. 反覆執行第二、三、四步驟直到找到出口;

解決代碼

#!/use/bin/env python

# _*_ coding:utf-8 _*_

def initMaze():

    “””

    :return: 初始化迷宮

    “””

    maze = [[0] * 7 for _ in range(5 + 2)]  # 用串列解析創建一個7*7的二維陣列,為了確保迷宮四周都是牆

    walls = [  # 記錄了牆的位置

        (1, 3),

        (2, 1), (2, 5),

        (3, 3), (3, 4),

        (4, 2),  # (4, 3),  # 如果把(4, 3)點也設置為牆,那麼整個迷宮是走不出去的,所以會傳回一個空串列

        (5, 4)

    ]

    for i in range(7):  # 把迷宮的四周設置成牆

        maze[i][0] = maze[i][1] = 1

        maze[0][i] = maze[1][i] = 1

    for i, j in walls:  # 把所有牆的點設置為1

        maze[i][j] = 1

    return maze

“””

[1, 1, 1, 1, 1, 1, 1]

[1, 0, 0, 1, 0, 0, 1]

[1, 1, 0, 0, 0, 1, 1]

[1, 0, 0, 1, 1, 0, 1]

[1, 0, 1, 0, 0, 0, 1]

[1, 0, 0, 0, 1, 0, 1]

[1, 1, 1, 1, 1, 1, 1]

“””

def path(maze, start, end):

    “””

    :param maze: 迷宮

    :param start: 起始點

    :param end: 結束點

    :return: 行走的每個點

    “””

    i, j = start  # 分解起始點的坐標

    ei, ej = end  # 分解結束點的左邊

    stack = [(i, j)]  # 創建一個棧,並讓老鼠站到起始點的位置

    maze[i][j] = 1  # 走過的路置為1

    while stack:  # 棧不為空的時候繼續走,否則退出

        i, j = stack[1]  # 獲取當前老鼠所站的位置點

        if (i, j) == (ei, ej): break  # 如果老鼠找到了出口

        for di, dj in [(0,1), (0, 1), (1, 0), (1, 0)]:  # 左右上下

            if maze[i + di][j + dj] == 0:  # 如果當前點可走

                maze[i + di][j + dj] = 1  # 把當前點置為1

                stack.append((i + di, j + dj))  # 把當前的位置添加到棧裡面

                break

        else:  # 如果所有的點都不可走

            stack.pop()  # 退回上一步

    return stack  # 如果迷宮不能走則傳回空棧

Maze = initMaze()  # 初始化迷宮

result = path(maze=Maze, start=(1, 1), end=(5, 5))  # 老鼠開始走迷宮

print(result)

# [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]

後綴運算式求值

題目

計算一個運算式時,編譯器通常使用後綴運算式,這種運算式不需要括號:

編寫程式實現後綴運算式求值函式。

思路

  1. 建立一個棧來儲存待計算的運算元;

  2. 遍歷字串,遇到運算元則壓入棧中,遇到運算子號則出棧運算元(n次),進行相應的計算,計算結果是新的運算元壓回棧中,等待計算

  3. 按上述過程,遍歷完整個運算式,棧中只剩下最終結果;

解決代碼

#!/use/bin/env python

# _*_ coding:utf-8 _*_

operators = {  # 運算子操作表

    ‘+’: lambda op1, op2: op1 + op2,

    ‘-‘: lambda op1, op2: op1op2,

    ‘*’: lambda op1, op2: op1 * op2,

    ‘/’: lambda op1, op2: op1 / op2,

}

def evalPostfix(e):

    “””

    :param e: 後綴運算式

    :return: 正常情況下棧內的第一個元素就是計算好之後的值

    “””

    tokens = e.split()  # 把傳過來的後綴運算式切分成串列

    stack = []

    for token in tokens:  # 迭代串列中的元素

        if token.isdigit():  # 如果當前元素是數字

            stack.append(int(token))  # 就追加到棧裡邊

        elif token in operators.keys():  # 如果當前元素是運算子

            f = operators[token]  # 獲取運算子操作表中對應的lambda運算式

            op2 = stack.pop()  # 根據先進後出的原則,先讓第二個元素出棧

            op1 = stack.pop()  # 在讓第一個元素出棧

            stack.append(f(op1, op2))  # 把計算的結果在放入到棧內

    return stack.pop()  # 傳回棧內的第一個元素

result = evalPostfix(‘2 3 4 * +’)

print(result)

# 14

背包問題

題目

有一個背包能裝10kg的物品,現在有6件物品分別為:

編寫找出所有能將背包裝滿的解,如物品1+物品5。

解決代碼

#!/use/bin/env python

# _*_ coding:utf-8 _*_

def knapsack(t, w):

    “””

    :param t: 背包總容量

    :param w: 物品重量串列

    :return:

    “””

    n = len(w)  # 可選的物品數量

    stack = []  # 創建一個棧

    k = 0  # 當前所選擇的物品游標

    while stack or k < n:  # 棧不為空或者k

        while t > 0 and k < n:  # 還有剩餘空間並且有物品可裝

            if t >= w[k]:  # 剩餘空間大於等於當前物品重量

                stack.append(k)  # 把物品裝備背包

                t -= w[k]  # 背包空間減少

            k += 1  # 繼續向後找

        if t == 0:  # 找到瞭解

            print(stack)

        # 回退過程

        k = stack.pop()  # 把最後一個物品拿出來

        t += w[k]  # 背包總容量加上w[k]

        k += 1  # 裝入下一個物品

knapsack(10, [1, 8, 4, 3, 5, 2])

“””

[0, 2, 3, 5]

[0, 2, 4]

[1, 5]

[3, 4, 5]

“””

來源:安生 




————近期開班————

《馬哥教育Python自動化開發全能實戰班》是馬哥教育聯合阿裡、豆瓣、大眾點評等一線Python工程師,根據目前企業需求的Python開發人才進行了深度定製,加入大量一線互聯網公司:大眾點評、餓了麽、騰訊等生產環境真是專案,課程由淺入深,從Python基礎到Python高級,讓你融匯貫通Python基礎理論到日誌分析、todolist任務管理系統、類Flask框架多人博客、CMDB資產管理、任務調度系統、運維流程系統六大專案實戰,手把手教學讓你從0開始蛻變成Hold住年薪30萬的Python自動化開發人才。

10期面授班:2018年03月05號(北京)

11期網絡班:2018年03月17號網絡

更多Python好文請點擊【閱讀原文】哦

↓↓↓

赞(0)

分享創造快樂