基本情報技術者 2009年秋期午前（科目A）問03

問題文

逆ポーランド表記法(後置表記法)で、“EF-G÷CD-AB+÷+”と表現される式はどれか。

選択肢

ア：((A+B)+(C-D))÷G-(E÷F)

イ：((A+B)÷(C-D))+G÷(E-F)

ウ：((E-F)÷G)+((C-D)÷(A+B))（正解）

エ：((E-F)÷G)÷((C-D)+(A+B))

##: 逆ポーランド表記法の式判定 — EF-G÷CD-AB+÷+【午前2 解説】

要点まとめ

結論: 後置表記「EF-G÷CD-AB+÷+」は $((E - F) \div G) + ((C - D) \div (A + B))$ を表すため、選択肢ウが正解です。
根拠: 後置表記は左から読みスタックに積み、演算子が出たら直前の2項を取り計算する「スタック方式」で式が決まります。
差がつくポイント: 減算・除算は非可換なのでオペランドの取り出し順（先に積まれた方が左オペランド）を絶対に逆にしないこと。

正解の理由

後置表記 "EF-G÷CD-AB+÷+" を左から順に処理すると次の2つの部分式が作られ、それらを加算します。

最初に
```
E F - G ÷
```
が処理され $(E - F) \div G$ になる。
次に
```
C D - A B + ÷
```
が処理され $(C - D) \div (A + B)$ になる。
最後にこれら二つを加えるので式は $((E - F) \div G) + ((C - D) \div (A + B))$ となり、選択肢ウと一致します。

よくある誤解

演算子の左右を入れ替えてしまい $(F - E) \div G$ のように誤ることがあります。
÷ や − の順序を無視して優先度で誤って括弧を付けるミスが頻出します。

解法ステップ

式を左から読み、アルファベットはスタックに積む。
演算子（−, ÷, ＋）が来たらスタックの「直近の2つ」を取り、左オペランドは先に積まれた方、右オペランドは後に積まれた方とする。
その演算結果（または部分式）を再びスタックに積む。
最後にスタックに残った1つの式が求める中置表記である。
上の手順で "EF-G÷" → $(E - F) \div G$ 、"CD-AB+÷" → $(C - D) \div (A + B)$ 、最後に加算で合成。

選択肢別の誤答解説

ア: $((A + B) + (C - D)) \div G - (E \div F)$ — 演算の構造や演算子の適用順が根本的に異なり、元の後置順と合致しません。
イ: $((A + B) \div (C - D)) + G \div (E - F)$ — 部分式の順序とオペランドの取り方が逆で、G の位置も誤りです。
ウ: $((E - F) \div G) + ((C - D) \div (A + B))$ — 正しい。スタック処理に従うとこの式が得られます。
エ: $((E - F) \div G) \div ((C - D) + (A + B))$ — 最後の演算が「÷」になっており、元の末尾が「+」である点と矛盾します。

補足コラム

逆ポーランド記法（後置表記）は括弧不要で計算の逐次処理に適しており、計算機の内部処理や電卓（HP電卓等）でよく使われます。
中置→後置の変換はシューダン＝ヤード（Shunting-yard）アルゴリズムで行えます。
実務的には、非可換演算（−, ÷）の順序を必ず確認することがケアレスミス防止に有効です。

FAQ

Q: 後置表記で「−」や「÷」の左右はどう決まりますか？
A: スタックからポップする順で、先にポップした値が右オペランド、次にポップした値が左オペランドとなります（読みは左から右で積む）。

Q: RPN の式を手早く中置に直すコツは？
A: スタックを文字列として扱い、演算子が出たら直前の2つを括弧で結合して戻す手順を頭でシミュレートすると速いです。

関連キーワード: 逆ポーランド記法、後置記法、スタック、式評価、演算子順序、シュタイン＝ヤード

コード例（後置表記を文字列の中置式に変換する簡易Python例）

def rpn_to_infix(tokens):
    stack = []
    for t in tokens:
        if t.isalpha():  # オペランド
            stack.append(t)
        else:  # 演算子
            b = stack.pop()
            a = stack.pop()
            stack.append(f"({a}{t}{b})")
    return stack[0]

tokens = list("EF-G÷CD-AB+÷+".replace("÷","/"))  # ÷ を / に置換して扱う
print(rpn_to_infix(tokens))
# 出力: ((E-F)/G)+((C-D)/(A+B))