逆ポーランド表記法とは？

逆ポーランド表記法の意味

演算子を被演算子の後ろに置く記法。括弧を使わずに演算順序を一意に表現でき、スタックを使えば左から順に読むだけで評価できる。

逆ポーランド表記法の具体例

「A＋B×(C－D)」は後置記法で「ABCD－×＋」。評価はスタックにオペランドを積み、演算子が来たら上位2つを取り出して計算し結果を積み直す。

逆ポーランド表記法は試験でどう引っ掛けられる？

前置記法（ポーランド記法）は演算子が前に来る。「逆」が付く方が後置であることを取り違えやすい。

逆ポーランド表記法と関連する用語

• スタック
• 構文解析

逆ポーランド表記法が出た過去問

• 逆ポーランド表記法で表された式を評価する場合、途中の結果を格納するためのスタックを用意し、式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき…

  正解：C 演算子 D

  要点：RPNは演算子で上位2つをポップ、後から出た方が左項

  逆ポーランド表記法の評価では、演算子が現れるとスタックから2つ取り出して演算し、結果を積み直します。先に取り出されるのはスタックの最上位である D で、次が C です。二項演算では先に取り出した値が右側の被演算数になるため、中置表記に直すと C 演算子 D となります。引き算や割り算のように順序が結果に影響する演算では、この向きの取り違えが誤答に直結します。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問3（IPA）

• 式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）