Contents
逆ポーランド記法で変換(括弧含む）やスタックについて
逆ポーランド記法（後置表記法）は通常の中置記法とは異なり、演算子（＋、－、×、÷）を2つの項の後ろに記述する数式の表現方法です。たとえば、中置記法の「2＋3」は、逆ポーランド表記法で「23＋」と記述されます。
ただし、以下のポイントに留意しながら変換していく必要があります。
逆ポーランド記法のポイント
- 優先順位：括弧付き”()”→積商算(×÷)→和差算(＋－)→＝ の順番
- 1回変換した部分は1つの項とみなすこと
例えば
式A＋B×Cの逆ポーランド表記法すると
①最初に「B×C」の部分を変換します。
A＋B×C → A＋BC× ※BC×は１つの項とみなす（演算子も）
②次に「BC×」を1つの項とみなしてAとの＋演算部分を変換します。
A＋BC× → ABC×＋
括弧や＝を含む計算式を逆ポーランド記法に変換
括弧や＝を含んでいる計算式を逆ポーランド記法で変換をかけてみます。
ポイントは繰り返しになりますが、
逆ポーランド記法のポイント
- 優先順位：括弧付き”()”→積商算(×÷)→和差算(＋－)→＝ の順番
- 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つずつスタックに積んでいく
- 演算子が現れたら、スタックから上2つの値を取り出して演算し、その結果をスタックに積む
- 式を最後まで評価し、スタックに残っている値が答えとなる
例えば、
2＋3×(4－2)の解は8となります。
逆ポーランド記法に変換すると2342－×＋をスタックを使って解が8となることを確認します。
この問題の式も、次のようにスタックを使って答えを求めることができます。
- 2を積む [2]
- 3を積む [2, 3]
- 4を積む [2, 3, 4]
- 2を積む [2, 3, 4, 2]
- －なので、4、2を取り出し、4－2の結果である2を積む [2, 3, 2]
- ×なので、3、2を取り出し、3×2の結果である6を積む [2, 6]
- ＋なので、2、6を取り出し、2＋6の結果である8を積む [8]
式の評価が終わった時点でスタックに残っている8が演算結果となり解を求めることができました。
コメントを残す