BFE.devでのAI解答例 - JavaScript コーディング問題
173. 文字列を解凍する

解法:

再帰的に解凍することができます。まず、文字列を最初から最後までスキャンし、数字、開き括弧、閉じ括弧、および文字符号の各種類の文字を識別して、それらをキューに格納します。すべての文字が処理されたら、次のように再帰的に解凍します

• キューが空になるまで次のステップを繰り返します
• キューの先頭の文字が文字符号の場合は、出力に追加し、キューからポップします
• キューの先頭が数字の場合は、その数だけ数字を読み込み、開き括弧を読み込みます。その後、再帰的に解凍して、キューから読み込んだ分の要素を除去します。
• キューの先頭が開き括弧である場合、閉じ括弧が見つかるまで再帰的に解凍します。閉じ括弧以降の部分を再度処理し、キューから読み込んだ分の要素を除外します。

最後に、得られた出力を返します。以下が完全なコードです:

function uncompress(str) {
  let queue = [];
  for (let i = 0; i < str.length; i++) {
    const char = str.charAt(i);
    if (!isNaN(char)) {
      let num = char;
      while (!isNaN(str.charAt(i + 1))) {
        num += str.charAt(i + 1);
        i++;
      }
      queue.push(parseInt(num));
    } else {
      queue.push(char);
    }
  }

  function recurse(queue) {
    let result = "";
    while (queue.length > 0) {
      const current = queue.shift();
      if (typeof current === "string") {
        result += current;
      } else if (typeof current === "number") {
        const subQueue = [];
        const openParenCount = 1;
        while (openParenCount > 0) {
          const next = queue.shift();
          if (next === "(") {
            openParenCount++;
          } else if (next === ")") {
            openParenCount--;
          } else {
            subQueue.push(next);
          }
        }
        result += recurse(subQueue).repeat(current)
      }
    }
    return result;
  }

  return recurse(queue);
}

例えば、

uncompress('3(ab2(c))') // 'abccabccabcc'

この場合、最初にキューに次の要素が格納されます。

[3, "(", "a", "b", 2, "(", "c", ")", ")"]

その後、再帰的に解凍して、出力が得られます。

uncompress(['3', '(', 'a', 'b', '2', '(', 'c', ')', ')'])
  -> 'a' + 'b' + uncompress(['2', '(', 'c', ')']) * 3
  -> 'a' + 'b' + ('c' + 'c') * 3
  -> 'a' + 'b' + 'cc' + 'cc' + 'cc'
  -> 'abccabccabcc'

よって、出力は 'abccabccabcc' になります。