【JavaScript】配列操作について

Question

['(', '*', '(', '+', 2, 4, ')', 3, ')']

上のような配列ひとつを引数にとり、

['*', ['+', 2, 4], 3]

このような配列に変換して返す関数を定義したいのですが、
渡された配列の要素を順に検証していき '(' と ')' に反応して再帰処理を行い
配列の配列を生成していくコードがなかなか書けません。

定義コードをお教えいただくか、効率的なアルゴリズムの説明をしていただけると嬉しいです。

追記：常に要素は()で括られているものとします。

Comments

[think49]

()で括られていない要素はどうなるのでしょうか。

[0918Nobita]

常に要素は()で括られているものとします。説明不足ですみません

Answer 1

なかなか興味深い課題なので自分で書いてみました。

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, ')']); // エラー。括弧が開いていないのに閉じている

効率的なアルゴリズムかどうかは自信がありませんが、参考にしていただければと思います。

Comments

[0918Nobita]

なるほど、与えられた配列からshiftで要素を切り出しながら新たに配列を生成していくんですね。自分は与えられた配列を直接操作して目的の状態に遷移させることばかり考えていたのですごく勉強になりました。ありがとうございます！(この関数はテキストエリアでの入力を変換するためのもので、S式で記述する自作言語のインタプリタで利用するつもりです)

Answer 2

でけた！ (ことにして)　

var arr = ['(', '*', '(', '+', 2, 4, ')', 3, ')'];
var str = '[';
arr.map(v => v === '(' ? '[' : v === ')' ? ']' : isNaN(v) ? `"${v}"` : v).reduce((a, b, i) => {
  str += (a === '[' || b === ']' ? '' : ',') + b;
  return b;
});
var result = JSON.parse(str);
console.log(result);    

これ以上は無理！！ (じゃないのはわかってる)
再帰してない・・・・ゴメンこの回答は無し。