質問: ``` ['(', '*', '(', '+', 2, 4, ')', 3, ')'] ``` 上のような配列ひとつを引数にとり、 ``` ['*', ['+', 2, 4], 3] ``` このような配列に変換して返す関数を定義したいのですが、 渡された配列の要素を順に検証していき `'('` と `')'` に反応して再帰処理を行い 配列の配列を生成していくコードがなかなか書けません。 定義コードをお教えいただくか、効率的なアルゴリズムの説明をしていただけると嬉しいです。 追記:常に要素は()で括られているものとします。
回答: なかなか興味深い課題なので自分で書いてみました。 ``` function f(input){ input = input.slice(1, -1); // 最初と最後の括弧は固定なので切り捨てる function g(ary){ var elm; while(input.length){ elm = input.shift(); // 先頭の要素を取得。同時にその要素をinputから捨てる if(elm === "(") ary.push(g([])); // もし "(" なら再帰的に新しい配列を挿入する else if(elm === ")") break; // もし ")" なら再帰的な配列挿入は終了する else ary.push(elm); // それ以外なら現在の配列に挿入する } return ary; } return g([]); } f(['(', '*', '(', '+', 2, 4, ')', 3, ')']); // ["*",["+",2,4],3] f("(((a)))".split("")); // [[["a"]]] f("((a)((aa)(a)(a))(aa))".split("")); // [["a"],[["a","a"],["a"],["a"]],["a","a"]] ``` ただ、上のコードではエラーチェックをしていません。 エラーチェックもするならこんな感じにします。 ``` function f(input){ if(!Array.isArray(input) || input[0] != "(" || input[input.length-1] != ")") throw new Error; // inputが配列かどうか、最初と最後の要素が正しいかどうかをチェックする input = input.slice(1, -1); function g(ary, top){ var elm; while(input.length){ elm = input.shift(); if(elm === "(") ary.push(g([], false)); else if(elm === ")"){ if(top) throw new Error; // 最上位の配列に挿入中なのに、")" が来るのはおかしい else break; } else ary.push(elm); } if(!top && elm != ")" && input.length == 0) throw new Error; // 下位の配列に挿入中なのに、inputの要素がなくなるのはおかしい return ary; } return g([], true); } f(['(', '*', '(', '+', 2, 4, ')', 3, ')']); // ["*",["+",2,4],3] f(['(', '*', '(', '+', 2, 4, ')', 3]); // エラー。最後の括弧がない f(['(', '*', '(', '+', 2, 4, 3, ')']); // エラー。閉じてない括弧がある f(['(', '*', '+', 2, 4, ')', 3, ')']); // エラー。括弧が開いていないのに閉じている ``` 効率的なアルゴリズムかどうかは自信がありませんが、参考にしていただければと思います。