数値表現で書かれているString(infix)を受け取ってlevel-order-traversalの配列に変換するプログラムを作りたいのですが。どうやって書いたらいいかさえもわかりません。さらに、Level-orderからPostfixとlevel-orderからprefixに画面に出力する方法も知りたいのですが、アドバイスをもしよかったらお願いします。
質問の補足として、
2*X/5+3*Y-4*Z-1 (infix)
をStringで受けたファンクションから
-/-*+*12X5*4Z 3Y (level order)
(空のノードと一番初めはスペースにしてます)
っという風に変えたいということです。
二分木は
....................-
.......... /....................-
.....*........+..........*..........1...
2..X.....5...*......4...Z................
................3..Y.........................
のようになっています。(ちょと解りづらくて申し訳ないですが.を抜かした部分が木になっています)
どなたかわかる方よろしくお願いします。
No.2ベストアンサー
- 回答日時:
大学レベルの課題だと思いますが、作成者のレベルが推し量れる良い課題だと思います。
で、アドバイスだけですが
1.ノードのクラスを設計する
(符号をどのように扱うか、レベル自体をノードの情報として保持するか)
2.Treeのクラスを設計する
(追加・削除・表示の機能を実装)
3.infixの内容を解析するプログラムの検討
(スタックを利用して、逆ポーランド表記に変換するのが楽かな)
4.スタックしたデータでノードのインスタンスを作成してTreeに追加
5.Treeの内容を表示
(ついでにPreorderやInorderなど別の巡回法も実装すれば+αの評価がもらえるかも)
二分木も逆ポーランドのプログラムもネットで多数Hitするので参考にすればよいでしょう。
返事が遅くなって申し訳ないです。
なんとか、先生の助けを借りて、終わらせる事ができました。
ChateauAresもとても参考になりました。
ありがとうございました。
No.1
- 回答日時:
>2*X/5+3*Y-4*Z-1 (infix)
>-/-*+*12X5*4Z 3Y (level order)
こうはならないと思うのだけど??
演算子の優先順位とかは通常の*/は+-より先に計算というものではないのでしょうか?
全部の演算子が等価だとすれば、手前から順になるべきだと思うし。
私の理解が間違っているのでしょうか?
どうしてこうなるのかアルゴリズムを補足して下さい。
でないとプログラムは書けません。
この回答への補足
すいません、間違えてました。。
問題は(2*X)/(5+3*Y)-(4*Z-1)
というのを前提としてました。
でもちょっとわかりづらいので、例を変えようと思います。
56+34*2-36*12/3+5*13-5*4+6 (infix)
の場合
+ - 6 + * - * 5 4 + * 5 13 56 * 36 / 34 2 12 3
(level order)
となると思いますが、また間違ってたらすいません。
>演算子の優先順位とかは通常の*/は+-より先に計算>というものではないのでしょうか?
はい、普通の計算の優先順位であっています。
そして、質問は、infixをStringで受け取り、level order の配列で返すという質問でした。
方法としては、演算子の優先順位順に演算子を前に持っていってその後に近くの数字を次に持ってくる!?のような方法で配列を並び替えればいいのでしょうか?
どういう方法で並び替えてよいのかわからなくて困っています。もし、わかるようでしたらアドバイスお願いします。
質問の内容がわからないようであったら、まだ補足します。間違いを指摘していただいてありがとうございました。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
関連するカテゴリからQ&Aを探す
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・人生のプチ美学を教えてください!!
- ・10秒目をつむったら…
- ・あなたの習慣について教えてください!!
- ・牛、豚、鶏、どれか一つ食べられなくなるとしたら?
- ・【大喜利】【投稿~9/18】 おとぎ話『桃太郎』の知られざるエピソード
- ・街中で見かけて「グッときた人」の思い出
- ・「一気に最後まで読んだ」本、教えて下さい!
- ・幼稚園時代「何組」でしたか?
- ・激凹みから立ち直る方法
- ・1つだけ過去を変えられるとしたら?
- ・【あるあるbot連動企画】あるあるbotに投稿したけど採用されなかったあるある募集
- ・【あるあるbot連動企画】フォロワー20万人のアカウントであなたのあるあるを披露してみませんか?
- ・映画のエンドロール観る派?観ない派?
- ・海外旅行から帰ってきたら、まず何を食べる?
- ・誕生日にもらった意外なもの
- ・天使と悪魔選手権
- ・ちょっと先の未来クイズ第2問
- ・【大喜利】【投稿~9/7】 ロボットの住む世界で流行ってる罰ゲームとは?
- ・推しミネラルウォーターはありますか?
- ・都道府県穴埋めゲーム
- ・この人頭いいなと思ったエピソード
- ・準・究極の選択
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
自作Androidアプリのデータ引き...
-
正規表現について質問です。 カ...
-
list の空は [] ってあわらすのに
-
プログラミングの問題です。大...
-
デバッグツールの具体例を教え...
-
「main メソッドを持つクラスが...
-
ゲーム開発の入門書を探しています
-
jdbcでinsert,delete,createをe...
-
session,requestはjspで未定義...
-
サーブレットをapacheで公開す...
-
下記のリストならno002が含まれ...
-
is this even a thing?
-
JAの支部?地域の農協のカード...
-
えハミルトン路と全域木のちが...
-
CSV出力を画面から選択したデー...
-
ショートカットキーについて
-
あんまりお料理しないのに台所...
-
質問です。 配列が100以上の場...
-
次のhtml・cssでspan内の文字を...
-
Jupyter notebookですわかりま...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
鍵盤アプリで、スマホの画面に...
-
アコーディオンメニューにする...
-
iText セル内での自動改行について
-
Aタグのhrefの値を取得したいの...
-
JTreeのドラッグアンドドロップ...
-
或る文字列の文字数が一定数以...
-
jtreeのノードを右クリックで選...
-
JTextAreaを改行コードを直接書...
-
Listでintの最大値を超える要素...
-
javaがわかりません。。。
-
配列による二分木
-
innerTextは標準化されているの...
-
addEventListener の第三引数の...
-
(再質問)エクセルのマクロボ...
-
collection型を引数にしたファ...
-
汎用機のJCLの入門書ありま...
-
ヘッダファイルimage.hとは?
-
コンソール画面のクリアの方法
-
timeSetEventに対するtimeKillE...
-
Progateの入力画面で使えるショ...
おすすめ情報