blob: 741795ba6db2738bb003f7875c1474dacd5705be (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
stringToTree :: Monad m => [Char] -> m (Tree Char)
stringToTree "" = return (Empty)
stringToTree [x] = return (Branch x Empty Empty)
stringToTree x = fmap fst $ parse x
where parse (x:xs)
| x == ',' || x == ')' = return (Empty, x:xs)
parse (x:y:xs)
| y == ',' || y == ')' = return (Branch x Empty Empty, y:xs)
| y == '(' = do (lt, ',':xs') <- parse xs
(rt, ')':xs'') <- parse xs'
return (Branch x lt rt, xs'')
parse _ = fail "parse error"
treeToPreorder :: Tree Char -> [Char]
treeToPreorder Empty = ""
treeToPreorder (Branch x l r) = x:treeToPreorder l ++ treeToPreorder r
treeToInorder :: Tree Char -> [Char]
treeToInorder Empty = ""
treeToInorder (Branch x l r) = treeToInorder l ++ [x] ++ treeToInorder r
preInTree :: Monad m => [Char] -> [Char] -> m (Tree Char)
preInTree [] [] = return Empty
preInTree (p:ps) is = do let (lis, _:ris) = break (== p) is
(lps, rps) = splitAt (length lis) ps
lt <- preInTree lps lis
rt <- preInTree rps ris
return $ Branch p lt rt
preInTree _ _ = fail "error"
|