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

計算式と逆ポーランド表記法の組合せ【午前2 解説】

要点まとめ

• 結論：選択肢エが正解。計算式 $a+(b\ast (c-d))$ の逆ポーランド表記は $abcd-\ast +$、つまり abcd−*+ です。
• 根拠：逆ポーランド表記は演算子をオペランドの後に置き、括弧と演算子優先度に従って出力順を決めるため、内側の $(c-d)$ が先に出力されます。
• 差がつくポイント：文字列を単に左から右へ変換するのではなく、括弧の入替と演算子の適用順（優先度・結合性）を厳密に扱うことです。

正解の理由

よくある誤解

• 「文字列の順でそのまま演算子を移す」：括弧の内側で先に行われる演算があることを忘れて誤った順序になる。
• 「演算子の優先度を逆ポーランドで無視する」：*や/の優先度を考えず + や - と同列扱いにしてしまう。
• 「空白や区切りを無視してトークン化を誤る」：トークン分割を曖昧にすると順序が狂い発想ミスにつながる。

解法ステップ

1. 式をトークンに分割する（変数、演算子、括弧）。
2. 最も内側の括弧から順に、演算子の優先度に従ってオペランドの後に演算子を出力する（シャント・イングヤードやスタック方式）。
3. 括弧が無くなったら、残った演算子を優先度順かつ結合性に従って出力する。
4. 出力した順が逆ポーランド表記。実際に $a+(b\ast (c-d))$ を処理すると、まず $cd-$、次に $b(cd-)\ast$、最後に $a(\text{結果})+$ で $abcd-\ast +$ になる。

選択肢別の誤答解説

• ア
  • 計算式：$((a+b)\ast c)-d$
  • 与えられた逆ポーランド表記：abc*+d−
  • 解説：正しい逆ポーランド表記は $ab+c\ast d-$（ab+cd-）であり、与えられた abc+d− は $(a+(b\ast c))-d$ に相当するため不正解。
• イ
  • 計算式：$(a+(b\ast c))-d$
  • 与えられた逆ポーランド表記：ab+c*d−
  • 解説：正しい逆ポーランド表記は $abc\ast +d-$（abc*+d-）で、提示の ab+c*d− はトークン順が狂っており不適合。
• ウ
  • 計算式：$(a+b)\ast (c-d)$
  • 与えられた逆ポーランド表記：abc* d−+（空白は無視すると "abc*d-+"）
  • 解説：実際は $ab+cd-\ast$（ab+cd-*）が正解。提示の表記は演算子の位置が誤っている。
• エ
  • 計算式：$a+(b\ast (c-d))$
  • 与えられた逆ポーランド表記：abcd−*+
  • 解説：$cd-$ → $b(cd-)\ast$ → $a(\text{結果})+$ の順で、正しく $abcd-\ast +$ となるため正解。

補足コラム

• 中置表記 $a+(b\ast (c-d))$ の値は $1+(2\ast (5-3))=1+4=5$。
• 逆ポーランド表記 abcd−*+ をスタックで評価しても同じ結果になります。
  簡易的な検算用 Python スニペット：

a,b,c,d = 1,2,5,3
infix = a + (b * (c - d))
# RPN evaluation for "a b c d - * +"
stack = []
for token in ['a','b','c','d','-','*','+']:
    if token == 'a': stack.append(a)
    elif token == 'b': stack.append(b)
    elif token == 'c': stack.append(c)
    elif token == 'd': stack.append(d)
    elif token == '-':
        x,y = stack.pop(), stack.pop()
        stack.append(y - x)
    elif token == '*':
        x,y = stack.pop(), stack.pop()
        stack.append(y * x)
    elif token == '+':
        x,y = stack.pop(), stack.pop()
        stack.append(y + x)
rpn_value = stack.pop()
print(infix, rpn_value)  # 5 5

FAQ