括弧の対応確認に使うスタック
スタックで括弧の対応を検証します
「括弧の対応確認に使うスタック」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
後入れ先出し
スタックは、皿を積む場合と同じように、最後に追加した要素を最初に取り出す構造です。🍽️
Python のリストはスタックになる
Python では専用のクラスは必要ありません。通常のlistが、コンテストで使える高速な既製のスタックとしてそのまま機能します。
stack = []append でプッシュする
スタックの一番上に要素を追加するには append を呼び出します。値は O(1) 時間でリストの末尾に追加されます。
stack.append('(')
stack.append('[')一番上からポップする
インデックスを指定せずに pop を呼び出すと、最後の要素、つまりスタックに最も新しくプッシュされた要素が削除されて返されます。
top = stack.pop() # removes '['削除せずに先頭を見る
一番上の要素を取り出さずに確認するには、stack[-1] を読み取ります。ポップするか決める前に確認できて便利です。
if stack:
top = stack[-1]必ず空か確認する
空のスタックからポップするとエラーが発生します。解答がクラッシュしないよう、すべての pop の前に if stack で確認してください。
括弧対応の考え方
括弧はきれいに入れ子になるため、スタックが適しています。すべての開き括弧をプッシュし、閉じ括弧はスタックの先頭と対応させます。
閉じ括弧を開き括弧に対応付ける
各閉じ括弧と、それが期待する開き括弧を対応付ける小さな辞書を用意すると、確認処理を簡潔にできます。
pairs = {')': '(', ']': '[', '}': '{'}走査して判定する
文字列を一度走査します。開き括弧をプッシュし、閉じ括弧が現れたら、pairs マップを使ってポップした先頭と比較します。
for c in s:
if c in pairs.values():
stack.append(c)不一致なら無効
ポップした開き括弧が一致しない場合や、必要なときにスタックが空の場合、その文字列はすぐに無効と判断できます。
elif not stack or stack.pop() != pairs[c]:
return False最後にスタックが空であること
走査後も開き括弧が残っていれば、閉じられていない括弧があります。最後にスタックが空の場合に限り、文字列は有効です。
return not stack確認問題
スタックを使って括弧を検証しています。最後までスタックが空でない場合、何を意味するでしょうか。
まとめ：スタックで括弧を扱う
リストをスタックとして使い、開き括弧をプッシュし、閉じ括弧でポップし、最後にスタックが空なら括弧が対応していることを学びました。よくできました！🎉
よくある質問
「括弧の対応確認に使うスタック」レッスンは無料ですか？
はい。「括弧の対応確認に使うスタック」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「括弧の対応確認に使うスタック」で何を学びますか？
スタックで括弧の対応を検証します ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「括弧の対応確認に使うスタック」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。