本サイトはプロモーション(広告)が含まれています。

逆ポーランド記法で変換(括弧含む)やスタックについて

逆ポーランド記法で変換(括弧含む)やスタックについて

 逆ポーランド記法(後置表記法)は通常の中置記法とは異なり、演算子(+、-、×、÷)を2つの項の後ろに記述する数式の表現方法です。たとえば、中置記法の「2+3」は、逆ポーランド表記法で「23+」と記述されます。

 ただし、以下のポイントに留意しながら変換していく必要があります。

逆ポーランド記法のポイント

  1. 優先順位:括弧付き”()”→積商算(×÷)→和差算(+-)→= の順番
  2. 1回変換した部分は1つの項とみなすこと

例えば

式A+B×Cの逆ポーランド表記法すると

①最初に「B×C」の部分を変換します。
 A+B×C → A+BC× ※BC×は1つの項とみなす(演算子も
②次に「BC×」を1つの項とみなしてAとの+演算部分を変換します。
 ABC× → ABC×+

括弧や=を含む計算式を逆ポーランド記法に変換

括弧や=を含んでいる計算式を逆ポーランド記法で変換をかけてみます。

ポイントは繰り返しになりますが、

逆ポーランド記法のポイント

  1. 優先順位:括弧付き”()”→積商算(×÷)→和差算(+-)→= の順番
  2. 1回変換した部分は1つの項とみなすこと

です。

式E=(A+B)×(C-D)を逆ポーランド記法に変換すると

①まず括弧内の A+B と C-Dを、それぞれAB+、CD-に変換します。
 E=(AB+)×(CD-)

②”×”の左側と右側の演算を変換します。この時「AB+」「CD-」をそれぞれ1つの項として捉えます。
 E=AB+CD-×

③最後に 左辺と右辺を”=”で演算して逆ポーランド表記法への変換は終了です。
 EAB+CD-×=

二重括弧がある場合の逆ポーランド記法への変換

括弧の中に括弧がある場合でも、括弧の中の括弧を優先していくという考えで問題ないです。

例えば、次の式を逆ポーランド記法で変換をかけていきます。

Y=(A+B)×(C-(D÷E))

①まず括弧内のA+B と D÷Eを変換します。
 Y=AB+×(C-DE÷)

②次にもう一つの括弧内の(C-DE÷)を変換します。
 Y=AB+×CDE÷-
この時「DE÷」を一つの項として考えます。
「C」-「DE÷」⇒CDE÷-

③次に右辺でまだ演算をしていない、”×”の左側と右側で演算します。先程と同様に「AB+」×「CDE÷-」⇒AB+CDE÷-×と考えます。
 Y=AB+CDE÷-×

④最後に 左辺と右辺を”=”で演算して逆ポーランド表記法への変換が完了します。
 YAB+CDE÷-×=

 

逆ポーランド記法とスタックについて

 プログラミングにおいて、スタックを利用しての計算にて逆ポーランド記法は役に立っています。

 逆ポーランド記法はプログラミングで「スタックにデータを積む (PUSH) 操作」、「スタックからデータを下ろす (POP) 操作」、「二つのオペランド間の演算」だけで計算動作が可能になるからです。

 具体的には以下の手順で逆ポーランド記法の式をスタックを利用して計算可能です。

  1. 数式の左側から値を1つずつスタックに積んでいく
  2. 演算子が現れたら、スタックから上2つの値を取り出して演算し、その結果をスタックに積む
  3. 式を最後まで評価し、スタックに残っている値が答えとなる

例えば、

2+3×(4-2)の解は8となります。

 逆ポーランド記法に変換すると2342-×+をスタックを使って解が8となることを確認します。

この問題の式も、次のようにスタックを使って答えを求めることができます。

  1. 2を積む [2]
  2. 3を積む [2, 3]
  3. 4を積む [2, 3, 4]
  4. 2を積む [2, 3, 4, 2]
  5. -なので、4、2を取り出し、4-2の結果である2を積む [2, 3, 2]
  6. ×なので、3、2を取り出し、3×2の結果である6を積む [2, 6]
  7. +なので、2、6を取り出し、2+6の結果である8を積む [8]

式の評価が終わった時点でスタックに残っている8が演算結果となり解を求めることができました。

情報処理 の記事一覧

PAGE TOP