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]:nots

Out[6]:True

In[7]:s.append(1)

In[8]:nots

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

一大波實例

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

括弧匹配

題目

假如表達式中允許包含三中括弧()、[]、{}，其嵌套順序是任意的，例如：

正確的格式

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

錯誤的格式

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

編寫一個函數，判斷一個表達式字元串，括弧匹配是否正確

思路

創建一個空棧，用來存儲尚未找到的左括弧；

便利字元串，遇到左括弧則壓棧，遇到右括弧則出棧一個左括弧進行匹配；

在第二步驟過程中，如果空棧情況下遇到右括弧，說明缺少左括弧，不匹配；

在第二步驟遍歷結束時，棧不為空，說明缺少右括弧，不匹配；

解決代碼

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

#!/use/bin/env python

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

LEFT={ ( , [ , { }# 左括弧

RIGHT={ ) , ] , } }# 右括弧

defmatch(expr):

"""

:param expr: 傳過來的字元串

:return: 返回是否是正確的

"""

stack=[]# 創建一個棧

forbracketsinexpr:# 迭代傳過來的所有字元串

ifbracketsinLEFT:# 如果當前字元在左括弧內

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

elifbracketsinRIGHT:# 如果是右括弧

ifnotstackornot1

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

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

returnFalse# 返回False

stack.pop()# 刪除左括弧

returnnotstack# 如果棧內沒有值則返回True，否則返回False

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

print(result)

迷宮問題

題目

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

如圖所示

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

思路

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

走到某點後，將該點左邊壓棧，並把該點值置為1，表示走過了；

從臨近的四個點中可到達的點中任意選取一個，走到該點；

如果在到達某點後臨近的4個點都不走，說明已經走入死胡同，此時退棧，退回一步嘗試其他點；

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

解決代碼

#!/use/bin/env python

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

definitMaze():

"""

:return: 初始化迷宮

"""

maze=[[]*7for_inrange(5+2)]# 用列表解析創建一個7*7的二維數組，為了確保迷宮四周都是牆

walls=[# 記錄了牆的位置

(1,3),

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

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

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

(5,4)

]

foriinrange(7):# 把迷宮的四周設置成牆

maze[i][]=maze[i][-1]=1

maze[][i]=maze[-1][i]=1

fori,jinwalls:# 把所有牆的點設置為1

maze[i][j]=1

returnmaze

"""

[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]

"""

defpath(maze,start,end):

"""

:param maze: 迷宮

:param start: 起始點

:param end: 結束點

:return: 行走的每個點

"""

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

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

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

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

whilestack:# 棧不為空的時候繼續走，否則退出

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

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

fordi,djin[(,-1),(,1),(-1,),(1,)]:# 左右上下

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

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

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

break

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

stack.pop()# 退回上一步

returnstack# 如果迷宮不能走則返回空棧

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)]

後綴表達式求值

題目

計算一個表達式時，編譯器通常使用後綴表達式，這種表達式不需要括弧：

編寫程序實現後綴表達式求值函數。

思路

建立一個棧來存儲待計算的操作數；

遍歷字元串，遇到操作數則壓入棧中，遇到操作符號則出棧操作數(n次)，進行相應的計算，計算結果是新的操作數壓回棧中，等待計算

按上述過程，遍歷完整個表達式，棧中只剩下最終結果；

解決代碼

#!/use/bin/env python

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

operators={# 運算符操作表

+ :lambdaop1,op2:op1+op2,

- :lambdaop1,op2:op1-op2,

* :lambdaop1,op2:op1*op2,

/ :lambdaop1,op2:op1/op2,

}

defevalPostfix(e):

"""

:param e: 後綴表達式

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

"""

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

stack=[]

fortokenintokens:# 迭代列表中的元素

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

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

eliftokeninoperators.keys():# 如果當前元素是操作符

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

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

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

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

returnstack.pop()# 返回棧內的第一個元素

result=evalPostfix( 2 3 4 * + )

print(result)

# 14

背包問題

題目

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

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

解決代碼

#!/use/bin/env python

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

defknapsack(t,w):

"""

:param t: 背包總容量

:param w: 物品重量列表

:return:

"""

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

stack=[]# 創建一個棧

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

whilestackork

whilet>andk

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

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

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

k+=1# 繼續向後找

ift==:# 找到了解

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]

"""

點擊展開全文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！