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

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

はじめに

コジマです。

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

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

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

普通の四則演算だと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)を
フォローしてくれたらうれしいです!

もっと学びたい人はこちら

エンジニアになりたい!基本的な知識を身に着けたい!という人のためにおすすめのUdemy講座を紹介いたします!

私が時々扱うエンジニアが身に着けるべき数学の内容だったり、
基本情報や応用情報の試験対策をすることもできます。
エンジニアとして働くために資格は必須ではないですが、私は勉強したほうが良いと思う派です。
最新版: 基本情報技術者試験+応用情報技術者試験+Python+SQL 初心者からプロのエンジニアになる講座

エンジニアにとってネットワークは必要不可欠です。
今こうしてみて頂いている私のブログもインターネットの上で成り立っています。
この講座は基本的といえど、物理層からアプローチしているので小難しく感じると思います。
しかし、この基礎固めができているか否かで今後の成長率が段違いになります。思わぬ障害に出会った時も基本に立ち返り、あなたを適切なアプローチをもたらしてくれるはずです。
ネットワークエンジニアを目指す初心者はここから始めよう!「ゼロから学ぶネットワーク基礎」豊富な図解で徹底解説

気になった人はぜひ見てみてくださいね!

以上、コジマでした。


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