Python算法應(yīng)用實(shí)戰(zhàn)之棧詳解
棧(stack)
棧又稱之為堆棧是一個(gè)特殊的有序表,其插入和刪除操作都在棧頂進(jìn)行操作,并且按照先進(jìn)后出,后進(jìn)先出的規(guī)則進(jìn)行運(yùn)作。
如下圖所示
例如槍的彈匣,第一顆放進(jìn)彈匣的子彈反而在發(fā)射出去的時(shí)候是最后一個(gè),而最后放入彈匣的一顆子彈在打出去的時(shí)候是第一顆發(fā)射出去的。
棧的接口
如果你創(chuàng)建了一個(gè)棧,那么那么應(yīng)該具有以下接口來進(jìn)行對(duì)棧的操作
接口 | 描述 |
---|---|
push() | 入棧 |
pop() | 出棧 |
isEmpty() | 判斷是否為空棧 |
length() | 獲取棧的長(zhǎng)度 |
getTop() | 取棧頂?shù)脑?,元素不出?/td> |
知道棧需要上述的接口后,那么在Python中,列表就類似是一個(gè)棧,提供接口如下:
操作 | 描述 |
---|---|
s = [] | 創(chuàng)建一個(gè)棧 |
s.append(x) | 往棧內(nèi)添加一個(gè)元素 |
s.pop() | 在棧內(nèi)刪除一個(gè)元素 |
not s | 判斷是否為空棧 |
len(s) | 獲取棧內(nèi)元素的數(shù)量 |
s[-1] | 獲取棧頂?shù)脑?/td> |
Python中的棧接口使用實(shí)例:
# 創(chuàng)建一個(gè)棧 In [1]: s = [] # 往棧內(nèi)添加一個(gè)元素 In [2]: s.append(1) In [3]: s Out[3]: [1] # 刪除棧內(nèi)的一個(gè)元素 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 # 獲取棧內(nèi)元素的數(shù)量 In [9]: len(s) Out[9]: 1 In [10]: s.append(2) In [11]: s.append(3) # 取棧頂?shù)脑? In [12]: s[-1] Out[12]: 3
一大波實(shí)例
在了解棧的基本概念之后,讓我們?cè)賮砜磶讉€(gè)實(shí)例,以便于理解棧。
括號(hào)匹配
題目
假如表達(dá)式中允許包含三中括號(hào)()、[]、{},其嵌套順序是任意的,例如:
正確的格式
{()[()]},[{({})}]
錯(cuò)誤的格式
[(]),[()),(()}
編寫一個(gè)函數(shù),判斷一個(gè)表達(dá)式字符串,括號(hào)匹配是否正確
思路
- 創(chuàng)建一個(gè)空棧,用來存儲(chǔ)尚未找到的左括號(hào);
- 便利字符串,遇到左括號(hào)則壓棧,遇到右括號(hào)則出棧一個(gè)左括號(hào)進(jìn)行匹配;
- 在第二步驟過程中,如果空棧情況下遇到右括號(hào),說明缺少左括號(hào),不匹配;
- 在第二步驟遍歷結(jié)束時(shí),棧不為空,說明缺少右括號(hào),不匹配;
解決代碼
建議在pycharm中打斷點(diǎn),以便于更好的理解
#!/use/bin/env python # _*_ coding:utf-8 _*_ LEFT = {'(', '[', '{'} # 左括號(hào) RIGHT = {')', ']', '}'} # 右括號(hào) def match(expr): """ :param expr: 傳過來的字符串 :return: 返回是否是正確的 """ stack = [] # 創(chuàng)建一個(gè)棧 for brackets in expr: # 迭代傳過來的所有字符串 if brackets in LEFT: # 如果當(dāng)前字符在左括號(hào)內(nèi) stack.append(brackets) # 把當(dāng)前左括號(hào)入棧 elif brackets in RIGHT: # 如果是右括號(hào) if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2: # 如果當(dāng)前棧為空,()] # 如果右括號(hào)減去左括號(hào)的值不是小于等于2大于等于1 return False # 返回False stack.pop() # 刪除左括號(hào) return not stack # 如果棧內(nèi)沒有值則返回True,否則返回False result = match('[(){()}]') print(result)
迷宮問題
題目
用一個(gè)二維數(shù)組表示一個(gè)簡(jiǎn)單的迷宮,用0表示通路,用1表示阻斷,老鼠在每個(gè)點(diǎn)上可以移動(dòng)相鄰的東南西北四個(gè)點(diǎn),設(shè)計(jì)一個(gè)算法,模擬老鼠走迷宮,找到從入口到出口的一條路徑。
如圖所示
出去的正確線路如圖中的紅線所示
思路
- 用一個(gè)棧來記錄老鼠從入口到出口的路徑
- 走到某點(diǎn)后,將該點(diǎn)左邊壓棧,并把該點(diǎn)值置為1,表示走過了;
- 從臨近的四個(gè)點(diǎn)中可到達(dá)的點(diǎn)中任意選取一個(gè),走到該點(diǎn);
- 如果在到達(dá)某點(diǎn)后臨近的4個(gè)點(diǎn)都不走,說明已經(jīng)走入死胡同,此時(shí)退棧,退回一步嘗試其他點(diǎn);
- 反復(fù)執(zhí)行第二、三、四步驟直到找到出口;
解決代碼
#!/use/bin/env python # _*_ coding:utf-8 _*_ def initMaze(): """ :return: 初始化迷宮 """ maze = [[0] * 7 for _ in range(5 + 2)] # 用列表解析創(chuàng)建一個(gè)7*7的二維數(shù)組,為了確保迷宮四周都是墻 walls = [ # 記錄了墻的位置 (1, 3), (2, 1), (2, 5), (3, 3), (3, 4), (4, 2), # (4, 3), # 如果把(4, 3)點(diǎn)也設(shè)置為墻,那么整個(gè)迷宮是走不出去的,所以會(huì)返回一個(gè)空列表 (5, 4) ] for i in range(7): # 把迷宮的四周設(shè)置成墻 maze[i][0] = maze[i][-1] = 1 maze[0][i] = maze[-1][i] = 1 for i, j in walls: # 把所有墻的點(diǎn)設(shè)置為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: 起始點(diǎn) :param end: 結(jié)束點(diǎn) :return: 行走的每個(gè)點(diǎn) """ i, j = start # 分解起始點(diǎn)的坐標(biāo) ei, ej = end # 分解結(jié)束點(diǎn)的左邊 stack = [(i, j)] # 創(chuàng)建一個(gè)棧,并讓老鼠站到起始點(diǎn)的位置 maze[i][j] = 1 # 走過的路置為1 while stack: # 棧不為空的時(shí)候繼續(xù)走,否則退出 i, j = stack[-1] # 獲取當(dāng)前老鼠所站的位置點(diǎn) 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: # 如果當(dāng)前點(diǎn)可走 maze[i + di][j + dj] = 1 # 把當(dāng)前點(diǎn)置為1 stack.append((i + di, j + dj)) # 把當(dāng)前的位置添加到棧里面 break else: # 如果所有的點(diǎn)都不可走 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)]
后綴表達(dá)式求值
題目
計(jì)算一個(gè)表達(dá)式時(shí),編譯器通常使用后綴表達(dá)式,這種表達(dá)式不需要括號(hào):
中綴表達(dá)式 | 后綴表達(dá)式 |
---|---|
2 + 3 * 4 | 2 3 4 * + |
( 1 + 2 ) * ( 6 / 3 ) + 2 | 1 2 + 6 3 / * 2 + |
18 / ( 3 * ( 1 + 2 ) ) | 18 3 1 2 + * / |
編寫程序?qū)崿F(xiàn)后綴表達(dá)式求值函數(shù)。
思路
- 建立一個(gè)棧來存儲(chǔ)待計(jì)算的操作數(shù);
- 遍歷字符串,遇到操作數(shù)則壓入棧中,遇到操作符號(hào)則出棧操作數(shù)(n次),進(jìn)行相應(yīng)的計(jì)算,計(jì)算結(jié)果是新的操作數(shù)壓回棧中,等待計(jì)算
- 按上述過程,遍歷完整個(gè)表達(dá)式,棧中只剩下最終結(jié)果;
解決代碼
#!/use/bin/env python # _*_ coding:utf-8 _*_ operators = { # 運(yùn)算符操作表 '+': lambda op1, op2: op1 + op2, '-': lambda op1, op2: op1 - op2, '*': lambda op1, op2: op1 * op2, '/': lambda op1, op2: op1 / op2, } def evalPostfix(e): """ :param e: 后綴表達(dá)式 :return: 正常情況下棧內(nèi)的第一個(gè)元素就是計(jì)算好之后的值 """ tokens = e.split() # 把傳過來的后綴表達(dá)式切分成列表 stack = [] for token in tokens: # 迭代列表中的元素 if token.isdigit(): # 如果當(dāng)前元素是數(shù)字 stack.append(int(token)) # 就追加到棧里邊 elif token in operators.keys(): # 如果當(dāng)前元素是操作符 f = operators[token] # 獲取運(yùn)算符操作表中對(duì)應(yīng)的lambda表達(dá)式 op2 = stack.pop() # 根據(jù)先進(jìn)后出的原則,先讓第二個(gè)元素出棧 op1 = stack.pop() # 在讓第一個(gè)元素出棧 stack.append(f(op1, op2)) # 把計(jì)算的結(jié)果在放入到棧內(nèi) return stack.pop() # 返回棧內(nèi)的第一個(gè)元素 result = evalPostfix('2 3 4 * +') print(result) # 14
背包問題
題目
有一個(gè)背包能裝10kg的物品,現(xiàn)在有6件物品分別為:
物品名稱 | 重量 |
---|---|
物品0 | 1kg |
物品1 | 8kg |
物品2 | 4kg |
物品3 | 3kg |
物品4 | 5kg |
物品5 | 2kg |
編寫找出所有能將背包裝滿的解,如物品1+物品5。
解決代碼
#!/use/bin/env python # _*_ coding:utf-8 _*_ def knapsack(t, w): """ :param t: 背包總?cè)萘? :param w: 物品重量列表 :return: """ n = len(w) # 可選的物品數(shù)量 stack = [] # 創(chuàng)建一個(gè)棧 k = 0 # 當(dāng)前所選擇的物品游標(biāo) while stack or k < n: # 棧不為空或者k<n while t > 0 and k < n: # 還有剩余空間并且有物品可裝 if t >= w[k]: # 剩余空間大于等于當(dāng)前物品重量 stack.append(k) # 把物品裝備背包 t -= w[k] # 背包空間減少 k += 1 # 繼續(xù)向后找 if t == 0: # 找到了解 print(stack) # 回退過程 k = stack.pop() # 把最后一個(gè)物品拿出來 t += w[k] # 背包總?cè)萘考由蟱[k] k += 1 # 裝入下一個(gè)物品 knapsack(10, [1, 8, 4, 3, 5, 2]) """ [0, 2, 3, 5] [0, 2, 4] [1, 5] [3, 4, 5] """
總結(jié)
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助,如果有疑問大家可以留言交流。
- Python算法的時(shí)間復(fù)雜度和空間復(fù)雜度(實(shí)例解析)
- Python算法中的時(shí)間復(fù)雜度問題
- python算法題 鏈表反轉(zhuǎn)詳解
- python算法與數(shù)據(jù)結(jié)構(gòu)之單鏈表的實(shí)現(xiàn)代碼
- python算法與數(shù)據(jù)結(jié)構(gòu)之冒泡排序?qū)嵗斀?/a>
- 詳解python算法之冒泡排序
- Python算法之圖的遍歷
- Python算法輸出1-9數(shù)組形成的結(jié)果為100的所有運(yùn)算式
- python算法演練_One Rule 算法(詳解)
- python算法表示概念掃盲教程
- Python算法之棧(stack)的實(shí)現(xiàn)
- python算法學(xué)習(xí)之計(jì)數(shù)排序?qū)嵗?/a>
- Python集成學(xué)習(xí)之Blending算法詳解
相關(guān)文章
Numpy中矩陣matrix讀取一列的方法及數(shù)組和矩陣的相互轉(zhuǎn)換實(shí)例
今天小編就為大家分享一篇Numpy中矩陣matrix讀取一列的方法及數(shù)組和矩陣的相互轉(zhuǎn)換實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2018-07-07Python實(shí)現(xiàn)從url中提取域名的幾種方法
這篇文章主要介紹了Python實(shí)現(xiàn)從url中提取域名的幾種方法,本文給出了3種方法實(shí)現(xiàn)在URL中提取域名的需求,需要的朋友可以參考下2014-09-09Python列表(list)、字典(dict)、字符串(string)基本操作小結(jié)
這篇文章主要介紹了Python列表(list)、字典(dict)、字符串(string)基本操作小結(jié),本文總結(jié)了最基本最常用的一些操作,需要的朋友可以參考下2014-11-11python輸出數(shù)學(xué)符號(hào)實(shí)例
這篇文章主要介紹了python輸出數(shù)學(xué)符號(hào)實(shí)例,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-05-05python使用tensorflow保存、加載和使用模型的方法
本篇文章主要介紹了python使用tensorflow保存、加載和使用模型的方法,小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過來看看吧2018-01-01python讀取測(cè)試數(shù)據(jù)的多種方式
本文主要介紹了python讀取測(cè)試數(shù)據(jù)的多種方式,文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-08-08