JavaScriptで括弧文字列のスコアを計算する方法

問題の概要

バランスの取れた角括弧（[ と ]）のみで構成された文字列 str を引数として受け取り、そのスコアを計算して返すJavaScript関数を作成する必要があります。

スコアの計算は、以下のルールに従います。

• [] のスコアは 1
• 2つのバランスの取れた括弧文字列 A と B を連結した AB のスコアは A + B
• バランスの取れた括弧文字列 A を囲んだ [A] のスコアは 2 × A

入出力例

例えば、関数への入力が次の場合：

入力

const str = '[][]';

出力

const output = 2;

この場合、[] が2つ並んでいるため、スコアは 1 + 1 = 2 となります。

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

この問題は、スタック（配列）を活用することで効率的に解けます。基本的な考え方は以下の通りです。

1. 文字列を先頭から1文字ずつ走査し、スタックに push していきます。
2. スタックの末尾が ] である間、pop を繰り返します。
3. 直前が [ であれば、空の括弧ペアなので 1 を push します。
4. そうでなければ、数値を取り出して合算し、[ を pop した上で、2 × 合計値 を push します。
5. 最後に、スタックに残ったすべての数値を合計すれば、それが文字列全体のスコアになります。

実装コード

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

const findScore = (str = '') => {
    const arr = []
    for(const char of str) {
       arr.push(char)
       while(arr[arr.length - 1] === ']') {
          arr.pop()
          if(arr[arr.length - 1] === '[') {
             arr.pop()
             arr.push(1)
          } else {
             let num = arr.pop()
             while(arr[arr.length - 1] >= 1) {
                num += arr.pop()
             }
            arr.pop()
            arr.push(2 * num)
          }
       }      
   }
   return arr.reduce((acc, a) => acc + a, 0)
};
console.log(findScore(str));

実行結果

2

処理の流れを詳しく見る

入力 '[][]' の場合、処理は以下のように進みます。

1. 1文字目の [ をスタックに push → スタック: ['[']
2. 2文字目の ] を push → 直後に while ループが発火。末尾の ] を pop すると直前は [ なので、両方を取り除いて 1 を push → スタック: [1]
3. 3文字目・4文字目も同様に処理され、1 がもう一つ push される → スタック: [1, 1]
4. 最終的に reduce で全要素を合計し、2 が返されます。

このアルゴリズムの時間計算量は O(n)、空間計算量も O(n) であり、括弧文字列の長さに対して線形で動作します。ネストされた括弧（例：[[]] → スコア 2）にも正しく対応できる汎用的な実装です。