JavaScriptで括弧のバランスを取る：最小挿入回数を求めるアルゴリズム

問題の概要

「(」と「)」の2種類の文字のみで構成された文字列が与えられます。この文字列に対して、必要な回数だけ「(」または「)」を挿入して括弧のバランスを取る関数を作成します。

そして、その関数は文字列のバランスを取るために行った挿入の最小回数を返す必要があります。

例

たとえば、次のような文字列が与えられたとします。

const str = '()))';

この場合、出力は 2 になります。先頭に「((」を追加すれば文字列のバランスが取れるためです。

解決策：スタックを使ったアプローチ

この問題は、スタック（配列）を使うことで効率的に解決できます。考え方は以下のとおりです。

• 「(」が出現したらスタックにプッシュします。
• 「)」が出現したとき、スタックの末尾が「(」であればペアとしてポップ（取り除き）ます。
• スタックの末尾が「(」でない場合（スタックが空の場合を含む）は、対応する開き括弧が存在しないため、プレースホルダーとして「#」をプッシュします。

最終的にスタックに残った要素の数が、バランスを取るために必要な挿入回数と一致します。

実装コード

以下が実際のコードです。

const str = '()))';
const balanceParanthesis = str => {
    let paren = [];
    for (let i = 0; i < str.length; i++) {
        if (str[i] === "(") {
            paren.push(str[i]);
        } else if (str[i] === ")") {
            if (paren[paren.length - 1] === "("){
                paren.pop();
            } else {
                paren.push("#");
            };
        };
    }
    return paren.length;
}
console.log(balanceParanthesis(str));

コードの解説

この関数は、文字列を先頭から1文字ずつ走査します。開き括弧「(」はスタックに積まれ、閉じ括弧「)」が現れた際に直前の要素が「(」であればペアとして取り除かれます。対応する開き括弧がない場合は「#」をスタックに積むことで、後から挿入が必要な「(」の数をカウントできるようにしています。

ループが終了した時点でスタックに残っている要素は、未対応の「(」または挿入すべき「)」に相当するため、その長さを返すことで最小挿入回数が求まります。

実行結果

このコードをコンソールで実行すると、次の出力が得られます。

2

このアルゴリズムの計算量は、文字列を一度だけ走査するため O(n) であり、非常に効率的です。