二分木について

以下の図式を２分木にしようと思っているのですが、
こつとかありましたら教えてください。
私は、以下のように造ればいいかなと思いますが、
イメージがはっきりしません。
(1+2)*3+(4+(5+6)*3)*2+1
-＞
Node1=(1+2)
Node1*3+(4+(5+6)*3)*2+1
Node2=Node1*3
Node2+(4+(5+6)*3)*2+1
Node3=(5+6)
Node2+(4+Node3*3)*2+1
・・・
です。
しかし、こんな方法で上手く作れるのかわかりません。
これだと、単純に左から右に演算子の優先順位を見て
/*がスタックにあると+-はおいておいて/*を先に出す。
）があれば、前の(まで演算子をスタックから取り出していくという方法のほうがよい気がします。

(1+2)*3+(4+(5+6)*3)*2+1
↓

................|-----+---------|...
................|...............|...
........|-------+---------|.....1...
........|.................|.........
..|-----*---|......|------*------|..
..|.........|......|.............|..
|-+-|.......3..|---+---|.........2..
|...|..........|.......|............
1...2..........4...|---*---|........
...................|.......|........
...............|---+---|...3........
...............|.......|............
...............5.......6............
（メモ帳でこぴぺしてください。）
12+3*456+3*+2*+1+

No.2 ベストアンサー 回答者： rabbit_cat 回答日時： 2005/07/16 03:02

普通の、中置記法から逆ポーランド記法への、変換法が載っているページがいくつかあると思うので、

見てみるとよいと思うのですが、LALR1文法と思ってスタックを使って変換すると、実はカッコの処理もたいして大変ではなかったりします。
頭いい方法ですね。

この回答への補足

とりあえずできました。
ノードの情報を増やしました。括弧に対応するためです。
struct NODE
{
NODE *Parent;
NODE *Left;
NODE *Right;
NODE *xArrayNext;
NODE *xArrayPrev;
char Code;
int Priority;
int StringCount;//usedebug
};
括弧なしの四則演算は簡単でした。
xArrayNext、xArrayPrevは、
((1+2*3)*(5-4))
内の一文字をそれぞれ順番に格納していき、
ある一文字の次のノード、前のノードです。
一番深い括弧の中のノードをまずツリー化して、
得られたトップノードのxArrayNext、xArrayPrevを括弧の前後にくっつけて、Priorityを（と同じにする。
そして、再計算（繰り返し、）しました。
ありがとうございました。

補足日時：2005/07/19 20:21

この回答へのお礼

一応できたつもりでしたが、
重大な論理エラーがありました。
括弧の内部をツリー化して、その外枠の演算子とノード化するときに、
その大内の括弧は数値のように振舞わないといけないことが解りました。
ご報告いたします。
このプログラムは、現在修正中です。

お礼日時：2005/07/20 23:01

No.1 回答者： rabbit_cat 回答日時： 2005/07/12 05:26

仰るとおり、普通はスタック（＋１文字先読み）を使って処理します。

「逆ポーランド記法 変換 スタック」
とかで検索すれば、大量に情報が出てくるかと。

他の方法でもがんばれば出来るかもしれませんが、スタックを使う処理より早くできるとは思えません。

この回答への補足

ありがとうございました。
今は、とりあえず、
struct NODE
{
NODE *Left;
NODE *Right;
NODE *Parent;
char Code;
int Cnt;
};
という構造体を式の長さの数だけ作成して、
Codeのところに、「1」「2」「+」「*」などを順番に格納しています。
肝心なのは、+-*/演算子なのでそれを連結していき、
あまったところへ、数値文字を連結していくというやり方で作成中です。()についてはまだ考慮に入れていません。
前途多難ですが、何とかやってみようと思います。

補足日時：2005/07/14 12:46