Pythonアルゴリズム応用実践スタック

スタックとは何ですか? 先入れ後出しのデータ構造 (First In Last Out)、つまり、限定された操作を備えた線形テーブルとして理解できます。次の記事では主に Python でのスタックの応用例を紹介します。必要な方はぜひ参考にしてください。

スタック

スタックはスタックとも呼ばれ、挿入と削除の操作はスタックの先頭で実行され、先入れ後出しの規則に従って実行されます。後入れ先出し操作。

下の写真のように

例えば、銃の弾倉では、発砲時にはマガジンに最初に入れた弾丸が最後となり、マガジンに入れられた最後の弾丸はそれは発売されたときに最初に発射されました。

スタックインターフェース

スタックを作成する場合、スタックを操作するために次のインターフェースが必要です

インターフェース	説明
)	スタックにプッシュ
pop()	スタックからポップ
isEmpty()	スタックが空かどうかを判定
length()	スタックの長さを取得
getTop()	スタックの最上位にある要素を取得します。要素はスタックから飛び出ません

スタックが上記のインターフェイスを必要とすることがわかった後、Python では、リストは次のようになります。スタックであり、提供されるインターフェイスは次のとおりです:

Operation	Description
s = []	Create a stack
s.append(x)	スタックに要素を追加
スタック内のs.pop()	要素を削除
s	ではない スタックが空かどうかを判定
len(s)	番号を取得スタック内の要素の数
s[-1]	スタックの先頭にある要素を取得します

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

多数の例

スタックの基本概念を理解した後、スタックを理解しやすくするためにさらにいくつかの例を見てみましょう。

括弧の一致

質問

式に 3 つの角括弧 ()、[]、{} を含めることができる場合、ネスト順序は任意です。例:

正しい形式

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

形式が間違っています

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

式文字列内の括弧の一致が正しいかどうかを判断する関数を作成してください

アイデア

1. 見つからなかった左括弧を格納する空のスタックを作成します

2. 便利な文字列。左括弧が見つかった場合はスタックにプッシュされ、右括弧が見つかった場合は一致するために左括弧がスタックからポップされます

3. 2 番目のステップでは、右括弧が存在する場合、スタックが空の場合に発生します。これは、左括弧が欠落していることを意味します。

4. トラバーサルの 2 番目のステップの終了時に、スタックが空ではなく、右括弧が欠落していることを示します。一致しません。

コードを解決します

よりよく理解するには、pycharm でポイントを分割することをお勧めします

迷路問題

質問

単純な迷路。通路を表すのに 0 を使用し、ブロックを表すのに 1 を使用します。マウスは各点で隣接して移動できます。南東、北西、北西の 4 つの点で、マウスが迷路を歩くのをシミュレートするアルゴリズムを設計します。入り口から出口までの道。

写真の通り

正しい出口は写真の赤い線で示されています

アイデア

スタックを使用して入口から出口までのマウスの経路を記録します

1. 特定のポイントに到達したら、ポイントの左側をスタックにプッシュし、ポイントの値を 1 に設定して、歩いたことを示します

2. 近くの 4 つのポイントからいずれか 1 つを選択します。ポイントを指定してそのポイントまで歩きます

3. 特定のポイントに到達した後、近くの 4 つのポイントに行かない場合は、行き止まりに達したことを意味します。この時点で、スタックを出て、一歩戻ります。他のポイントを試してください。

4. 出口が見つかるまでステップ 2、3、4 を繰り返します。

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

後置式の評価

質問

コンパイラは通常、括弧を必要としない後置式を使用します:

中置式

後置式

2 + 3 * 42 3 4 * + ( 1 + 2 ) * ( 6 / 3 ) + 21 2 + 6 3 / * 2 +18 / ( 3 * ( 1 + 2 ) )18 3 1 2 + * /

编写程序实现后缀表达式求值函数。

思路

1. 建立一个栈来存储待计算的操作数；

2. 遍历字符串，遇到操作数则压入栈中，遇到操作符号则出栈操作数(n次)，进行相应的计算，计算结果是新的操作数压回栈中，等待计算

3. 按上述过程，遍历完整个表达式，栈中只剩下最终结果；
   

解决代码

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

背包问题

题目

有一个背包能装10kg的物品，现在有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: 背包总容量
 :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]
"""

以上がPythonアルゴリズム応用実践スタックの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。