最終更新日:2026年10月18日
fe fe-technology algorithm
まず結論
逆ポーランド表記法とは、演算子を、計算する対象の後ろに置く表記法です。
基本情報技術者試験では、次の3つの読み方を使い分けます。
普通の式から変換する
→ 内側の計算から「左・右・演算子」に置き換える
普通の式へ戻す
→ 「値・値・演算子」を1つの式にまとめる
スタックで処理する
→ 値はpush
→ 演算子は2個popして計算し、結果をpush
普通の式から変換するときは、演算子だけを右へ移動するのではなく、計算順に1つずつ「かたまり」へ変換するのがポイントです。
例えば、
A + B
→ AB+
です。
最大スタック深さを問われた場合は、処理中に同時に積まれている値の最大個数を数えます。
直感的な説明
普通の式では、演算子は値の間にあります。
A + B
逆ポーランド表記法では、演算子を後ろに置きます。
A B +
つまり、
値 値 演算子
→ その2つの値を計算する
と読みます。
例えば、AB+ は (A+B)、AB- は (A-B) です。
逆ポーランド表記では計算順序が式の並びに含まれるため、括弧や演算子の優先順位を使わずに式を評価できます。
さらに、スタックを使うと処理を機械的に追えます。
値が来た
→ 積む
演算子が来た
→ 上から2個取り出して計算
→ 結果を積む
スタックのLIFOやpush・popを先に復習したい場合は、スタックとは?を確認すると理解しやすくなります。
定義・仕組み
逆ポーランド表記法は、演算子を被演算子の後ろに書く表記法で、後置表記法(postfix notation)とも呼ばれます。
| 表記 | 例 | 意味 |
|---|---|---|
| 中置表記 | A+B | 普通の式。演算子が間にある |
| 後置表記 | AB+ | 逆ポーランド表記法。演算子が後ろにある |
| 前置表記 | +AB | ポーランド表記法。演算子が前にある |
普通の式へ戻す
例えば、
XY-Z*
を考えます。
まず、XY- を1つにまとめます。
XY-
→ (X-Y)
残りは、
(X-Y) Z *
なので、
(X-Y) * Z
となります。
複雑な式は、括弧の内側から順に変換する
括弧が複数ある式や分数を含む式は、式全体を一気に変換しようとすると混乱しやすくなります。
FEでは、普通に計算するときと同じ順番で、内側から1つずつ逆ポーランド表記へ変換すると安定します。
例えば、
(A+B)×(C-D)
──────────
E+F
を考えます。
まず、括弧の中を変換します。
A+B
→ AB+
C-D
→ CD-
E+F
→ EF+
次に、分子の掛け算を変換します。
(A+B)×(C-D)
→ AB+CD-×
最後に、分子を分母で割ります。
AB+CD-×EF+÷
このように、
① 括弧の中
② 乗算・除算
③ 外側の演算
の順に、変換済みの部分を1つのかたまりとして扱うのがポイントです。
3段階で見る:内側から「かたまり」にする
例えば、次の式を変換します。
a + (b × (c - d))
図で確認:内側から1つずつ後置表記へ
変換した部分は、次の段階では「1つの値」のように扱います。
c - d↓
cd-
b × (cd-)↓
bcd-×
a + (bcd-×)↓
abcd-×+
abcd-×+
括弧は書かなくなりますが、括弧が示していた計算順は演算子の位置として残ります。
見るポイント:「括弧を消す」ではなく、「計算済みの部分を1つのかたまりへ置き換える」と考えます。
JavaScriptで動かすよりも、このテーマでは変換順を3段階で固定して見せる静的な図の方が、操作を増やさず本質を確認しやすいため、ここではCSSだけで図解しています。
スタックで計算する
逆ポーランド表記をスタックで処理するときの基本ルールは次のとおりです。
| 読んだもの | 処理 |
|---|---|
| 値・変数 | スタックへpush |
| 演算子 | 上から2個popして演算し、結果をpush |
例えば、
ab+c+
なら、
| 記号 | 処理後のスタック |
|---|---|
| a | [a] |
| b | [a, b] |
| + | [a+b] |
| c | [a+b, c] |
| + | [a+b+c] |
となります。
演算子を1個処理すると、
2個pop
↓
計算
↓
結果を1個push
なので、スタックの深さは結果として1減ります。
減算・除算は順番に注意
加算や乗算では順序を入れ替えても結果は同じですが、減算や除算では違います。
AB-
→ A-B
AB÷
→ A÷B
スタックでは、先にpopした値が右側、次にpopした値が左側になります。
公式の出題範囲やシラバスは、IPA:基本情報技術者試験から確認できます。
科目Aでどう出る?
科目Aでは、主に次のような形で出題されます。
- 逆ポーランド表記を普通の式に戻す
- 普通の式を逆ポーランド表記にする
- スタックの途中状態を求める
- 必要な最大スタック深さを求める
普通の式から変換するときの判断手順
選択肢から正しい後置表記を選ぶときは、次の順に見ると安定します。
1. いちばん内側の括弧、または優先順位の高い演算を探す
2. 「左の値 右の値 演算子」の順へ変換する
3. 変換済みの部分を1つのかたまりとして扱う
4. 外側の演算へ進む
例えば、
p + (q × (r - s))
なら、
r - s
→ rs-
q × (r - s)
→ qrs-×
p + ...
→ pqrs-×+
となります。
演算子を見つけるたびに右端へ移すのではなく、先に計算される部分から順に完成させるのが判断基準です。
最大スタック深さとは
最大スタック深さは、処理途中でスタックへ同時に積まれた値の最大個数です。
例えば、
abcd+++
を処理すると、最初に4つの値をすべて積みます。
a → [a] 深さ1
b → [a, b] 深さ2
c → [a, b, c] 深さ3
d → [a, b, c, d] 深さ4
+ → [a, b, c+d] 深さ3
+ → [a, b+c+d] 深さ2
+ → [a+b+c+d] 深さ1
したがって、最大深さは4です。
一方、
ab+c+d+
なら、値を2個積むたびに途中計算できます。
a → [a] 深さ1
b → [a, b] 深さ2
+ → [a+b] 深さ1
c → [a+b, c] 深さ2
+ → [a+b+c] 深さ1
d → [a+b+c, d] 深さ2
+ → [a+b+c+d] 深さ1
最大深さは2です。
どちらも加算だけなら最終結果は同じですが、必要なスタックの深さは異なります。
操作して理解する:最大スタック深さ
スタックの深さは、積まれている値の個数(図の高さ)です。最後に1個になるかどうかではなく、処理途中の最大値を見ます。
次の図は、例として a=2、b=3、c=4、d=5 を使います。「次へ」を押すと、実際の計算結果と、スタックの高さが1記号ずつ変わります。
逆ポーランド表記を1文字ずつ実行する
同じ合計14でも、計算する順番によって最大深さが変わります。
開始前です。「次へ」でaを積みます。
見るポイント:値なら1個増える。+なら2個取り出して結果を1個積むので、深さは1減る。最終深さと最大深さは別です。
最大深さを小さくする判断基準
試験では、次の傾向が使えます。
値を先にたくさん並べる
→ スタックが深くなりやすい
演算子を早めに処理する
→ 途中結果を1個にまとめられる
→ スタックが浅くなりやすい
ただし、式を見ただけで迷う場合は、必ず左からスタックを追います。
科目Bでどう使う?
科目Bでは、逆ポーランド表記そのものだけでなく、スタック処理のトレースとして考えると役立ちます。
例えば、
23+4×
を処理すると、
| 記号 | 操作 | スタック |
|---|---|---|
| 2 | push | [2] |
| 3 | push | [2, 3] |
| + | 2と3を計算し5をpush | [5] |
| 4 | push | [5, 4] |
| × | 5と4を計算し20をpush | [20] |
となります。
頭の中だけで追わず、
読んだ記号 | 操作 | スタック
の3列でメモするとミスを減らせます。
スタックの内容を1ステップずつ書き換える練習は、科目Bの疑似言語をトレースするときにもつながります。
よくある誤解・混同
値を読んだらすぐ計算する
値を読んだだけでは計算しません。
値
→ push
演算子
→ 計算
です。
演算子を読むとスタックの深さが2減る
2個popしますが、計算結果を1個pushするため、深さは結果として1だけ減ります。
最大スタック深さは変数の個数と同じ
違います。
4変数を使う式でも、
ab+c+d+
なら最大深さは2です。
変数の総数ではなく、途中で同時に何個積まれたかを数えます。
abcd+++ と ab+c+d+ は意味が違う
加算だけなら、どちらも
a+b+c+d
を計算します。
ただし、スタックの使い方と最大深さは異なります。
AB- は B-A
誤りです。
AB-
→ A-B
です。
減算と除算では順番を必ず確認します。
演算子を単純に右へ移動すればよい
誤りです。
普通の式から逆ポーランド表記へ変換するときは、先に計算される部分を「左・右・演算子」の形へ変換し、その結果を1つのかたまりとして外側へ進めます。
括弧を消すときに、演算子の順番も消してしまう
逆ポーランド表記では、括弧そのものは書きません。
ただし、括弧が示していた計算順序は、演算子を置く位置として残ります。
例えば、
(A+B)×C
なら、
AB+C×
です。
ABC+×
ではありません。
迷ったら、括弧の中を先に1つのまとまりへ変換してから、そのまとまり同士を次の演算子でつなぎます。
ポーランド表記法と同じ
違います。
+AB
→ ポーランド表記法(前置)
AB+
→ 逆ポーランド表記法(後置)
FIFOのキューでも同じように処理できる
逆ポーランド表記の評価では、最後に積んだ値を先に使うためLIFOのスタックが適しています。
スタックとキューの違いを整理したい場合は、スタックとキューの違いも確認してください。
確認問題(基本情報技術者試験対策)
問1:普通の式から逆ポーランド表記へ
次の式を逆ポーランド表記へ変換したものとして、適切なものはどれか。
x + (y × (z - w))
- ア.
xy+zw-* - イ.
xyz*w-+ - ウ.
xyzw-*+ - エ.
xyzw-+*
▶ クリックして答えと解説を見る(ここを開く)
正解:ウ
内側から順に変換します。
z - w
→ zw-
y × (z - w)
→ yzw-*
x + ...
→ xyzw-*+
したがって、正しい逆ポーランド表記は xyzw-*+ です。
ポイントは、z-w を変換した zw- を、次の掛け算では1つのかたまりとして扱うことです。
問2:最大スタック深さ
次の逆ポーランド表記をスタックで処理するとき、最大スタック深さはいくつか。
ab+cde+++
- ア. 2
- イ. 3
- ウ. 4
- エ. 5
▶ クリックして答えと解説を見る(ここを開く)
正解:ウ
左から処理します。
a → [a] 深さ1
b → [a, b] 深さ2
+ → [a+b] 深さ1
c → [a+b, c] 深さ2
d → [a+b, c, d] 深さ3
e → [a+b, c, d, e] 深さ4
+ → [a+b, c, d+e] 深さ3
+ → [a+b, c+d+e] 深さ2
+ → [a+b+c+d+e] 深さ1
最大深さは4です。
このタイプは見た目だけで判断せず、迷ったらスタックの状態を1段ずつ書くのが安全です。
まとめ(試験直前用)
- 逆ポーランド表記法は、演算子を値の後ろに置く後置表記法
- 普通の式から変換するときは、内側から「左・右・演算子」に変換し、完成部分を1つのかたまりとして扱う
- 値を読んだらpushする
- 演算子を読んだら2個popし、計算結果をpushする
- 最大スタック深さは、途中で同時に積まれた値の最大個数
- 演算子が早く出るほど、途中結果へまとめられて深さを小さくしやすい
- 減算・除算はpopした値の順番に注意する
- 複雑な式は、括弧の内側から順に1つずつ変換する
- 変換済みの部分は、次の演算では1つのかたまりとして扱う
値 → push
演算子 → 2個pop → 計算 → 結果をpush
スタックそのものを復習したい場合は、スタックとは?へ戻ると理解をつなげやすくなります。