Pythonアルゴリズム実践シリーズ: スタック

スタックは、特別な順序付けがされたテーブルです。挿入および削除操作はスタックの先頭で実行され、先入れ後出しおよび後入れ先出しのルールに従って動作します。

下の図に示すように

たとえば、銃のマガジンでは、最初にマガジンに入れられた弾丸が発射されるときに最後に発射され、最後にマガジンに入れられた弾丸が発射されるときに最初に発射されます。

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

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

スタックには上記のインターフェースが必要であることがわかっているので、Python ではリストはスタックに似ており、次のインターフェースを提供します。

Python でスタックインターフェイスを使用する例:

 # スタックを作成する
 
 [1]において: s = [] 
 
 # スタックに要素を追加する
 
 [2]では: s.append(1) 
 
 [3]では： 
 
アウト[3]:[1] 
 
 # スタックから要素を削除する
 
 [4]では：s.pop() 
 
アウト[4]: 1 
 
 [5]では： 
 
アウト[5]: [] 
 
 # スタックが空かどうか確認する
 
 [6]では: sではない
 
アウト[6]:真  
 
 [7]では: s.append(1) 
 
 [8]では: sではない
 
アウト[8]:偽  
 
 # スタック内の要素数を取得する
 
 [9] : len(s) 
 
アウト[9]: 1 
 
 [10]では: s.append(2) 
 
 [11]では: s.append(3) 
 
 # スタックの一番上の要素を取得する
 
 [12]では: s[-1] 
 
アウト[12]: 3

多数の例

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

括弧のマッチング

トピック

式に 3 つの角括弧 ()、[]、{} を含めることができる場合、入れ子の順序は任意です。次に例を示します。

正しいフォーマット

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

形式が間違っています

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

式文字列の括弧のマッチングが正しいかどうかを判断する関数を作成します。

アイデア

まだ見つかっていない左括弧を格納するための空のスタックを作成します。
便利な文字列。左括弧に遭遇するとスタックにプッシュし、一致する右括弧に遭遇するとスタックに左括弧をポップします。
2 番目のステップでは、右括弧が空のスタックで見つかった場合、左括弧が欠落しており一致しないことを意味します。
2 番目のステップのトラバーサルの終了時にスタックが空でなく、右括弧が欠落していて一致しないことを示します。

ソリューションコード

理解を深めるためにpycharmでブレークポイントを設定することをお勧めします

#!/use/bin/env python 
 
 # _*_ コーディング:utf-8 _*_ 
 
 LEFT = { '(' , '[' , '{' } # 左括弧
 
 RIGHT = { ')' , ']' , '}' } # 右括弧
 
 def match(式): 
 
 「」 「 」 
 
    :param expr: 渡された文字列
 
    : return : 正しいかどうかを返します
 
 「」 「 」 
 
    stack = [] # スタックを作成する
 
 for brackets in expr: # 渡されたすべての文字列を反復処理します
 
        括弧内の  LEFT : # 現在の文字が左括弧内にある場合
 
            stack.append(brackets) # 現在の左括弧をスタックにプッシュします
 
        elif括弧内  RIGHT : # 右括弧の場合
 
            スタックしない場合は  1 <= ord(brackets) - ord(stack[-1]) <= 2ではない: 
 
                # 現在のスタックが空の場合、()] 
 
                # 右括弧の値から左括弧の値を引いた値が2以下でなく1以上である場合
 
戻る  False # Falseを返します  
 
            stack.pop() # 左括弧を削除
 
戻る  not stack # スタックに値がない場合にはTrueを返し、そうでない場合はFalseを返します  
 
結果 = 一致( '[(){()}]' ) 
 
印刷(結果)

迷路問題

トピック

2 次元配列を使用して単純な迷路を表します。0 はパスを表し、1 は障害物を表します。各ポイントで、マウスは東、南、西、北の 4 つの隣接ポイントに移動できます。マウスが迷路を歩く様子をシミュレートし、入口から出口までのパスを見つけるアルゴリズムを設計します。

図に示すように

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

アイデア

スタックを使用して、入口から出口までのマウスの経路を記録します。
特定のポイントに到達したら、そのポイントの左側をスタックにプッシュし、そのポイントの値を 1 に設定して、通過したことを示します。
到達可能な近くの 4 つのポイントのいずれかを選択し、そのポイントまで歩きます。
あるポイントに到達した後、隣接する 4 つのポイントに行かない場合は、行き止まりに達したことを意味します。このときは、スタックから撤退して 1 ステップ戻り、他のポイントを試す必要があります。
出口が見つかるまで手順 2、3、4 を繰り返します。

ソリューションコード

