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

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

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

サンプルコードでは、pairsというDictで閉じ括弧に対応する開き括弧を管理し、Char[]という型指定付きの配列をスタックとして使い、開き括弧が来たらpush!()で積み、閉じ括弧が来たらスタックの一番上と一致するか確認しています。

初心者がよくつまずくのが、括弧の種類が複数ある場合(丸括弧・角括弧・波括弧が混在する場合)の対応関係です。単に開閉の数を数えるだけでは不十分で、正しい順序でネストしているかまで確認する必要があります。

コンパイラが構文を解析するときにも似た仕組みが使われている、応用範囲の広い考え方です。

📖 お手本コード

function is_balanced(str)
    stack = Char[]
    pairs = Dict(')' => '(', ']' => '[', '}' => '{')
    for ch in str
        if ch in "([{"
            push!(stack, ch)
        elseif ch in ")]}"
            if isempty(stack) || pop!(stack) != pairs[ch]
                return false
            end
        end
    end
    return isempty(stack)
end

println(is_balanced("(a[b]{c})"))
println(is_balanced("(a[b)]"))

✍️ あなたのコード

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

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

🎯

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