基礎科目・情報・アルゴリズム
スタックと木・逆ポーランド
6問H26・H27・H30・R1・R3
スタックの出し入れ、二分探索木の作り方、式を木にして逆ポーランド記法に直す問題が出ます。
よく出る形
- 空のスタックに PUSH と POP を順に行い，最後に取り出される値を答える
- 二分探索木と同じ形になるキーの登録順を選ぶ
- 中置記法の式（ふつうの式）を逆ポーランド記法（後置記法）に直す。算術木が表す式を選ぶ
- スタック・逆ポーランド・二分探索木が入れ替わって出る。同じ型どうしは操作列や式だけが替わる
覚えること
- スタック：後から入れたものを先に出す（後入れ先出し，LIFO）。PUSH は上に積む，POP は上から取る
- キュー：先に入れたものを先に出す（先入れ先出し，FIFO）
- 二分探索木：どの節でも，左の子孫は小さいキー，右の子孫は大きいキー。キーは根から「小さければ左，大きければ右」へ進めて空いた場所に置く
- 同じ形の木になるには，親のキーを子のキーより先に登録する必要がある
- 逆ポーランド記法は，演算子を2つの数の後ろに書く（A＋B → AB＋）。かっこが要らない
- 式の木を「左の部分木 → 右の部分木 → 節」の順にたどると逆ポーランド記法になる
- × と ÷ は ＋ と − より先に計算する
- 木のたどり方：先行順（節 → 左 → 右），中間順（左 → 節 → 右），後行順（左 → 右 → 節）
- 二分探索木を中間順でたどると，キーが小さい順に並ぶ
- 逆ポーランド記法の計算：数は積み，演算子が来たら上の2つを取り出して計算し結果を積む。引き算・割り算は「下の数 演算子 上の数」の順
解き方
- スタックは中身を「左が底，右が上」として1手ずつ書き出す
- 例：PUSH1，PUSH2，PUSH3，PUSH4，POP，POP，PUSH5，POP，POP → [1，2，3，4] → 4と3を出す → [1，2，5] → 5と2を出す。最後は 2
- 逆ポーランドに直すときは，最後に計算する演算子を木の根にして，左右に分けていく
- 例：(A＋B÷C)×(D−F) は，根が ×，左が A＋(B÷C)，右が D−F。B÷C → BC÷，左全体 → ABC÷＋，右 → DF−，まとめて ABC÷＋DF−×
- 確かめは，左から読んで演算子が来たら直前の2つで計算し，元の式に戻るか見る
- 二分探索木は，登録順に1つずつ根から置き場所をたどって木を書き，それから先行順などでたどる
ひっかけ
- 演算子を前に書く「ポーランド記法（前置記法）」の選択肢がまぎれている
- A＋B÷C を AB＋C÷ としない（(A＋B)÷C の意味になる）
- 引き算・割り算の順番を逆にしない（先に積んだ数から，後に積んだ数を引く・割る）
- 登録順をそのまま並べた選択肢や，中間順・後行順の並びがまぎれている
このテーマの過去問（このサイトに解説がある 3問）
平成に出た同じテーマ（3問）
このサイトにはまだ解説がありません。年度と題だけです。
- 平成30年度逆ポーランド記法への変換
- 平成27年度算術木（2分木）
- 平成26年度スタックのPUSH・POP