応用情報技術者 2024年 秋期 午前2 問03

逆ポーランド記法【午前2解説】

正解の理由

解法ステップ

1. 入力Aを読む → オペランドなので出力列に追加: 出力 = A
2. 入力 + を読む → スタックが空なので + をスタックに積む: スタック = [+]
3. 入力Bを読む → オペランドなので出力に追加: 出力 = A B
4. 入力 × を読む → スタックの先頭にある + より × の方が優先度が高いので、× をそのままスタックに積む: スタック = [+, ×]
5. 入力Cを読む → オペランドなので出力に追加: 出力 = A B C
6. 入力が終わったのでスタックの演算子を上から順に出力へ移す（まず ×、次に +）: 出力 = A B C × +

選択肢別の誤答解説

• ア: +×CBA
  演算子が先頭に来ており、逆ポーランド記法の原則（オペランド→演算子）に反します。さらにオペランドの順序も式の意味（A + (B × C)）を反映していません。
• イ: x+ABC
  先頭に演算子（ここでは小文字のx = × と仮定）や + があり、演算子がオペランドの前に来ているため後置表記になっていません。演算の順序も間違っています。
• ウ: ABC×+
  オペランドを先に出力し、乗算（BとC）を先に処理するための × をその直後に配置し、最後に加算 + を置く正しい後置表記です。従って式A + B × Cの逆ポーランド表記として適合します。
• エ: CBA+×
  これを評価すると、まずBとAの和を求め（AとBを加算）、その結果にCを掛ける形になり、C × (A + B) を表します。元の式A + (B × C) とは演算順序が異なります。

よくある誤解

• 「BC× を先に書いて次にAを置く」と説明するとBC×A+ のように見えてしまい混乱します。正しくはオペランドを読み出力し、演算子は適切なタイミングでスタックから取り出して出力する手順（上記の手順）が必要です。
• 演算子の優先度を無視して左から単純に演算子を並べてしまうと誤答になります。乗算は加算より優先度が高い点を常に確認してください。
• 同じ記号（× やx）の表記ゆれに注意してください。選択肢の記号が異なっても位置関係が重要です。

補足コラム

# 後置式評価の簡単な例（単一文字オペランドを辞書で置換）
values = {'A':1, 'B':2, 'C':3}
expr = "ABC×+"
def eval_postfix(expr):
    stack = []
    for ch in expr:
        if ch in values:
            stack.append(values[ch])
        elif ch == '×':
            b = stack.pop(); a = stack.pop(); stack.append(a*b)
        elif ch == '+':
            b = stack.pop(); a = stack.pop(); stack.append(a+b)
    return stack[0]
print(eval_postfix(expr))  # 出力: 7

FAQ