Detaillierte Erläuterung des Anwendungsstapels des Python-Algorithmus

Stapel (Stapel)

Der Stapel wird auch als Stapel bezeichnet. Es handelt sich um eine spezielle geordnete Liste. Die Einfüge- und Löschvorgänge werden oben im Stapel ausgeführt und folgen den Regeln von „First in, Last“. Out-, Last-In-, First-Out-Operationen.

Wie im Bild unten gezeigt

Zum Beispiel ist im Magazin einer Waffe die erste Kugel, die in das Magazin gesteckt wird, die letzte, wenn sie abgefeuert wird . Die letzte Kugel, die in das Magazin eingelegt wird, ist die erste Kugel, die beim Abfeuern abgefeuert wird.

Stack-Schnittstelle

Wenn Sie einen Stack erstellen, sollten Sie über die folgende Schnittstelle verfügen, um den Stack zu bedienen

Nach dem Stack wissen erfordert die obige Schnittstelle, dann ähnelt die Liste in Python einem Stapel und die bereitgestellte Schnittstelle lautet wie folgt:

Verwendungsbeispiel der Stapelschnittstelle in 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

Eine große Anzahl von Beispielen

Nachdem wir die Grundkonzepte des Stapels verstanden haben, schauen wir uns einige weitere Beispiele an, um unser Verständnis des Stapels zu erleichtern.

Klammerabgleich

Frage

Wenn der Ausdruck drei eckige Klammern (), [], {} enthalten darf, ist die Verschachtelungsreihenfolge willkürlich, zum Beispiel:

Richtiges Format

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

Falsches Format

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

Schreiben Sie eine Funktion, um zu bestimmen, ob die Klammerübereinstimmung einer Ausdruckszeichenfolge korrekt ist

Idee

Erstellen Sie einen leeren Stapel, um noch nicht gefundene linke Klammern zu speichern.

Komfortzeichenfolge: Schieben Sie den Stapel, wenn Sie auf eine linke Klammer stoßen, und öffnen Sie eine linke Klammer, wenn Sie auf eine rechte Klammer stoßen ;

Wenn im zweiten Schritt die rechte Klammer angetroffen wird, wenn der Stapel leer ist, bedeutet dies, dass die linke Klammer fehlt und nicht übereinstimmt.

Am Ende des zweiten Schritts Beim Durchlaufen ist der Stapel nicht leer, was darauf hinweist, dass die rechte Klammer fehlt und nicht übereinstimmt.

Lösungscode

Zum besseren Verständnis wird empfohlen, Punkte in Pycharm zu unterbrechen

#!/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(&#39;[(){()}]&#39;)
print(result)

Labyrinthproblem

Die Frage

verwendet ein zweidimensionales Array, um ein einfaches Labyrinth darzustellen, 0 repräsentiert das Passage, 1 stellt den Block dar, Maus An jedem Punkt können Sie die benachbarten vier Punkte Südosten und Nordwesten verschieben und einen Algorithmus entwerfen, um eine Maus zu simulieren, die durch ein Labyrinth geht und einen Weg vom Eingang zum Ausgang findet.

Wie im Bild gezeigt

Der richtige Weg nach draußen wird als rote Linie im Bild angezeigt

Denken

Verwenden Sie einen Stapel, um den Weg der Maus vom Eingang zum Ausgang aufzuzeichnen

Nachdem Sie einen bestimmten Punkt erreicht haben, schieben Sie die linke Seite des Punktes auf den Stapel und setzen Sie den Wert des Punktes auf 1. zeigt an, dass es passiert ist;

Wählen Sie einen der vier benachbarten Punkte und gehen Sie zu diesem Punkt

Wenn Sie nicht zu den vier benachbarten Punkten gehen, nachdem Sie a erreicht haben Bestimmter Punkt bedeutet, dass Sie sich in einer Sackgasse befinden. Gehen Sie einen Schritt zurück und versuchen Sie es mit den anderen Punkten. Wiederholen Sie die Schritte zwei, drei und vier, bis Sie den Ausgang gefunden haben 🎜>

Lösen Sie den Code

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

Postfix-Ausdrucksauswertung

Frage

Bei der Auswertung Als Ausdruck verwendet der Compiler normalerweise einen Postfix-Ausdruck, für den keine Klammern erforderlich sind:

Schreiben Sie ein Programm, um die Postfix-Ausdrucksauswertungsfunktion zu implementieren.

Idee

Erstellen Sie einen Stapel, um die zu berechnenden Operanden zu speichern.

Durchlaufen Sie die Zeichenfolge, schieben Sie den Operanden in den Stapel, wenn Sie darauf stoßen, und lassen Sie ihn herausspringen, wenn Sie darauf stoßen Das Operationssymbol stapelt Operanden (n-mal) und führt entsprechende Berechnungen durch. Das Berechnungsergebnis ist der neue Operand, der auf den Stapel zurückgeschoben wird und auf die Berechnung wartet

Gemäß dem obigen Prozess wird der gesamte Ausdruck durchlaufen, und zwar nur das Endergebnis bleibt auf dem Stapel ;

Lösungscode

Rucksackproblem

#!/use/bin/env python
# _*_ coding:utf-8 _*_
operators = { # 运算符操作表
 '+': 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: 后缀表达式
 :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

Frage

Es gibt einen Rucksack, der das kann fassen 10 kg Gegenstände, und jetzt sind es 6 Gegenstände. Sie sind:

Schreiben und finden Sie alle Lösungen, die den Rucksack füllen können, z. B. Gegenstand 1 + Gegenstand 5.

Lösungscode

Zusammenfassung

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

Das Obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels jedem beim Lernen oder bei der Arbeit helfen kann . Wenn Sie Fragen haben, können Sie eine Nachricht hinterlassen.

Ausführlichere Erläuterungen zu praktischen Stacks für Python-Algorithmusanwendungen finden Sie auf der chinesischen PHP-Website!