逆ポーランド記法について

「後置記法」とも呼ばれる．
式を表現する場合，被演算子を最初に列挙し，演算子を最後に記述する表現形式．
通常の演算子を真中に記述する形式は「中置記法」と呼ばれる．
例

中置記法逆ポーランド記法

a+b ab+

a+b-c ab+c-

a*(b+c) abc+*

(a+b)/(c-d) ab+cd-/
上記例でわかるように， 逆ポーランド記法は計算機に計算を指示する場合に都合が良い． その理由は，
1. 式を前から順番に読み，それをスタックに積んでゆく．
2. もし，演算子を読んだら，その演算に必要な被演算子(引数) をスタックから取りだし，演算を行う．
3. 演算結果をスタックに返す．
という単純な処理で計算を進めることができるからである．
```
3*(2+1)の逆ポーランド計算例

逆ポーランドに変換: 321+*

スタック[]      式の読み残り 321+*
スタック[3]     式の読み残り 21+*
スタック[3 2]   式の読み残り 1+*
スタック[3 2 1] 式の読み残り +*
スタック[3 3]   式の読み残り *     (+を読んで2引数なので2つ値をとり2+1を計算)
スタック[9]     式の読み残り       (*を読んで2引数なので2つ値をとり3*3を計算)
```
通常のレジスタ等を用いて計算を行う計算機の計算メカニズムには，ぴったりとはマッチしないが，式の評価を抽象的に考えるには良い機構である．
数値演算に限らず， 一般的な関数呼び出しについても同様に扱うことができる．
参考文献: コンパイラの解説本ならどれでも．例えば，
など．

中置記法	逆ポーランド記法
`a+b`	`ab+`
`a+b-c`	`ab+c-`
*`a(b+c)`**	*`abc+`**
`(a+b)/(c-d)`	`ab+cd-/`

$Id: rpolish.html,v 1.3 2000-05-19 09:19:12+09 kaiya Exp kaiya $