逆ポーランド記法と聞きますと、じゃあ順ポーランド記法というのがあるのかなと思います。それは関数形式の書き方ではないでしょうか。たとえば2+3は+(2,3)と書きます。3*4は*(3,4)という感じです。すると、2+3*4は+(2,*(3,4))となり、(2+3)*4は*(+(2,3),4)となります。

この書き方だとかっこを使わなくても2+3*4と(2+3)*4を区別できますので、カッコを外して+2*34と*+234でも良いのです。

そこで、関数形式の最初に書いた演算子を最後に持ってくると、逆ポーランド記法となります。つまり、2+3は23+となり、3*4は34*となるわけです。2+3*4は(2,(3,4)*)+ですからカッコを外すと234*+となります。(2+3)*4は((2,3)+,4)*ですから、23+4*となります。

通常の書き方をinfix notationと言いますが、そこでは2+3*4の場合には後に書いてある3*4を先に計算する必要があり、コンピュータにやらせるのはしんどいのです。逆ポーランドでは次の手順によれば、書いてある順番に実行するだけなのでコーディングが容易になります。それはスタックを使った計算方法です。

　・数値などのオペランドが現れたら、スタックにプッシュする

　・掛け算や足し算などの演算子が現れたら必要なだけポップして結果をプッシュする

実に簡単明瞭ですね。これはK&Rに書いてありました。いやあ、実に素晴らしいテキストですね。それでは、具体的な使い方について、書いていきます。コンパイラつくりの話では、通常のinfix notatinで書かれた計算式を逆ポーランド記法に変換するというところから始まります。

…とりあえず、ここまで。