応用情報技術者試験 - SE娘の剣 -

応用情報処理技術者試験の対策サイトです。 応用情報処理技術者試験の午前問題を中心とした基礎用語の解説を中心に掲載します。書き始めたばかりなので、内容はまだまだ不十分です。少しずつ追記していきます

逆ポーランド表記法

 

1.逆ポーランド表記法

逆ポーランド表記法とは,演算子を二つの演算対象の後ろに配置することによって,数式を表現する表記法です。例えば,一般的な表記法の数式1+2×3を,逆ポーランド表記法では123×+と表記します。逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い表記方法です。

まずは過去問(H24秋AP午前問4)を見てみましょう。

問4 式 E=(A+B)×(C-D)と対応する逆ポーランド表記法はどれか。
ア =EX+AB-CD ウ EAB-CD+×=
イ EAB+CD-×= 工 EABCX+D-=


逆ポーランド表記法は、パッと見は難しいのですが、方式を覚えて慣れてしまえば難しくはありません。後述する過去問(H25春AP午後問2)をベースに解説します。
まず、表記の方法は、 2×3 を 23× とします。演算子を演算対象のすぐ後ろに配置するのです。このルールだけ覚えてください。
では、 1+2×3 はどうなるかというと、(2×3)をZと考えると、1+Zですから、1Z+になります。Zに23×を入れると、123×+となります。
2
よって、この問題の正解はイです。
応用情報技術者試験を勉強する成子 

なぜこんな面倒なことをするのですか?
先ほどの過去問には、「逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。」とあります。

上記の過去問ですが、このルールに従うと、 A+B は AB+ 、 C-D は CD- 
(A+B)と(C-D)をそれぞれの塊とみた上で掛け算をするので、 (A+B)×(C-D) は AB+CD-× になります。この塊とEを「=」という演算をすると考えればいいので、 EAB+CD-×= が正解です。

2.逆ポーランド表記法の過去問

(1)H25春AP午後問2
 過去問(H25春AP午後問2)に、逆ポーランド表記法に関する出題があるので以下に掲載します。

問2 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムに関する次の記述を読んで,設問1~3に答えよ。
 逆ポーランド表記法とは,演算子を二つの演算対象の後ろに配置することによって,数式を表現する表記法である。例えば,一般的な表記法の数式1+2×3を,逆ポーランド表記法では123×+と表記する。
 逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。
 一般的な表記法の数式から逆ポーランド表記法への変換は,スタックを用いることで容易に実現できる。

逆ポーランド表記法への変換アルゴリズム
 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムでは,まず変換前の数式を,数値,演算子及び括弧の要素(以下,演算要素という)に分解する。
演算子には二項演算子十,-,×,÷を用い,括弧には"("と")"を用いる。
数値は0~9の1桁の数とする。それぞれの演算要素には,優先度を定義する。
 変換の処理には,変換前配列,スタック及び変換後配列を用いる。初期状態では,変換前配列には変換前の数式の演算要素が順に入っており,スタックと変換後配列は空の状態である。変換後には,変換後配列に逆ポーランド表記法に変換した結果が入る。例えば,変換前の数式が1+2×3の場合,初期状態は表1のようになる。
a

 逆ポーランド表記法への変換は,次の(1)~(4)の手順で行う。
(1)変換前配列の先頭から順に,演算要素を1個参照する。
  参照する演算要素がない場合は(4)に進む。
(2)スタック上に演算要素がある場合は,スタックの先頭にある演算要素の優先度を参照し, (1)の演算要素の優先度以上なら,スタックの先頭の演算要素をホップし,変換後配列の末尾に追加する。これを,スタックの先頭の演算要素の優先度が, (1)の演算要素の優先度未満になるまで繰り返す。ただし,スタックの先頭の演算要素が“(”の場合は,そこで繰返しを終了する。
(3)(1)で参照した演算要素が“)”なら,それを破棄し,その際スタックの先頭にあるはずの“(”もホップして破棄した後(1)に戻る。(1)で参照した演算要素が“)”以外なら,その演算要素をスタックにプッシュし. (1)に戻る。
(4)スタック上にある全ての演算要素を順番にホップし,変換後配列の末尾に追加する。

演算要素の優先度を表2に,数式1+2×3を変換するときの処理過程を図1に示す。
なお,図1中の丸で囲った演算要素は, (1)の手順で参照した演算要素である。
b
(後半略)

設問1 逆ポーランド表記法への変換について, (1), (2)に答えよ。
(1)数式(2+3)×4を逆ポーランド表記法に変換した結果を答えよ。
(2)表2及び表4中の[ ア ]~[ エ ]に入れる適切な二項演算子を、+,-,×,÷の中から一つずつ選んで,表を完成させよ。

(後半略)


(2)H28秋AP午前問3

問3 逆ポーランド表記法で表された式を評価する場合,途中の結果を格納するためのスタックを用意し,式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき,入力が演算子となった。このときに行われる演算はどれか。ここで,演算は中置表記法で記述するものとする。
enzan
ア A 演算子 B   ウ C 演算子 D
イ B 演算子 A   エ D 演算子 C

中置表記法なので、3+4のように、演算子(×や+)が文字と文字の中に入ります。
ちなみに、逆ポーランド記法は、34+などと表記するので、後置記法と言われます。
スタックの流れは以下です。

sm.seeeko.com


 (詳しくは別途解説)
スタックは後入れ先出し法(LIFO)ですので、上から順に処理をします。
ただこのとき、リンクの図を見てもらうとわかるように、最初に演算する数値が下に来ます。よって、正解は、ウの C 演算子 D  です。