# 創(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

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

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

#!/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)

#!/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)]

#!/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

#!/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]
"""