99 questions/Solutions/69
Dotstring representation of binary trees.
We consider again binary trees with nodes that are identified by single lower-case letters, as in the example of problem P67. Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree (nil) is encountered during the tree traversal. For example, the tree shown in problem P67 is represented as 'abd..e..c.fg...'. First, try to establish a syntax (BNF or syntax diagrams) and then write a predicate tree_dotstring/2 which does the conversion in both directions. Use difference lists.
data Tree a = Empty | Branch a (Tree a) (Tree a) deriving (Show, Eq)
ds2tree [] = (Empty,"")
ds2tree ('.':xs) = (Empty,xs)
ds2tree (x:xs) = (Branch x left right, rest2)
where (left,rest) = ds2tree xs
(right,rest2) = ds2tree rest
tree2ds Empty = "."
tree2ds (Branch x l r) = x:(tree2ds l ++ tree2ds r)
The tree2ds function is straightforward: Empty trees become a dot, and non-empty trees become their label, with left and right trees appended.
ds2tree is a bit trickier because you have to know which part of the string belongs to which subtree. Ds2tree returns the part of the string that hasn't been consumed yet.
The following solution uses Parsec for 'dsToTree':
import Text.Parsec.String
import Text.Parsec hiding (Empty)
pTree :: Parser (Tree Char)
pTree = do
pBranch <|> pEmpty
pBranch = do
a <- letter
t0 <- pTree
t1 <- pTree
return $ Branch a t0 t1
pEmpty = do
char '.'
return Empty
dsToTree str =
case parse pTree "" str of
Right t -> t
Left e -> error (show e)