逆ポーランド記法

オペレータとオペランド

数式はオペレータとオペランドから構成される

  • オペレータ・・・演算子（＋　－　＊　/）
  • オペランド・・・被演算子（数値、変数、定数）

二項演算

二項演算子とは、数の四則演算などの 「二つの数から新たな数を決定する規則」 を一般化した概念

例　１　+　２　　１と２がオペランド、+がオペレータ

数式の計算

通常、数式の計算は

  • １　+　２　　オペレータ（演算子）を真ん中に置く

と記述するが、コンピュータで計算する場合には

  • １　２　+　　オペレータ（演算子）を後ろに置く

にいったん変換してから、計算する（この方が簡単に処理できる）

ちなみに、日本語で「１+２」を表現すると

  • １に２を加える　　オペレータを後ろに置いている→コンピュータ内部と同じ

逆ポーランド記法とは

逆ポーランド記法（後置表記）は、コンピュータで処理するのに都合のいい形の数式の書き方。コンピュータは、入力した数式を逆ポーランド記法（後置表記）に変換してから計算処理を行う。

例

 

※逆ポーランド記法への書き換え方法は一つではない。

中置記法　前置記法　後置記法とは

数式を記述する方法には、中置記法、前置記法、後置記法の３つがある

数式から逆ポーランド記法への変換方法１（二項演算単位で変換する）

数式の中で優先順位の高い演算（同じ優先順位の場合には、左から順に）から逆ポーランド記法（後置表記）に変換する

上図で、□はオペランド（被演算子）と考える

算術演算子の優先順位

例

例

１　+　２　－　３　→　１　２　+　－　3　→　１　２　+　3　－

1　×　２　÷　３　→　１　２　×　÷　３　→　１　２　×　３　÷

１　＋　２　×　３　→　１　+　２　３　×　→　１　２　３　×　+

数式から逆ポーランド記法への変換方法２
（二つ以上の同じ優先順位の演算子を含む式を変換する）

オペランドは左から右の順で、オペレーションは右から左の順で並べる

例

例

１　+　２　－　３　→　１　２　３　－　+

1　×　２　÷　３　→　１　２　３　÷　×

１　＋　２　×　３　→　１　+　２　３　×　→　１　２　３　×　+

 

 

逆ポーランド記法に変換した数式をスタックを利用して計算する

逆ポーランド記法に変換した数式のオペランド、オペレーションを、左からひとつずつ取り出して、以下の処理を行う。

①逆ポーランド記法の数式から一つ取り出す

②オペランド（数値）の場合には、スタックにpush

③オペレータ（演算子）の場合には、スタックに格納されている２つの数値をpopで取り出して、次のように演算を行う
（後でpopで取り出した数値）演算子（先にpopで取り出した数値）

④演算結果をスタックにpush　※逆ポーランド記法の数式のオペランド、オペレータがなくなるまで①～④を繰り返す。

⑤最後にスタックに残った値が、数式の結果となる

例　数式「１＋２－３」を逆ポーランド記法に変換し、スタックを使って計算する

１　+　２　－　３　→　１　２　+　－　3　→　１　２　+　3　－

左から順に取り出し、スタックを使って計算する

練習問題

数式「１×２÷３」を逆ポーランド記法に変換し、スタックを使って計算しなさい

なぜ、逆ポーランド記法にするとコンピュータは処理しやすいのか？

通常使う数式の記法「中置記法」だと、計算するには演算子の優先順位を考えなければいけない。逆ポーランド記法だと、演算子の優先順位を考えずに、順に処理するので、シンプルなプログラムになる。

逆ポーランド記法から通常の数式に変換する方法

逆ポーランド記法　　→　通常の数式

数字　数字　演算子　→　数字　演算子　数字

上記のように変換していく

＝がある数式を逆ポーランド記法に変換する

※　＝は、演算子の中で最も優先順位が低い

確認問題

１．数式は（　a　）（演算子）と（　ｂ　）（被演算子）から構成される

２．（　a　）は、コンピュータで処理するのに都合のいい形の数式の書き方

３．数式を記述する方法には、（　a　）、（　ｂ　）、（　ｃ　）の３つがある

４．当てはまる演算子を入れなさい　　（演算子　+　－　※　／　（）　＝）

５．次の数式を逆ポーランド記法（変換方法1で）に変換しなさい。

(1)　A＋B×C－D         (2)　A÷B－C÷D＋E      (3)　 (A＋B)÷(C＋D)×E

６．次の数式を逆ポーランド記法（変換方法２で）に変換しなさい。

(1)　A＋B×C－D         (2)　A÷B－C÷D＋E      (3)　 (A＋B)÷(C＋D)×E

７．次の数式を逆ポーランド記法に変換後、スタックを使って計算しなさい。

(1)　1＋2×3－4               (2)　6÷2－4÷2＋5      (3)　 (5＋3)÷(1＋1)×2

基本情報対策問題

１．逆ポーランド記法（後置表記法）で、“EF－G÷CD－AB＋÷＋”と表現される式を通常の式（中置表記法）で表現しなさい。（H21　基本情報　秋　改題）

２．A＝1，B＝3，C＝5，D＝4，E＝2 のとき，逆ポーランド表記法で表現された式 AB＋CDE／－* の演算結果を求めなさい。（H22　基本情報　春　改題）

３．A＝1，B＝2，C＝3，D＝4，E＝2 のとき，逆ポーランド表記法で表現された式 ABC×＋DE÷－の演算結果を求めなさい。

４．後置表記法(逆ポーランド表記法)では，例えば，式 Y＝(A－B)×C を YAB－C×＝ と表現する。（H23　高度　秋　改題）

次の式を後置表記法で表現しなさい。

Y＝(A＋B)×(C－(D÷E))

５．逆ポーランド表記法で表された式を評価する場合，途中の結果を格納するためのスタックを用意し，式の項や演算子を左から右に順に入力し処理する。スタックが図の状態のとき，入力が演算子となった。このときに行われる演算はどれか。ここで，演算は中置表記法で記述するものとする。（H28　高度情報　秋）

ア　A　演算子　B　　　イ　B　演算子　A

ウ　C　演算子　D　　　エ　D　演算子　C