はてなキーワード: 木構造とは
いや、ごめん。再帰というのは、木構造による再帰、でも、Switchによる再帰でも同じ。そのアルゴリズムで Call命令を使うのか?って事。
あとCでもswitchが嫌で かつ 再帰によるCall命令が許容されるなら、Treeに関数ポインタ持たせて、関数ポインタで評価関数呼び出せばいいじゃん。
単純に要素だけ書けば
struct leaf{
int (*eval)(leaf *);
};
でよかろ 値を入れるときにAddなら eval_add sub なら eval_sub を呼び出せばいい (データー構造と アルゴリズムの分離はCでもできる。)
どっちみち C++でも、子どものevalを親が呼ぶ 時点で call が呼ばれているから、それ再帰。
というかC++自体が こういう vtableのC実装から 生まれている実装なので C++でできて、Cで実装できないって、テンプレとかそういうのぐらいだから。
究極的にはvtalbe実装すればCでもできる。つか、昔のCのコードなんてVtableを第1引数として渡すようなものばっかだろ。
何が言いたいかというと、別に データー構造と アルゴリズムの分離は関数ポインタとVtableの実装によりCでもできる。
switchテーブルが巨大化するのも 小さいクラスが無数にあるのも どっちも同じ事だよ。
Swithならよい Classならよいってことはない。
「Cならswitchテーブルを使った再帰関数で実現する必要がある」に対するレスなんだろうけど、飽くまでも「C以外の、継承とオーバーライドの機能がある言語では例題とほぼ同じ形で実装できるのに対してその機能がない言語では『関数内でswitchをして値ごとにdispatch、その後更に再帰』という原始的かつ全てのロジックを詰め込むせいでひとつの関数の行数が膨大になる問題を孕んでいる」という意味しか持たない。
確かにTopCoderで再帰を使ったら撃墜される可能性がある事には同意だけど、今回の例ではプロコンの外側での事であってスタックがオーバーフローしたなら例外をキャッチして後処理を行えば良い。
更に
バイナリツリーを自前で構築して式を表現する例題(expression tree)と、set and mapは用途が違う。
setとmapは本来、順序が定義できる要素をキーにしてそれそのものを保持するか、或いはそれに伴う値を結びつけて保持しておくもの。
例題のexpression treeの構造は「(必ずしもオペランドがふたつとは限らない)式の木を表現して、オーバーライドされたevalで式全体の評価を行う」もの。
は成り立たない主張であるし、
(C言語等のOOPが導入される前の言語で)綺麗に書く事ができないと問題を提供する側がそもそも「綺麗な解を前提とした問題」を出せない。