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 はどうなるでしょうか。
この演算は、1+2を先にするのではなく、2×3を先に計算しますよね。つまり、2×3が一つの塊です。よって、(2×3)をZと考えると、1+Zですから、1Z+になります。Zに23×を入れると、123×+となります。
よって、この問題の正解はイです。
なぜこんな面倒なことをするのですか?
先ほどの過去問には、「逆ポーランド表記法で表記した数式は,数値や演算子を左から順に処理すればよく,括弧を使う必要もないので,コンピュータが数式を取り扱うのに都合が良い。」とあります。
上記の過去問ですが、このルールに従うと、 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のようになる。 ![]() 逆ポーランド表記法への変換は,次の(1)~(4)の手順で行う。 (1)変換前配列の先頭から順に,演算要素を1個参照する。 参照する演算要素がない場合は(4)に進む。 (2)スタック上に演算要素がある場合は,スタックの先頭にある演算要素の優先度を参照し, (1)の演算要素の優先度以上なら,スタックの先頭の演算要素をホップし,変換後配列の末尾に追加する。これを,スタックの先頭の演算要素の優先度が, (1)の演算要素の優先度未満になるまで繰り返す。ただし,スタックの先頭の演算要素が“(”の場合は,そこで繰返しを終了する。 (3)(1)で参照した演算要素が“)”なら,それを破棄し,その際スタックの先頭にあるはずの“(”もホップして破棄した後(1)に戻る。(1)で参照した演算要素が“)”以外なら,その演算要素をスタックにプッシュし. (1)に戻る。 (4)スタック上にある全ての演算要素を順番にホップし,変換後配列の末尾に追加する。 演算要素の優先度を表2に,数式1+2×3を変換するときの処理過程を図1に示す。 なお,図1中の丸で囲った演算要素は, (1)の手順で参照した演算要素である。 ![]() (後半略) 設問1 逆ポーランド表記法への変換について, (1), (2)に答えよ。 (1)数式(2+3)×4を逆ポーランド表記法に変換した結果を答えよ。 (2)表2及び表4中の[ ア ]~[ エ ]に入れる適切な二項演算子を、+,-,×,÷の中から一つずつ選んで,表を完成させよ。 (後半略) |
(2)H28秋AP午前問3
問3 逆ポーランド表記法で表された式を評価する場合,途中の結果を格納するためのスタックを用意し,式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき,入力が演算子となった。このときに行われる演算はどれか。ここで,演算は中置表記法で記述するものとする。![]() ア A 演算子 B ウ C 演算子 D イ B 演算子 A エ D 演算子 C |
中置表記法なので、3+4のように、演算子(×や+)が文字と文字の中に入ります。
ちなみに、逆ポーランド記法は、34+などと表記するので、後置記法と言われます。
(詳しくは別途解説)
スタックは後入れ先出し法(LIFO)ですので、上から順に処理をします。
ただこのとき、リンクの図を見てもらうとわかるように、最初に演算する数値が下に来ます。よって、正解は、ウの C 演算子 D です。
コメント