括弧の対応をチェックしよう(スタックの応用)

このレッスンでは、スタックを応用して括弧の対応をチェックするアルゴリズムを学び、データ構造の実践的な使い方を理解することを目標にします。「PHP 括弧対応チェック」で調べている方向けです。

スタック(後入れ先出し)を使うと、(や[のような開き括弧を積んでおき、閉じ括弧が来るたびに一番上と対応しているか確認する、という方法で括弧の対応チェックができます。

サンプルコードでは、$stackという配列をスタックとして使い、開き括弧のときはarray_push()、閉じ括弧のときはarray_pop()で取り出した値が正しいペアかどうかを$pairsという連想配列で確認しています。

初心者がよくつまずくのが、対応する括弧の種類が違う場合(閉じ括弧の種類が合わない場合)の判定です。単に開き括弧と閉じ括弧の数が一致しているだけでは不十分で、それぞれの種類が正しいペアになっているかまで確認する必要がある点が、このアルゴリズムのポイントです。

エディタの入力補完やコードのシンタックスチェックの裏側でも、似た考え方が使われています。HTMLタグの開閉タグが正しく対応しているかをチェックする、似た仕組みのツールもたくさん存在します。

📖 お手本コード

<?php
function isBalanced($str) {
    $stack = [];
    $pairs = [")" => "(", "]" => "[", "}" => "{"];
    for ($i = 0; $i < strlen($str); $i++) {
        $ch = $str[$i];
        if (in_array($ch, ["(", "[", "{"])) {
            array_push($stack, $ch);
        } elseif (in_array($ch, [")", "]", "}"])) {
            if (empty($stack) || array_pop($stack) !== $pairs[$ch]) {
                return false;
            }
        }
    }
    return empty($stack);
}

var_dump(isBalanced("(a[b]{c})"));
var_dump(isBalanced("(a[b)]"));

✍️ あなたのコード

コードを書いたら「実行する」を押してください

🧪 このサイトではPHPを直接コンパイル・実行できないため、お手本コードと同じ内容を入力できたかをその場で判定します(採点はブラウザ内だけで行われ、どこにも送信されません)。

🎯

ここまでできればゴール達成!
コード中のカッコの対応が取れているかをチェックする、簡単なツールが作れるようになります。