逆ポーランド記法をネタにGIFアニメ作りたかっただけです。

演算子の優先順位

四則演算では加減算より乗除算のほうが優先順位が高い。例えば、下記の通り乗除算を先に評価すると解釈するのが一般的である。

1 ＋ 2 × 3であれば、1 ＋ (2 × 3) = 1 + 6 = 7と解釈される。
12 − 8 ÷ 4であれば、12 − (8 ÷ 4) = 12 - 2 = 10と解釈される。

演算子の結合性

また、四則演算は左結合である。例えば、下記の通り左側から結合して考えるのが一般的である。（減算が連続した場合や、除算が連続した場合に左結合でないと困ったことになる。結合法則を満たす加算や乗算は、右結合と解釈しても問題はない。）

9 - 3 - 1 + 6であれば、((9 - 3) - 1) + 6 = (6 - 1) + 6 = 5 + 6 = 11と解釈される。
16 ÷ 4 ÷ 2 × 3であれば、((16 ÷ 4) ÷ 2) × 3 = (4 ÷ 2) × 3 = 2 × 3 = 6と解釈される。

なお、べき乗は通常右結合と考える。

括弧の入れ子と木構造

演算子の優先順位や結合性により、四則演算の式は解釈されていく。そのため、優先順位や結合性に沿わない順序で計算したい場合、括弧によって計算順序を示す必要がある。例えば下記の式は、括弧があることにより除算より先に減算が計算される

3 + 4 × 2 ÷ (1 - 5)は3 + 8 ÷ (-4) = 3 + (-2) = 1のような順序で計算される。

上式3 + 4 × 2 ÷ (1 - 5)に対して演算子の優先順位や結合性を明示的に示すように括弧をつけると下記のようになる。

((3) + (((4) × (2)) ÷ ((1) - (5))))

括弧の入れ子だらけでぱっと見よくわからないので、木に変形して見やすくする。

まず、最も外側の括弧に注目し、それに対応する演算子（＋）を持ち上げる。

（＋）の左側の子は（３）であり、括弧の入れ子はないためそのままにする。（＋）の右側の子には括弧の入れ子があるので、最も外側の括弧に注目し、それに対応する演算子（÷）を持ち上げる。

同様にして、２つの演算子（×）（‐）を持ち上げると、入れ子が解除された木構造が現れる。

木構造の走査

式の正体が木であることは分かったが、普段、式は一列に書く。つまり、私たちは木の各頂点を一列に列挙するある方法を無意識に使っていることになる。その無意識的に行っている列挙を意識的に行ってみる。

具体的には木構造の走査の間順、前順、後順の走査を((3) + (((4) × (2)) ÷ ((1) - (5))))の木に対して実行する。

間順（中置記法）

もしあれば、左の部分木を間順走査する。

根ノードを調査する。

もしあれば、右の部分木を間順走査する。

を実行した結果が下記の図。

最終的な結果の((3) + (((4) × (2)) ÷ ((1) - (5))))は、私たちが普段使う書き方だが、これを中置記法と呼ぶ。つまり、式の木を間順で走査すると中置記法で書かれた式が得られる。そして私たちが無意識に使用している木の各頂点を一列に列挙する方法とはこの間順走査のことである。