2006-07-12  ウィスパー3―その3―

だんだんと小難しい話しになってきました。廃刊になったOh!Xに載っていそうな内容になってきましたが，気にしないでください。

式の表現

前回は字句解析と構文解析により，式を表す文字列を因子（＜英＞factor）に分解しました。もちろん，ただバラバラにしただけではだめです。コンピュータで「式」として扱えるように，なんらかの決まりに則ってデータを格納しなければなりません。

今回は2分木で式を表すことにしました。この方法は定番中の定番です。ちょっと厚めのアルゴリズムの教科書になら，必ず載っています。

＜画像の説明＞A+B-C*D（後置記法ではAB+CD*-）の2分木表現。

本来なら2分木の性質や，木を組み立てる前に中置記法で表した式を後置記法に変換する方法にも触れた方がよいのでしょうけれど，細かな説明は省略することにします。業界の人であればだいたい察しが付くはずなのと，目眩がしそうな話しなのでやっぱり触れないでおきます。

BNodeクラスとFactorクラス

データ構造のお話しです。今回は2分木を表すためにBNodeクラスを導入しました（BNodeのBにはBinaryという意味を込めています）。また因子を表現するためにFactorクラスを導入しました。

BNodeクラスならびにFactorクラスには，等価判定とオブジェクトをコピーするための便利なメソッドを付けました。「妙にJavaっぽいな。実装はPerlなんですよね？」と思った人がいるかもしれません。それは何かの錯覚でしょう（ふめい）。

＜画像の説明＞クラスの定義のようなものです。Microsoft Visioでちょこちょこっと描いてみました。

余談ですが，BNodeのvalueはFactorオブジェクトでなければなりません。クラス間の結びつきが強すぎるのかなと思いましたが，BNodeは汎用的なクラスではないので今回は「良し」としました。

宿題の進み具合

• 式を最適化する ― それらしいものができていますが，停止性の検証がまだ。再帰処理を使ったのですが非再帰に書き換えるつもりです。次回，詳しくお話するつもりです。難易度は高めでした
• 式をSQLに展開する ― それらしいものができています
• 日付時刻の範囲を表すクラス ― まだ調査していません