JavaScriptで括弧の組み合わせが有効かどうかを判定する方法

問題の概要

文字列 str を引数として受け取り、その文字列に含まれるのが '('・')'・'{'・・'['・']' の6種類の括弧だけであるとき、その文字列が「有効」かどうかを判定するJavaScript関数を作成します。

有効な文字列の条件

入力文字列が有効とみなされるのは、以下の両方の条件を満たしている場合です。

• 開き括弧は、必ず同じ種類の閉じ括弧で閉じられていること。

• 開き括弧は、正しい順序で閉じられていること。

具体例

• "()" … 正しい組み合わせのため有効です。

• "()[]{}" … 複数種類の括弧が正しい順序で対応しているため有効です。

• "(]" … 開き括弧と閉じ括弧の種類が一致していないため無効です。

アルゴリズムのポイント：スタックを活用する

この種の問題は「スタック」を使うのが定石です。手順は以下のとおりです。

1. 開き括弧を見つけたら、スタックにプッシュします。

2. 閉じ括弧を見つけたら、スタックからポップした開き括弧と対応関係が一致するかを確認します。一致しなければ即座に false を返します。

3. ループ終了後にスタックが空であれば、すべての括弧が正しく対応しているため true を返します。

サンプルコード

const str = "()[]{}";
const isValid = (str = '') => {
    const map = new Map();
    map.set('{', '}');
    map.set('(', ')');
    map.set('[', ']');
    const b = [];
    for(let i = 0; i < str.length; i++){
        if(map.has(str.charAt(i))){
            b.push(str.charAt(i));
        } else {
            const pop = b.pop();
            if(map.get(pop) !== str.charAt(i)){
                return false;
            }
        }
    }
    return b.length === 0;
};
console.log(isValid(str));
console.log(isValid("(]"));

ここでは、Mapオブジェクトを使って開き括弧と閉じ括弧の対応表を定義し、配列 b をスタックとして利用しています。

実行結果

コンソールには次のように出力されます。

true
false

1つ目の出力 true は "()[]{}" が有効なことを示し、2つ目の出力 false は "(]" が無効なことを示しています。