1.逆ポーランド表記法
逆ポーランド表記法とは，演算子を二つの演算対象の後ろに配置することによって，数式を表現する表記法です。例えば，一般的な表記法の数式1＋2×3を，逆ポーランド表記法では１２３×+と表記します。逆ポーランド表記法で表記した数式は，数値や演算子を左から順に処理すればよく，括弧を使う必要もないので，コンピュータが数式を取り扱うのに都合が良い表記方法です。
まずは過去問（H24秋AP午前問4）を見てみましょう。
| 問4 式 E＝(A＋B)×(C－D)と対応する逆ポーランド表記法はどれか。 ア ＝EX＋AB－CD ウ EAB－CD＋×＝ イ EAB＋CD－×＝ 工 EABCX＋D－＝ |
逆ポーランド表記法は、パッと見は難しいのですが、方式を覚えて慣れてしまえば難しくはありません。後述する過去問（H25春AP午後問2）をベースに解説します。
まず、表記の方法は、 ２×３ を ２３× とします。演算子を演算対象のすぐ後ろに配置するのです。このルールだけ覚えてください。
では、 1＋2×3 はどうなるでしょうか。
この演算は、１＋２を先にするのではなく、２×３を先に計算しますよね。つまり、２×３が一つの塊です。よって、（２×３）をZと考えると、１＋Zですから、１Z＋になります。Zに23×を入れると、123×+となります。
よって、この問題の正解はイです。
なぜこんな面倒なことをするのですか？
先ほどの過去問には、「逆ポーランド表記法で表記した数式は，数値や演算子を左から順に処理すればよく，括弧を使う必要もないので，コンピュータが数式を取り扱うのに都合が良い。」とあります。
上記の過去問ですが、このルールに従うと、 A＋B は AB＋ 、 C－D は CD－
(A＋B)と(C－D)をそれぞれの塊とみた上で掛け算をするので、 (A＋B)×(C－D) は AB＋CD－× になります。この塊とEを「＝」という演算をすると考えればいいので、 EAB＋CD－×= が正解です。
２．逆ポーランド表記法の過去問
（１）H25春AP午後問2
過去問（H25春AP午後問2）に、逆ポーランド表記法に関する出題があるので以下に掲載します。
| 問２ 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムに関する次の記述を読んで，設問1～3に答えよ。 逆ポーランド表記法とは，演算子を二つの演算対象の後ろに配置することによって，数式を表現する表記法である。例えば，一般的な表記法の数式1＋2×3を，逆ポーランド表記法では１２３×+と表記する。 逆ポーランド表記法で表記した数式は，数値や演算子を左から順に処理すればよく，括弧を使う必要もないので，コンピュータが数式を取り扱うのに都合が良い。 一般的な表記法の数式から逆ポーランド表記法への変換は，スタックを用いることで容易に実現できる。 〔逆ポーランド表記法への変換アルゴリズム〕 一般的な表記法の数式を逆ポーランド表記法に変換するアルゴリズムでは，まず変換前の数式を，数値，演算子及び括弧の要素（以下，演算要素という）に分解する。 演算子には二項演算子十，－，×，÷を用い，括弧には"("と"）"を用いる。 数値は0～9の１桁の数とする。それぞれの演算要素には，優先度を定義する。 変換の処理には，変換前配列，スタック及び変換後配列を用いる。初期状態では，変換前配列には変換前の数式の演算要素が順に入っており，スタックと変換後配列は空の状態である。変換後には，変換後配列に逆ポーランド表記法に変換した結果が入る。例えば，変換前の数式が1＋2×3の場合，初期状態は表１のようになる。  逆ポーランド表記法への変換は，次の(1)～(4)の手順で行う。 (1)変換前配列の先頭から順に，演算要素を１個参照する。 参照する演算要素がない場合は(4)に進む。 (2)スタック上に演算要素がある場合は，スタックの先頭にある演算要素の優先度を参照し, (1)の演算要素の優先度以上なら，スタックの先頭の演算要素をホップし，変換後配列の末尾に追加する。これを，スタックの先頭の演算要素の優先度が, (1)の演算要素の優先度未満になるまで繰り返す。ただし，スタックの先頭の演算要素が“（”の場合は，そこで繰返しを終了する。 （3）（1）で参照した演算要素が“）”なら，それを破棄し，その際スタックの先頭にあるはずの“（”もホップして破棄した後（1）に戻る。（1）で参照した演算要素が“）”以外なら，その演算要素をスタックにプッシュし. (1)に戻る。 （4）スタック上にある全ての演算要素を順番にホップし，変換後配列の末尾に追加する。 演算要素の優先度を表２に，数式1＋2×3を変換するときの処理過程を図１に示す。 なお，図１中の丸で囲った演算要素は, (1)の手順で参照した演算要素である。  （後半略） 設問１ 逆ポーランド表記法への変換について, (1), (2)に答えよ。 (1)数式(２＋3)×4を逆ポーランド表記法に変換した結果を答えよ。 (2)表２及び表４中の[ ア ]～[ エ ]に入れる適切な二項演算子を、+，－，×，÷の中から一つずつ選んで，表を完成させよ。 （後半略） |
（２）H28秋AP午前問3
問3 逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき，入力が演算子となった。このときに行われる演算はどれか。ここで，演算は中置表記法で記述するものとする。 ア A 演算子 B ウ C 演算子 D イ B 演算子 A エ D 演算子 C |
中置表記法なので、３＋４のように、演算子（×や＋）が文字と文字の中に入ります。
ちなみに、逆ポーランド記法は、３４＋などと表記するので、後置記法と言われます。
（詳しくは別途解説）
スタックは後入れ先出し法（LIFO)ですので、上から順に処理をします。
ただこのとき、リンクの図を見てもらうとわかるように、最初に演算する数値が下に来ます。よって、正解は、ウの C 演算子 D です。
コメント