手作りネットプロトコル工房コミュの逆ポーランドから中置記法へ変換

今、自作のシステムで利用するための演算処理言語を設計しているのです。

演算処理言語自体は、人間が普通に読む「中置記法」という記法で記述しますが、処理を行う際は、中置記法のまま処理を行ってしまうと処理フローがとても煩雑になってしまうので、曖昧さが回避される「後置記法」で記述しなおしてから処理を行う必要があるのです。

＃記法とは、計算式の書き方のことです。ここでいう中置記法というのは、日ごろよく見かける計算式の書き方 1+1 というような書き方のことです。コレに対して「後置記法」というのは逆ポーランド記法とも呼ばれ、 1,1 + というように記号が後ろに来ます。この記法の大きな特色はカッコがなくても全ての計算方法を表現できる事です。数字と記号の順番だけで、正しい計算順序が全て表現できるのです。

http://tokuda-www.cs.titech.ac.jp/~tokuda/abstract.html

この後置記法の式を実際に計算するアルゴリズムは、大学などで課題として出されるようなとてもポピュラーな問題で、スタック計算機アルゴリズムと呼ばれる、方法を使うことでとてもシンプルで美しく実装できるのです。

... が、肝心の「中置記法」を「後置記法」に置き換えるアルゴリズムというのは、なかなかみかけないのです。

調べてみたのですが... ありました！ありましたよ！

http://montcs.bloomu.edu/~bobmon/Information/RPN/infix2rpn.shtml#algorithm
http://www.geocities.com/oosterwal/computer/infix2rpn.html
http://en.wikipedia.org/wiki/Shunting_yard_algorithm

「あなただけが出来る事だけをやりなさい」で有名なエズガーダイクストラが考えたアルゴリズムがあるんだそうです！さすが！

昨日からずっとそのことを考えていたのです。それで、スタック行列を２個使って、再帰的に処理する必要があるな... と思っていたのですが、それに近い事が書いてあったので、ちょっと嬉しい感じです。

しかし ... この事について日本語で説明されている文献って異常に少なくないですかね。プログラムを実際に書く段になれば、とても大切な事だと思うのですが...。プログラムを書かない人には無用でしょうが...。

余談：

英語のWIKI
http://en.wikipedia.org/wiki/Reverse_Polish_notation
http://en.wikipedia.org/wiki/Prefix_notation
http://en.wikipedia.org/wiki/Infix_notation

日本語のWIKI
http://ja.wikipedia.org/wiki/%E9%80%86%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
http://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%BC%E3%83%A9%E3%83%B3%E3%83%89%E8%A8%98%E6%B3%95
http://ja.wikipedia.org/wiki/%E4%B8%AD%E7%BD%AE%E8%A8%98%E6%B3%95

ホント、どうでもいいんですが、日本語の方は「逆ポーランドは日本語に似てる」とか「Mindという言語がある」とかぜんっっっぜん本質的じゃないところばかりに拘っているし(まそれは確かにそうなんですが)、そもそも、ほとんど英語の翻訳だし... なんかがっかりしちゃいます。

その点、英語の方は、本質的な点について、とてもよく考えている感じがします。

ここが日本がダメダメなところなんじゃないかと思います。少ない知識から自分の力で考える大切さをおろそかにし、考える事よりも知識を大量に持つこと自体に快楽を覚えてしまう。

討論すると、すぐ「お前はわかってない」「わかってないのはお前だ」戦争が勃発。コミュニケーション力の低さが露呈される。論で負けそうになると、すぐに知識の豊富さ勝負に持ち込みたがる。本当はどっちが論理的に合理性があるのかをあぶりだすための討論のはずなのに... すぐ勝ち負けにこだわるし...。

これじゃダメダメです。

何かこの話題になるとグチっぽくなってすみません。