スタックで解く逆ポーランド記法

さて、今回のテーマなんですけど、逆ポーランド記法です。はい。これあの、基本情報技術者試験の勉強とかしてると、まあ必ず出てきますよね。 出てきますね。多くの人がここで、ん？ってなるポイントです。ですよね。僕も最初見たとき、正直なにかの暗号かと思いましたもん。 1+2でいいじゃないかって話を、わざわざ1 2 +って書く？えー、人間の直感からすると、すごく奇妙に見えますよね。 表示がバグったのかな？って思いますよね。思います思います。私も学生の時、この記法を採用している関数電卓を初めて触って、本気で壊れたかと思いましたよ。 あ、やっぱりそうですか。でも、今回の分析を通して、この一見すると奇妙な記法の裏に隠された、なんていうか、コンピューターの思考法を解き明かしていきたいなと。 いいですね。なんだか知的なパズルを解いていくような、そんな時間になりそうです。まさに。人間には読みにくい。それはもう紛れもない事実です。 でも実はこれ、コンピューターにとってはカッコがいらない魔法の書き方なんです。おお、カッコがいらない魔法の書き方。そのキーワード、すごく惹かれますね。 ええ、なぜこれが魔法なのか。その秘密を一緒に解き明かしていきましょう。ぜひお願いします。では早速その点から掘り下げていきましょうか。 最初の疑問として、なぜコンピューターはこんなに人間に優しくない記法を好むんでしょうか。それを理解するには、まず人間とコンピューターの式の見方の違いから。 式の見方。はい。例えばここに、かっこ1+2かっこかける3、という式があるとします。はい、ありますね。答えは9ですね、もちろん。 私たちは式全体をパッと見て、あ、カッコがある、だからこっちを先に計算するんだな、と瞬時に判断できます。まさにそこなんです。人間は全体を俯瞰して優先順位を見つけるのが得意なんですよ。 ええ。でもコンピューターって基本そういうのが苦手で、彼らは非常に素直で、なんていうか、愚直な働き者なんです。ほうほう。 できることなら、式の左から右へ何も考えずにただ順番に処理していきたい。それが彼らの理想なんです。 ということはカッコがあると、えっと、どこからどこまでがカッコの範囲だっけ、ってまず認識して、その部分の計算を一旦保留して、中の計算が終わったら元の流れに戻ってきて、みたいな。 そうなんです。それがコンピューターにとって、まあ、余計な一手間、ってことですか。そういうことなんです。その余計な一手間をなくすための、すごい工夫が、この逆ポーランド記法なんですね。 なるほど。先ほどの式を逆ポーランド記法に変換すると、1 2 + 3 * になります。わ、やっぱり不思議な並び順だ。1 2 + 3 *。 確かにこれなら左から順番に読んでいけそうですけど、これを書かされる人間からすると、デバッグとかものすごく大変そうですね。あー、鋭い指摘ですね。その通りで。 人間がこれを直接書くのは現実的じゃないです。だからこそ、人間が書いた式を、プログラムがコンピューターのために自動で1 2 + 3 * に翻訳してあげてるんです。 あ、翻訳。ええ。この形にさえなってしまえば、コンピューターは驚くほど楽ができる。左から順番に見ていくだけで、カッコも優先順位も、もう一切気にしなくてよくなりますから。 なるほど、仕組みが見えてきました。となると、次の疑問はもう当然そこですよね。はい。一体どうやって1+2かける3を1 2 + 3 * に変換してるんでしょうか。 ここが一番のパズルに思えます。ええ、まさにそこが核心です。そして、この変換パズルを解くための非常にエレガントなツールがあるんです。ほう。それが式の木、演算木と呼ばれるものです。 式の木ですか。はい。数式をですね、木の枝が分かれていくような図で表現するんです。作り方はすごくシンプルですよ。ええ。 まず、計算の中で一番最後に行う演算子を、根、ま、つまり親と考えます。一番最後。今回の場合だと、最後に計算するのはかけるですよね。 ということは、このかけるが一番上の親になると。その通りです。まず一番上にかけるを置きます。そして、そのかけるから左と右に枝を伸ばすんですね。 左側の子が1+2という塊で、右側の子が3になります。はいはい。でも、まだ左側が1+2という式のままなので、これもさらに分解できるわけです。 なるほど。1+2の中心はプラスだから、今度はプラスを親にして、そこから左に1、右に2という子をぶら下げる。これで完成ですか。 完璧です。まさにその通り。一番上にかけるがいて、その左下にプラス、その下に1と2、かけるの右下に3がぶら下がっている。そんな構造ですね。 ふむふむ。この木が完成すれば、あとはもう魔法のように答えが出てきます。ここからが、すごく面白いところですよ。ぜひその魔法を教えてください。 ルールはたった一つです。ズバリ、左の子、右の子、親の順番で、この木を散歩するだけ。左、右、親、ですか。 これだけです。専門用語だと後行順とかポストオーダーなんて言ったりしますね。なるほど。じゃあまず1+2の小さな木で試してみますね。 えーっと、親がプラス、左の子が1、右の子が2。はい。ルールに従うと、まず左の子、次に右の子、最後に親に戻ってくる。あ、本当だ。1 2 プラスになりました。 なりましたよ。うわ、これちょっとしたアハ体験ですね。気持ちいい。ええ、ではさっきの式の、もう少し複雑な木でも同じルールで辿ってみましょうか。 はい。まず一番上の親、かけるからスタートします。左、右、親のルールなので、最初にどこへ行きますか。まずは左の子、プラスが親になっているエリアに行きます。 素晴らしい。そしてそのプラスの木の中でも同じルールが適用されます。左、右、親なので、まず1に行って、次に2、最後にプラスに戻る。これで1 2 プラスができますね。 その通りです。これで大元のカケルから見て、左側の子の散歩が終わりました。はい。ルールは左、右、親でしたから、次に辿るのは。 左が終わったので、次は右ですね。右の子は3だけなので、そのまま3に行きます。正解です。そして左も右も回り終えたので、最後にどこに戻りますか。 最後に一番上の大親分であるカケルに戻ります。辿った順番を全部繋げると、1 2 プラス 3 カケル、つまり1 2 + 3 * になりました。パズルが解けましたね。 このように、どんなに複雑な式でも、一度この式の木にしてしまえば、あとは機械的に、左、右、親、と辿るだけで、誰でも正確に逆ポーランド記法に変換できるんです。 いやー、これ面白い。さて、作り方は分かりました。では本丸です。コンピューターはどうやって計算するのか。試験で問われるのはまさにここですよね。 はい。ここが最も重要なポイントです。そして登場するのがスタックというデータ構造です。お皿を積み重ねるようなイメージの、あれですね。 ええ。後から入ったものが先に出てくる、後入れ先出しの仕組みです。はい、覚えています。逆ポーランド記法の計算ルールは、このスタックを使うと驚くほどシンプルになるんです。 ルールはたったの2つだけ。1つ目、数字が来たらスタックに積む、プッシュ。2つ目、演算子が来たら2つ取り出し計算してまた積む。たったこれだけです。 シンプルですね。ではまず実演してみましょう。式の左から見ていきます。最初に1が来ました。これは数字なのでルール1ですね。 空のスタックに積みます。まず1が一番下に入ります。はい。次は2。これも数字です。これもスタックに積みます。1の上にそっと2が乗っかるイメージ。 いいですね、その物理的なイメージ。これでスタックには下から1、2と積み重なりました。そして次にやってくるのがプラス。これが合図です。演算子プラスが来ました。 ルール2。演算子が来たらスタックから2つ取り出す。スタックの一番上にある2を取り出して、次に1を取り出します。はい。そして足す。1＋2で3。 結果をまたスタックに積むので、この3を今空になったスタックに戻します。これで式は全部読み終わりました。最後に残っているもの、それが最終結果です。 左から順番に処理して、最後に3という答えが残る。あ、その感覚はすごく大事です。まるで計算のプロセスを音で再現してるみたいで。ええ、その通りです。 では試験対策として、もう少し複雑な例題にも挑戦してみましょう。お願いします。例えば、かっこ5＋3かっこかけるかっこ8ー2かっこという式です。 うわ、やりごたえがありそうですね。まず、これを逆ポーランド記法に変換しないといけない。さっきの式の木を使えばいいんですね。 一番最後はかけるなので親。左の子が5＋3の塊、右の子が8ー2の塊。それぞれを分解すると、答えは 5 3 プラス 8 2 マイナス かける、になりますか。 大正解です。見事ですね。よかった。では、この 5 3 プラス 8 2 マイナス かけるを、スタックのルールで計算していきましょう。 はい。まず左から5が来たので積む。次に3が来たので5の上に積む。スタックは下から5、3です。次はプラスです。演算子なので2つ取り出す。 3と5を取り出して足します。5＋3で8。この結果をスタックに戻します。今スタックには8だけが入ってる状態。順調ですね。続けていきましょう。 次は8が来ます。数字の8なので積む。さっきの8の上に新しい8が乗る形ですね。はい。次に2が来たのでこれも積む。スタックは下から8、8、2です。 そして次にやってくるのがマイナス。引き算の演算子です。ここで注意したいのは取り出す順番ですね。ああ、そうか。後から入った2が先に、その次に8が出てきます。 なるほど。つまり先にあった8から、後から取り出した2を引く。8ー2という計算になるわけですね。もし順番が逆だと2ー8で答えが変わっちゃいますもんね。 まさにそこが重要なポイントです。8ー2で答えは6。これをスタックに戻します。スタックの中は、一番下にあった8と、今計算した6になりました。 あと一息です。最後に残っているのは？ええ、最後の演算子、かけるです。スタックから6と8を取り出して掛け合わせます。8かける6で48。これを戻します。 はい。これで式は全部終わり。スタックには48だけが残りました。かっこ5＋3が8、かっこ8ー2が6、8かける6は48。合ってます。同じルールで解けますね。 ええ。この機械的でシンプルなルールこそが、コンピューターがこの方法を好む理由なんです。ただの試験用のパズルじゃなくて、実用的な技術なんだって気がしてきます。 あ、いいですね。実際に現実の世界ではどこかで使われてたりするんですか。もちろん。実はこの考え方って、コンピューターサイエンスの様々な場面で生きてるんですよ。 へえ。例えばフォースとかポストスクリプトとかは、このスタックを基本とした逆ポーランド記法で命令を処理します。ポストスクリプト。ええ。 特にポストスクリプトはPDFファイルの内部で、図形とか文字を描画するための言語として、今でも広く使われてるんです。PDFの裏側でこれが動いてるんですか。 そうなんですよ。ですからPDFを見ている時、その裏ではコンピューターがスタックを使って健気に計算を続けているんだな、なんて思ってみるのも面白いかもしれません。 なるほど。そして試験対策として絶対に知っておくべき、もう一つの重要なことが。これまで逆ポーランド記法と呼んできましたけど、試験では別の名前で問われるんです。 別の名前。その名称が後置記法。演算子が数字の後に置かれる記法だから後置記法。1 2 プラスはまさに演算子が後ろにありますもんね。その通りです。 これは名前の由来が分かるとすごく覚えやすいです。試験では後置記法で書かれた式の値はどれか、と問われることもあります。二つが同じものを指していると理解しておくのが重要です。 了解しました。逆ポーランド記法イコール後置記法。これはもうセットで覚えておきます。さて、今回の分析を振り返ってみましょうか。最初は本当に奇妙に思えました。 コンピューターにとってはカッコが不要で、すごく効率的な書き方だということが分かりました。変換するためには式の木を使って、左の子、右の子、親、という順番で辿ればいい。 そして計算する際には、スタックを使って、数字は積む、演算子は2つ取り出して計算して戻す。あのシンプルなルールでどんな複雑な式でも解けることも体験できました。 人間の直感には反するように見えても、その裏側にはコンピューターが効率的に計算するための、非常に美しくて洗練されたロジックが隠されているんです。 一見複雑そうなものでも、その背景にあるルールとか目的を理解すると、途端にシンプルで美しいものに見えてきますね。まさに。今回は後置記法を扱いました。 ここで一つ面白い問いが生まれるんですよ。ほう。といいますと。もし演算子を式の前に置いたらどうなるでしょう？前ですか。ええ。例えばプラス 1 2 のようにです。 これは前置記法、あるいはポーランド記法と呼ばれます。へえ。式の木で言うと、親、左、右の順で辿るとこの形になるんですね。 さて、コンピューターはこの新しいパズルをスタックを使って一体どう解くと思いますか？うわー、どうなるんだろう。これもまた興味深い思考の体操になりますよ。