#!/use/bin/env python 
 
 # _*_ コーディング:utf-8 _*_ 
 
 initMaze() を定義します: 
 
 「」 「 」 
 
    : return : 迷路を初期化する
 
 「」 「 」 
 
    maze = [[0] * 7 for _ in range(5 + 2)] # リストの内包表記を使用して、迷路が壁に囲まれていることを確認するために 7*7 の 2 次元配列を作成します
 
    walls = [ # 壁の位置を記録する
 
        （１、３）、 
 
        （２、１）、（２、５）、 
 
        （３、３）、（３、４）、 
 
        (4, 2), # (4, 3), # ポイント (4, 3) も壁として設定されている場合、迷路全体を歩くことはできないため、空のリストが返されます。 
 
        （５、４） 
 
    ] 
 
 for i in range(7): # 迷路の周りに壁を設定する
 
        迷路[i][0] = 迷路[i][-1] = 1 
 
        迷路[0][i] = 迷路[-1][i] = 1 
 
 for i, j in walls: # すべての壁の点を 1 に設定する
 
        迷路[i][j] = 1 
 
迷路を戻る
 
 「」 「 」 
 
 [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] 
 
 「」 「 」 
 
定義パス(迷路、開始、終了): 
 
 「」 「 」 
 
    :param 迷路: 迷路
 
    :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 # マウスが出口を見つけたら
 
 di、djが[(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)) # 現在の位置をスタックに追加する
 
                壊す
 
 else : # すべてのポイントにアクセスできない場合
 
            stack.pop() # 1ステップ戻る
 
スタックを返す# 迷路を歩くことができない場合は、空のスタックを返す
 
 Maze = initMaze() # 迷路を初期化する
 
 result = path(maze=Maze, start=(1, 1), end =(5, 5)) # マウスは迷路の中を歩き始めます
 
印刷(結果) 
 
 # [(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 
 
 # _*_ コーディング:utf-8 _*_ 
 
演算子 = { # 演算子演算テーブル
 
 '+' : ラムダ op1, op2: op1 + op2, 
 
 '-' : ラムダ op1, op2: op1 - op2, 
 
 '*' : ラムダ op1, op2: op1 * op2, 
 
 '/' : ラムダ op1, op2: op1 / op2, 
 
 } 
 
 def evalPostfix(e): 
 
 「」 「 」 
 
    :param e: 接尾辞式
 
    : return : 通常、スタックの最初の要素は計算された値です。 
 
 「」 「 」 
 
    tokens = e.split() # 渡されたサフィックス式をリストに分割します
 
    スタック = [] 
 
 for token in tokens: # リスト内の要素を反復処理する
 
        if token.isdigit(): # 現在の要素が数値の場合
 
            stack.append( int (token)) # スタックに追加する
 
        elifトークンin operators.keys(): # 現在の要素が演算子の場合
 
            f = operators[token] # 演算子操作テーブル内の対応するラムダ式を取得します
 
            op2 = stack.pop() # 先入後出原則に従って、2番目の要素を最初にスタックからポップします
 
            op1 = stack.pop() # スタックから最初の要素を取り出す
 
            stack.append(f(op1, op2)) # 計算結果をスタックに格納する
 
 return stack.pop() # スタックの最初の要素を返します
 
結果 = evalPostfix( '2 3 4 * +' ) 
 
印刷(結果) 
 
 ＃14

ナップサック問題

トピック

10kgの荷物を収納できるバックパックがあります。現在、6つのアイテムがあります。

アイテム 1 + アイテム 5 など、バックパックを満たすことができるすべてのソリューションを検索するプログラムを作成します。

ソリューションコード

#!/use/bin/env python 
 
 # _*_ コーディング:utf-8 _*_ 
 
ナップサック(t, w)を定義します: 
 
 「」 「 」 
 
    :param t: バックパックの総容量
 
    :param w: アイテムの重量リスト
 
    ：戻る： 
 
 「」 「 」 
 
    n = len(w) # 選択できる項目の数
 
    stack = [] # スタックを作成する
 
    k = 0 # 現在選択されている項目のカーソル
 
    while スタックまたは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: # 解を求める
 
            印刷(スタック) 
 
        # フォールバックプロセス
 
        k = stack.pop() # 最後の項目を取り出す
 
        t += w[k] # バックパックの総容量にw[k]を加えた値
 
        k += 1 # 次の項目をロードする
 
ナップザック(10, [1, 8, 4, 3, 5, 2]) 
 
 「」 「 」 
 
 [0、2、3、5] 
 
 [0, 2, 4] 
 
 [1, 5] 
 
 [3, 4, 5] 
 
 「」 「 」