JavaScriptで文字列内の括弧の対応関係を検証する方法

JavaScriptでは、開き括弧と閉じ括弧を含む可能性のある文字列を受け取り、すべての開き括弧に対して対応する閉じ括弧が存在するかどうかを判定する関数を実装する必要があります。括弧が正しく対応していれば関数は true を返し、そうでなければ false を返します。

要件の例

f('(hello (world))') = true
f('(hello (world)') = false

最初の文字列は括弧が正しく入れ子になっており対応しているため true となります。一方、2つ目の文字列は閉じ括弧が1つ不足しているため false になります。

アプローチ：カウンターを使った検証

この問題は、カウンター変数を使ったシンプルな手法で効率的に解決できます。具体的な手順は以下の通りです。

1. 文字列を1文字ずつ走査します。
2. 開き括弧「(」を見つけたらカウンターを+1し、閉じ括弧「)」を見つけたら-1します。
3. 処理の途中でカウンターが負の値になった場合、対応する開き括弧のない閉じ括弧が出現したことを意味するため、その時点で false を返します。
4. ループ終了後にカウンターが 0 であれば、すべての括弧が正しく対応しているため true を返します。

コード例

const str1 = '(hello (world))';
const str2 = '(hello (world)';
const validateBrackets = (str = '') => {
    const strArr = str.split('');
    let counter = 0;
    for (let i = 0, len = strArr.length; i < len; i++) {
       if (strArr[i] === "(") {
          counter++;
       }else if (strArr[i] === ")") {
          counter--;
       };
       if (counter < 0) {
          return false;
       };
    };
    if (counter === 0) {
       return true;
    };
    return false;
};
console.log(validateBrackets(str1));
console.log(validateBrackets(str2));

出力結果

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

true
false

コードのポイント

• split('') により、文字列を1文字ずつの配列に変換して扱いやすくしています。
• カウンターが負になった瞬間に即座に false を返すことで、「)(」のような閉じ括弧が先に現れる不正なパターンも正しく検出できます。
• このアルゴリズムの時間計算量は O(n)、空間計算量は O(n) であり、長い文字列でも高速に動作します。