逆ポーランド記法（後置記法）と式の評価とは？

逆ポーランド記法（後置記法）と式の評価の意味

演算子を被演算子の後ろに置く記法で、括弧なしで演算順序を一意に表せる。スタックを使い、値が来たら積み、演算子が来たら2つ取り出して結果を積むだけで評価できるため、コンパイラの式評価や仮想機械の命令列で使われる。応用情報では中置記法との相互変換と評価結果の計算が定番。

逆ポーランド記法（後置記法）と式の評価の具体例

中置の「(3+4)×5−6」は後置で「3 4 + 5 × 6 −」となる。評価はスタックに3,4を積み「+」で7、5を積み「×」で35、6を積み「−」で29。二分木で表すと後行順（左・右・根）の巡回結果が後置記法、行きがけ順が前置記法に一致する。

逆ポーランド記法（後置記法）と式の評価は試験でどう引っ掛けられる？

減算・除算では取り出す順序が逆になる点。「6 2 −」は 6−2 であって 2−6 ではないため、スタックから先に出た値を右辺、後に出た値を左辺として扱う必要がある。

逆ポーランド記法（後置記法）と式の評価と関連する用語

• スタックとキュー
• 木の巡回（走査）
• コンパイラの構成（字句解析・構文解析・最適化）

逆ポーランド記法（後置記法）と式の評価が出た過去問

• 式A＋B×Cの逆ポーランド表記法による表現として、適切なものはどれか。

  正解：ABC×＋

  要点：後置記法は演算子を被演算数の後ろに置いて書く

  逆ポーランド表記法（後置記法）は、演算子を2つの被演算数の後ろに置く書き方である。A＋B×Cは乗算が先なのでB C ×が先に確定し、その結果とAを加算するのでA（BC×）＋という並びになる。まとめるとABC×＋である。

  出典：令和2年度 10月 応用情報技術者試験 午前 問3（IPA）

• 逆ポーランド表記法（後置記法）で表現されている式ABCD-×+において、A=16、B=8、C=4、D=2のときの演算結果はどれか。逆ポーランド表記法による式AB…

  正解：32

  要点：後置記法は演算子の直前2項に適用して順に評価する

  後置記法は、オペランドが並んだ直後の演算子をその直前2項に適用して評価する。ABCD-×+では、まずC-D=4-2=2、次にB×2=8×2=16、最後にA+16=16+16=32となる。よって演算結果は32である。

  出典：令和5年度 秋期 応用情報技術者試験 午前 問3（IPA）

• 式A＋B×Cの逆ポーランド表記法による表現として、適切なものはどれか。

  正解：ABC×＋

  要点：後置記法は演算子を被演算子の後ろに置き、優先順位を並び順で表す

  逆ポーランド表記法（後置記法）では、演算子を2つの被演算子の後ろに置く。A＋B×Cは乗算が優先なのでまずB×Cを「BC×」と書き、その結果とAを加算するので「A」「BC×」「＋」と並べて「ABC×＋」となる。演算子の位置と優先順位の反映が判断の要点である。

  出典：令和6年度 秋期 応用情報技術者試験 午前 問3（IPA）