Python でスタックを使用する方法

2年 ago
蓮, 翼
1 minute

Pythonでは、スタックの機能はリストを使用して実現できます。スタックは後入れ先出し(LIFO)のデータ構造で、スタックの一端でのみ挿入と削除の操作が許可されています。

リストをスタックとして使用する場合の例を以下に示します。

  1. スタックとして空のリストを作成: stack = []
  2. スタックに要素を入れる（プッシュ）：リストのappend()メソッドを使用して、スタックの最後に要素を追加する。例えば：stack.append(1)
  3. スタックから要素を削除する（ポップ）：リストのpop()メソッドを使用して、スタックの最上部の要素を削除して返します。例：element = stack.pop()
  4. スタックの先頭の要素を取得しますが、削除しません。リストの[-1]インデックスを使用して先頭の要素にアクセスできます。例えば: top_element = stack[-1]
  5. If not len(stack): # 判定スタックが空かどうか：リストの長さで判定
  6. スタック内の要素数を取得します: リストの len() 関数を使用します。例: size = len(stack)

括弧のマッチングを調べる、スタックを使ったサンプルプログラムです。

def is_valid_parentheses(s):
    stack = []
    parentheses = {'(': ')', '[': ']', '{': '}'}
    for char in s:
        if char in parentheses.keys():
            stack.append(char)  # 左括号入栈
        elif char in parentheses.values():
            if not stack or parentheses[stack.pop()] != char:
                return False  # 右括号不匹配或栈为空
    return not stack  # 栈为空表示括号匹配

s = "({[]})"
if is_valid_parentheses(s):
    print("括号匹配")
else:
    print("括号不匹配")

実行結果は「括弧が合っている」となる。

bannerAds