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

逆ポーランド記法の演算評価【午前解説】

正解の理由

解法ステップ

1. トークン列を左から順に読む：A B + C D E / - *
2. 値を見つけたらスタックに積む（push）、演算子が来たら直近2つを取り出して演算し結果を戻す（pop, op, push）。
3. 実際のスタック変化（以下で詳述）を追えば答えが得られる。

• 初期 []
• A=1 を push → [1]
• B=3 を push → [1, 3]
• '+' で 1 + 3 = 4 を push → [4]
• C=5 を push → [4, 5]
• D=4 を push → [4, 5, 4]
• E=2 を push → [4, 5, 4, 2]
• '/' で 4 / 2 = 2 を push → [4, 5, 2] （左オペランドが 4、右が 2）
• '-' で 5 - 2 = 3 を push → [4, 3]
• '*' で 4 * 3 = 12 を push → [12] → 最終結果 12

選択肢別の誤答解説

• ア: -12
  • 逆ポーランド表記でオペランド順を逆に扱い、$5-2$ と $4\times (-3)$ のような符号ミスや順序ミスで生じうる値です。符号や順序を厳密に確認すれば防げます。
• イ: 2
  • 中間段階の値 $4/2=2$ を最終結果と誤認したケース。最終演算（ここでは掛け算）を忘れがちです。
• ウ: 12（正解）
  • 正しくスタック手順に従って演算した結果で、最終スタック値が $12$ になります。
• エ: 14
  • おそらく $1+3=4$ と $5+4=9$ を足して $13$ に何らかの誤加算や別の順序ミスで $14$ にズレるような計算ミスが原因です。

よくある誤解

• 演算子の適用順を読み違えて「/ や - のオペランド順が逆」になり、$4/2$ を $2/4$ のように誤計算する。
• RPN を中置（通常の式）と混同して左から単純に計算しようとし、スタック操作を省略して途中の値を見落とすこと。
• 最後の掛け算を忘れて中間結果（例：2 や 3）を答えにしてしまうミス。

補足コラム

def eval_rpn(tokens, values):
    stack = []
    for t in tokens:
        if t in values:
            stack.append(values[t])
        else:
            b = stack.pop()
            a = stack.pop()
            if t == '+':
                stack.append(a + b)
            elif t == '-':
                stack.append(a - b)
            elif t == '*':
                stack.append(a * b)
            elif t == '/':
                stack.append(a // b)  # 整数除算の例
    return stack[0]

tokens = ['A','B','+','C','D','E','/','-','*']
vals = {'A':1,'B':3,'C':5,'D':4,'E':2}
print(eval_rpn(tokens, vals))  # 12

FAQ