2.プログラムで表現
数式を木構造に変換するプログラムをHaskellで実現する。数式が木構造に変換される様子をもう一度、図で示すと次のようになる。
複雑すぎて、Javaで実現しようとは思わない。直感的にHaskellでも苦労するかなと想像したが、取り越し苦労であった。数式から木構造への変換の様子をまとめると次のようになる。
①値が来たときは、木構造の右隅にあるEmptyを値で変える。
②加算が来たときは、加算のノードを作成し、これまでのTreeをその左側のノードに、右側にはEmptyのリーフをつける。
③乗算が来たときは、木構造の右隅にある値のところに、乗算のノードを作成し、これまでの値をその左側のノードに、右側にはEmptyのリーフをつける。
まず、型の定義から始める。ノードでの演算Opと、木構造Treeを代数的データ型(dataでの定義)を用いて次のように定義する。
data Op = Plus | Mult deriving (Eq, Ord, Show) data Tree = Empty | Leaf Int | Node Op Tree Tree deriving (Eq, Show)
OpではPlus,Multはそれぞれ加算と乗算である。Treeは再帰で定義した。Emptyは特別なリーフで何も入っていない。通常のリーフはLeaf Intで定義され、値は整数である。ノードはNode Op Tree Treeで定義され、Treeを再帰的に読んでいる。
つぎに、数式から木構造を作り出すプログラムは次の通りである。なお、ここでの数式に用いることができる値はプログラムの説明を簡単にするために1から9までの整数とした。また、数式は、スペースなしの値と演算だけで記述される文字列で与える。例えば、"3*4+5*6"である。
expr :: String -> Tree -> Tree expr [] tree = tree expr (x:xs) tree | x >= '1' && x <= '9' = expr xs $ number x tree | x == '+' = expr xs $ plus tree | x == '*' = expr xs $ mult tree | otherwise = tree
expr [] tree は式を全て読みつくしたら、生成された木構造treeを返す。
expr (x:xs) treeは処理途中の数式の先頭(すなわちもっとも左側にある文字)を取り出し、値、演算+,*に分けて処理を行う。これらの処理は再帰的で、それらの処理で返されてきた木構造を残りの文字列に対する木構造への変換に利用している。
次にこれらの処理について述べる。簡単なところから、加算が来た時のプログラムは次の通りである。
plus :: Tree -> Tree plus tree = Node Plus tree Empty
変換への仕様に応えて、新しい加算のノードを作成し、これまでのTreeをその左側のノードに、右側にはEmptyのリーフをつけていることがわかる。
値が来たときは、次のようになる。
number :: Char -> Tree -> Tree number x Empty = Leaf $ digitToInt x number x (Node op t1 t2) | t2 == Empty = Node op t1 (Leaf $ digitToInt x) | otherwise = Node op t1 $ number x t2
変換への仕様に応えて、木構造の右隅にあるEmptyを値で変えていることがわかる。なお、digitToIntは文字を数値に変える関数である。これを用いるときは、次のモジュールをロードしておくこと。
import Data.Char import Data.List
乗算が来たときは、次のようになる。
mult :: Tree -> Tree mult (Leaf t2) = Node Mult (Leaf t2) Empty mult (Node op t1 t2) = Node op t1 $ mult t2
変換への仕様に応えて、木構造の右隅にある値t2のところに、乗算のノードを作成し、これまでの値t2をその左側のノードに、右側にはEmptyのリーフをつけていることがわかる。
プログラムは、間違った数式も含めて確かめてみるとよい。例えば、次のようにする。
test1 = expr "3+4" Empty test2 = expr "3*4" Empty test3 = expr "2*3+4*5" Empty test4 = expr "2+3*4*5+6*7" Empty test5 = expr "3++4" Empty test6 = expr "3+*5" Empty test7 = expr "3+45" Empty
2.プログラム全体
プログラム全体は次のようになる。
import Data.Char import Data.List data Op = Plus | Mult deriving (Eq, Ord, Show) data Tree = Empty | Leaf Int | Node Op Tree Tree deriving (Eq, Show) expr :: String -> Tree -> Tree expr [] tree = tree expr (x:xs) tree | x >= '1' && x <= '9' = expr xs $ number x tree | x == '+' = expr xs $ plus tree | x == '*' = expr xs $ mult tree | otherwise = tree number :: Char -> Tree -> Tree number x Empty = Leaf $ digitToInt x number x (Node op t1 t2) | t2 == Empty = Node op t1 (Leaf $ digitToInt x) | otherwise = Node op t1 $ number x t2 mult :: Tree -> Tree mult (Leaf t2) = Node Mult (Leaf t2) Empty mult (Node op t1 t2) = Node op t1 $ mult t2
何ともあっさりと解決で、少し、調子抜けである。プログラムを簡単にしているのは、再帰的な処理と、パターン照合である。
3.課題1
数式から木構造への次の仕様が正しいことを示しなさい。
①値が来たときは、木構造の右隅にあるEmptyを値で変える。
②加算が来たときは、加算のノードを作成し、これまでのTreeをその左側のノードに、右側にはEmptyのリーフをつける。
③乗算が来たときは、木構造の右隅にある値のところに、乗算のノードを作成し、これまでの値をその左側のノードに、右側にはEmptyのリーフをつける。
4.課題2
数式にカッコを許した場合、仕様はどのようになるかを記述しなさい。
5.課題2
上記の仕様に基づき、プログラムを作成しなさい。