逆ポーランド記法⇔数式の変換方法【基本情報】

逆ポーランド記法⇔数式の変換方法【基本情報】

はじめに

コジマです。

基本情報の試験でよく出てくる逆ポーランド記法について書いてみようと思います。

逆ポーランド記法ってなに?

超簡単に言うと、数式を数字数字演算子の順番で書く書き方です。

普通の四則演算だと1+2のように数字演算子数字の順ですが、
逆ポーランド記法だと12+のように書きます。

逆ポーランド記法⇔数式の変換方法を順を追って説明します。
ここでは、いわゆる普通の四則演算を「数式」と呼ぶことにします。

以下、大前提として四則演算の計算順序は既知であるものとします。(そりゃそう)

数式=>逆ポーランド記法

ポイント
カッコは一つの数字とみなす。

順序

  1. 1番目に計算する「数字演算子数字」を「数字数字演算子」に並び替える
  2. 1の後また並び替えができるか確かめる
  3. 並び替えができたら1に戻る。並び替えができなくなったらカッコをはずす
  4. =があれば後ろに持っていく
  5. 並び替え終わったら終了

例題

習うより慣れろ。です。
出典:平成24年度 春期 基本情報技術者試験 午前 問4

後置表記法(逆ポーランド表記法)では,例えば,式 Y=(A-B)×C を YAB-C×= と表現する。
 次の式を後置表記法で表現したものはどれか。
  Y=(A+B)×(C-(D÷E))

ア:YAB+C-DE÷×=
イ:YAB+CDE÷-×=
ウ:YAB+EDC÷-×=
エ:YBA+CD-E÷×=

解説

実際にやってみましょう
1:(A+B)、(C-(D÷E))をそれぞれひとつの数字としてみなして並び替え
Y=(A+B)(C-(D÷E))×

2:D÷Eを並び替え
Y=(A+B)(C-(DE÷))×

3:(C-(DE÷))を並び替え
(DE÷)は一つの数字としてみなします。
Y=(A+B)(C(DE÷)-)×

4:A+Bを並び替え
Y=(AB+)(C(DE÷)-)×

5:カッコをはずす
Y=AB+CDE÷-×

6:=を後ろに持っていく

YAB+CDE÷-×=

これにてフィニッシュ。答えは「イ」ですね。

逆ポーランド記法=>数式

つまりはさっきと逆のことをやります。

ポイント
カッコは一つの数字とみなす。

順序

  1. =があれば1つ目の数字の後ろに持っていく
  2. 左から見ていき、「数字数字演算子」の並びをみつける
  3. 2で見つけた「数字数字演算子」を「数字演算子数字」に並び替える
  4. 3で並び変えたらカッコをつける
  5. 2~4を繰り返す
  6. 並び替え終わったら終了

例題

出典:平成21年度 秋期 基本情報技術者試験 午前 問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))

解説

実際にやってみましょう

1:EF-を並び替えてカッコつける
(E-F)G÷CD-AB+÷+

2:(E-F)G÷を並び替えてカッコつける
((E-F)÷G)CD-AB+÷+

3:CD-を並び替えてカッコつける
((E-F)÷G)(C-D)AB+÷+

4:AB+を並び替えてカッコつける
((E-F)÷G)(C-D)(A+B)÷+

5:(C-D)(A+B)÷を並び替えてカッコつける

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

6:((E-F)÷G)((C-D)÷(A+B))+を並び替えてカッコつける

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

これにてフィニッシュ。答えは「ウ」ですね。

さいごに

過去問のIPAの規約に則って引用しております。
https://www.jitec.ipa.go.jp/1_09faq/_index_faq.html

実際に手を動かしてみたらちょろいです。
確実に一問取りに行きましょう。

この記事を面白いまたは役に立ったと思ってくれた方は是非私のTwitter(@kojimanotech)を
フォローしてくれたらうれしいです!

以上、コジマでした。


エンジニア全般カテゴリの最新記事