スタック
rpn電卓はどうやって逆ポーランド記法の式を解釈・実行しているのでしょうか。実は、逆ポーランド式の計算を語る上で絶対に避けて通れないのがスタックという仕組みです。
今まで敢えてスタックについては詳しく説明してきませんでした。スタックをしっかり理解することは必須なのですが、スタックを目にすることで逆に初心者が敷居の高さを感じたり、意識しすぎて逆ポーランドの計算自体が理解できなくなるからです。
予備知識のない初心者は、中置記法から後置記法(逆ポーランド記法)への変換を日本語の並びと同様に考えて、頭の中で変換することに慣れたほうが習熟が早くなるのです。
しかし、いずれスタックの理解は必要です。今後の講座ではrpnのスタック操作記号がたくさん出てきます。スタックを操作することで柔軟な計算ができるようになるので、スタックの動きを知っておくことは大切です。
スタックってなに
スタックとは何でしょうか。スタックは後入れ先出し方式の保存方法です。
| |
+-----+ スタックは
| | こんなイメージ
+-----+
2つの箱が積んであるイメージです。このスタックに新しい箱を積むとすると以下のようになります。
| NEW |
+-----+
| |
+-----+ スタックは
| | こんなイメージ
+-----+
一番、上に積まれましたね。では、このスタックから箱を取り出すとしたらどうしますか。一番、上の箱を取り出すしかないですよね(達磨落としでもすれば別ですが)。
| NEW | : :
+-----+ +-----+ +-----+
| | ---------> | | -------> | |
+-----+ 新しく箱を +-----+ 箱を取り +-----+
| | 加えると… | | 除くと… | |
+-----+ +-----+ +-----+
これが後入れ先出し方式です。「後に入れたものから先に出す」という方式です。専門用語では、LIFO(Last In First Out)と言います。rpnは、このスタックの仕組みを使って動作しています。
それでは、rpnがどうやってスタックを使って計算しているのか見ていきましょう。
rpnとスタックは切っても切れない仲
rpnはどんなときもスタックを使いながら計算しています。
1
こんな簡単なrpn式一つでもスタックを使っています。スタックのイメージは以下の図のようになります。
| 1 | スタック1段目
+---+
rpnは計算が終わると、最後にスタックに積んである数値を表示する仕組みになっています。今回の式ではスタックに1が残ったので、1が画面に表示されていますね。
計算式のスタックの動き
もうちょっと、rpnの計算式らしきもので例を示してみましょう。
3
このケースでは1と2を足して3が答えとして表示されています。この計算過程を①から③までスタックと共に追いかけてみましょう。
①②③
まず①時点でのスタックは以下のとおりです。
| 1 | スタック1段目(X)
+---+
単に1がスタックに積まれた状態ですね。便宜的に1段目のスタックのことをXといいます。次に②時点でのスタックですが、2がスタックに上乗せで積まれていきます。同じく便宜的に2段目のスタックのことをYといいます。
| 2 | スタック2段目(Y)
+---+
| 1 | スタック1段目(X)
+---+
そして、最後の③時点でのスタックですが、+を計算するために一旦、スタックに積まれた1と2を取り出して足します。結果は3になるので、3を再度スタックに積み戻す動作をします。
| 3 | スタック1段目
+---+
結果はスタックに3が残るだけです。この3がrpnの計算結果として表示されているわけです。
ここまでは簡単ですね。次に+や*、括弧が付いている式のスタックの動きを見てみましょう。
ちょっと複雑な計算式のスタックの動き
例題とする式は次のとおりです。括弧を伴ったちょっと複雑な計算式です。
(1 + 2) * (3 - 4) 1 2 + 3 4 - *
rpnは数式を①から⑦までの7ステップで計算することになります。
①②③④⑤⑥⑦
ここで、①から⑦まで計算が進むときのスタックの様子を示します。
| 4 | | 3段目(Z)
+---+ +---+---+---+ |
| 2 | | 3 | 3 | -1| | 2段目(Y)
+---+---+---+---+---+---+---+ |
| 1 | 1 | 3 | 3 | 3 | 3 | -3| | 1段目(X)
+---+---+---+---+---+---+---+ |
① ② ③ ④ ⑤ ⑥ ⑦
①から⑦まで計算が進む間にスタックに数値が詰まれては、「+」や「-」、「*」の演算記号で計算されて新しい数値に置き換えられることを繰り返している様子が分かります。そして、最後の⑦のスタックに残った数値が計算の答えとして表示されることになります。
rpn式とスタックを一緒に示すとより分かりやすいですね。
| 4 | | 3段目(Z)
スタックの様子 +---+ +---+---+---+ |
| 2 | | 3 | 3 | -1| | 2段目(Y)
+---+---+---+---+---+---+---+ |
| 1 | 1 | 3 | 3 | 3 | 3 | -3| | 1段目(X)
+---+---+---+---+---+---+---+ |
rpnが計算する順番 ① ② ③ ④ ⑤ ⑥ ⑦
1 2 + 3 4 - *
①で1がスタックに積まれます。②で今度は2が1の上に積まれていきます。次の③の「+」ですが、一旦、スタックから2と1と取り出して足し算して、計算結果の3を再度、スタックに積んでいます。
続いて、④と⑤で順次3と4をスタックに積んでいますね。⑥の「-」で4と3をスタックから取り出して引き算して、結果の-1をスタックに積みます。
最後に⑦の「*」で-1と3をスタックから取り出して掛けています。結果の-3をスタックに積み戻します。計算が終わったのでrpnはスタックに残った-3を表示するわけです。
どうですか。rpnが使うスタックの動きが理解できたでしょうか。
レジスタを使ったスタックの動き
次はレジスタを使ったrpn式です。レジスタとの値のやり取りが新しいだけで、他は同じ仕組みです。
レジスタを使う例として、半径2の円の面積を求める計算式を考えてみましょう。
12.56
半径2の円の面積は12.56ですね。では、このrpn式の動きをスタックと共に追いかけてみましょう。
①② ③ ④⑤ ⑥ ⑦
スタックの深さ
スタックの様子 +-------+ +-------+ ^
| 2 | | 3.14 | | 2段目(Y)
+-------+ +-------+-------+-------+-------+-------+ |
| 2 | | 2 | 2 | 4 | 4 | 12.56 | | 1段目(X)
+-------+-------+-------+-------+-------+-------+-------+ |
① ② ③ ④ ⑤ ⑥ ⑦
2 #r @r . * 3.14 *
rレジスタ
+-------+-------+-------+-------+-------+-------+-------+
| 0 | 2 | 2 | 2 | 2 | 2 | 2 |
+-------+-------+-------+-------+-------+-------+-------+
①は単に2をスタックに積んでいるだけですが、今までとちょっと違うのはレジスタが出ていることです。②の#rはスタックにある2をrレジスタにコピーして2をスタックから削除する(移動する)レジスタ操作記号です。
次の③の@rはrレジスタの値を参照してスタックに積む操作記号です。この際、rレジスタの2は残ります。従って、rレジスタは②の時点からずっと2のままです。
「#」はスタックからレジスタへの移動。「@」はレジスタからスタックへの複写(コピー)だということです。ここだけ注意すればあとは簡単です。
④に「.」がありますが、これはスタックに最後に積まれた(一番上の)数値をコピーして、スタックに戻す操作記号です。「.」でなくても@rでも構いません。
⑤は「*」なので、スタックから2と2を取り出して掛けた答えの4をスタックに積み戻します。⑥は3.14を単にスタックに積んでいますね。そして、最後の⑦の「*」で3.14と4をスタックから取り出して掛けることで答えが出てきます。
関数を使ったスタックの動き
最後に関数を使ったときのスタックの動きを追いかけてみましょう。例題は10の2乗の階乗です。つまり、10を自乗して出てきた答えの100の階乗を計算するわけです。下の数式を参照ください。
(10 ) ! = 100 !
rpnで計算するときの式は、次のように簡単です。
9.33262e+157
計算結果はとてつもなく大きな数値ですね。この計算の動きを追ってみます。
+-------+ ^
| 2 | | 2段目(Y)
+-------+-------+-------+------------+ |
| 10 | 10 | 100 |9.33262e+157| | 1段目(X)
+-------+-------+-------+------------+ |
① ② ③ ④
10 2 p !
①で10をスタックに積みます。②で2を上積みしていますね。③の「p」は冪乗の演算記号なのでスタックから2と10を取り出して、10の2乗を計算します。計算結果の100をスタックに積み戻すことになります。④の「!」は階乗の演算記号です。スタックから100を取り出して階乗計算して、結果を再度、スタックに積み戻しています。rpnは計算が終わったので④の結果を表示します。
rpnの動きとスタックの動きを簡単なrpn式から複雑なものまで順に説明してきました。スタックの動きを頭の片隅に置きながら、rpn式を追えば今後の講座に出てくるスタック操作記号やレジスタ・配列操作記号にも惑わされずに正確に計算できるようになると思います。
ちなみにrpn標準版のスタックは256段あるので、スタックの段数制限をほとんど気にせずに計算することができます。
/