基本情報技術者平成21年秋期 午前問3

問3

逆ポーランド表記法(後置表記法)で,“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+÷+"では、EF-, CD-及びAB+がそれに当たります。
 EF-CD-AB+÷+

この[文字,文字,演算子]のパターンにマッチした場所を、[文字,演算子,文字]に変えます。
 (E-F)G÷(C-D)(A+B)÷+

上記のように変換した部分については、そのかたまりを一つの項として扱いますので括弧で括っておくとわかりやすいでしょう。

再び、式の中から[文字,文字,演算子]のパターンになっている箇所を探します。先ほど変換した部分についても一つの文字(項)として見てみると、(E-F)G÷と(C-D)(A+B)÷がパターンにマッチします。
 (E-F)G÷(C-D)(A+B)÷

先ほどと同じように、パターンにマッチした部分を、[文字,演算子,文字]に変えます。
 ((E-F)÷G) ((C-D)÷(A+B))+

まだ右端に +の演算子が残っていますので、再び同じ処理を繰り返し、[文字,演算子,文字]に変換します。
 ((E-F)÷G)+((C-D)÷(A+B)) …「ウ」の式

もうおわかりになったと思いますが、逆ポーランド表記法から通常の式に変換する方法は、式の中から[文字,文字,演算子]のパターンになっている箇所を探し、その部分を[文字,演算子,文字]に変えるという処理を繰り返すだけなのです。
© 2010- 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop