逆ポーランド記法および、ツリーの preoder/postoder traversal

今日、もうすぐ廃刊になるかわいそうなCマガジンを電車の中で読みながら
ぼーっと考えていたら、ふと逆ポーランド記法の記事が目に入ってきた。
曰く、Infixで書かれた数式を計算するのは難しくて、
逆ポーランド記法で書かれたものなら簡単だということだ。
Infixだと優先順位の処理とかが大変で(…本当か？)
逆ポーランド記法ならスタックを用意するだけで計算ができて、
いずれにせよ簡単だということなのだが、
ちょちょちょ、、、ちょっと待てよ？
逆ポーランド記法だとスタックで計算ができるって自明なのか？
少なくとも私は今までずっと、”そういうもん”だと思ってきて、
よく考えたことが無かった。

逆ポーランド記法とは言い換えると
計算式をツリーで表現したときのpostoder traversalということで、
これをスタックで計算できるということは、
前からスキャンすることにより、確定的に、線形オーダで、
元のツリーが復元できるということになる。
計算式のツリーは二分木で、リーフが数、ノードがオペレータと決まっている。
トークン列中、オペレータが出現すると、
それよりも前に二つ以上のツリーをあらわす列が必ず存在しており、
そのツリーがリーフのみなら数字で、
そうでなければオペレータ終端のトークン列であるはずである。
オペレータ終端の列はさらにそこでツリーを構成しているはずで、
そうならば、トークン列を前から見ていく途中で、
構成できるツリーを全てリダクション(ここでは単一の数字にするとする)するとすると、
結局、各オペレータの出現において、必ずその前に二つの数字が現れることになり、
そのオペレータが構成するツリーはそのオペレータをルートに、
直前二つの数を子に持つツリーでしかありえない。
そういうわけで、確かに逆ポーランド記法を前から見ていくことにより
確定的に線形オーダで一意にツリーが構成可能である。

と、これだけではいまさらながらに逆ポーランド記法の仕組みを理解したに過ぎないが、
実はこのことはもっと一般的に応用できるような気がする。
先の説明をきわめて一般的な言い方をすれば、
ある隣接三トークンを見て、それが確実にツリーをなすということができるような
規則が有るとすれば、そのようなツリーのpostoder traversalが与えられたら、
それを前から見ていき、リダクションできるところを発見し次第リダクションすれば、
確定的に一意に線形オーダで復元可能、ということになる。
そしてこれはスタックを用いて簡単に実装可能である。
また逆にpreoder traversalが与えられたら、
今度は後ろから見ていくことにより同様にツリーが復元できる。

(これは微妙にこのまえの合宿でやった問題に絡んでいるが…)
ツリーのpreoder traversalが与えられたら後ろから見ていくとか、
これはかなり定石になるのではなかろうか。
あるいはこれは有名なことだったりするんだろうか。
ともかく、これからツリーの問題が来たら、
これが適用できないか考えてみても良いと思った。
それに気付かせてくれたCマガジンに感謝…。