P67 - 二叉树的括号字符串表示
A string representation of binary trees
官方模块：
Problems.P67核心函数：treeToString、stringToTree
编码规则
叶子只写字符；非叶节点写成 根(左,右)；空子树写为空串。例如 a(b(d,e),c(,f(g,)))。
实现
方法一：手写递归下降
1treeToString :: Tree Char -> String
2treeToString Empty = ""
3treeToString (Branch c Empty Empty) = [c]
4treeToString (Branch c left right) =
5 c : '(' : treeToString left ++ "," ++ treeToString right ++ ")"
6
7stringToTree :: String -> Maybe (Tree Char)
8stringToTree "" = Just Empty
9stringToTree input = do
10 (tree, rest) <- parseTree input
11 if null rest then Just tree else Nothing
12
13parseTree :: String -> Maybe (Tree Char, String)
14parseTree [] = Nothing
15parseTree (c:'(':rest) = do
16 (left, afterLeft) <- parseOptional rest
17 (right, afterRight) <- case afterLeft of
18 ',':xs -> parseOptional xs
19 _ -> Nothing
20 case afterRight of
21 ')':xs -> Just (Branch c left right, xs)
22 _ -> Nothing
23parseTree (c:rest) = Just (leaf c, rest)
24
25parseOptional :: String -> Maybe (Tree Char, String)
26parseOptional input@(',':_) = Just (Empty, input)
27parseOptional input@(')':_) = Just (Empty, input)
28parseOptional input = parseTree input
编码直接跟随树结构，解析器则显式返回尚未消费的字符串。
方法二：差异列表 + ReadP
1import Text.ParserCombinators.ReadP
2
3treeToStringDL :: Tree Char -> String
4treeToStringDL tree = build tree ""
5 where
6 build Empty = id
7 build (Branch c Empty Empty) = (c :)
8 build (Branch c left right) =
9 (c :) . ('(' :) . build left . (',' :) . build right . (')' :)
10
11stringToTreeReadP :: String -> Maybe (Tree Char)
12stringToTreeReadP input = case
13 [tree | (tree, "") <- readP_to_S (treeParser <* eof) input] of
14 [] -> Nothing
15 trees -> Just (last trees)
16
17treeParser :: ReadP (Tree Char)
18treeParser = do
19 c <- satisfy (`notElem` "(),")
20 (do
21 char '('
22 left <- optionalTree ','
23 char ','
24 right <- optionalTree ')'
25 char ')'
26 pure (Branch c left right))
27 <++ pure (leaf c)
28
29optionalTree :: Char -> ReadP (Tree Char)
30optionalTree delimiter = do
31 remaining <- look
32 if not (null remaining) && head remaining == delimiter
33 then pure Empty
34 else treeParser
差异列表版本通过函数组合构造字符串，不反复复制左侧前缀；ReadP 版本则把分隔符、选择和输入结束检查交给标准解析组合子。
方法对比
| 方法 | 编码 | 解码 |
|---|---|---|
| 手写递归 | 直接使用 ++ | 显式传递剩余输入 |
差异列表 + ReadP | 函数组合 | 标准解析组合子 |
测试
1>>> treeToString tree1
2"a(b(d,e),c(,f(g,)))"
3>>> stringToTree (treeToString tree1) == Just tree1
4True
5>>> stringToTree "a(b,c"
6Nothing
7>>> treeToStringDL tree1 == treeToString tree1
8True
9>>> stringToTreeReadP (treeToString tree1) == Just tree1
10True
解析函数同时返回未消费后缀，顶层只接受后缀为空的结果，从而拒绝尾随垃圾字符。