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' になります。