１．木構造
数式は見慣れているため、簡単に理解できるように訓練されてはいるが、それでも、少し込み入ってくると、どのように計算したらよいか困るときがある。そのような時、木構造で描くとわかりやすくなる。3*4+5*6を木構造で表すと下図のようになる。
木構造は、一般に、ノード(枝)とリーフ(葉)で構成されている。ノードは、ノードあるいはリーフに繋がっている。リーフは末端である。ここでは、数式を次のように表している。ノードは演算を表し、リーフは値となっている。ノードでの値は、その下にあるノードあるいはリーフの値をノードでの演算に従って計算したものである。上の図では、乗算のノードはその下にある二つのリーフの値を掛け合わせて、加算のノードは二つの乗算ノードでの計算結果を足し合わせて、値を得る。
次に、数式が与えられた時、数式を左から右の方に読んでいったときに、木構造がどのように作成されるかを示したのが、下の図である。
最初は、Emptyのリーフが作られる。最初の値３が読み込まれると、Emptyが３のリーフに代わる。次に*を読み込むと、リーフ３が、新しい乗算ノードに代わり、その左側のリーフはリーフ３、その右側のリーフはEmptyのリーフとなる。値４が読み込まれると、Emptyが４のリーフに代わる。
さらに、+を読み込むと、新しい加算のノードが作られ、その左側のノードは先ほどの乗算のノードに、その右側にはEmptyのリーフが作れれる。このような操作を続けることで、数式を読み終わると最初に示した木構造の図が得られる。
