P70 - 多路树的节点串表示
Construct a multiway tree from a node string
官方模块：
Problems.P70核心函数：stringToMultitree、multitreeToString
数据结构与编码
多路树不能为空，每个节点保存任意数量的子树。深度优先输出节点字符，每次回退到父节点时输出 ^，包括从根退出。
1data MultiwayTree a = MultiwayTree a [MultiwayTree a]
2 deriving (Eq, Show)
3
4multitreeToString :: MultiwayTree Char -> String
5multitreeToString (MultiwayTree x children) =
6 x : concatMap multitreeToString children ++ "^"
解析
方法一：递归下降
1stringToMultitree :: String -> Maybe (MultiwayTree Char)
2stringToMultitree input = do
3 (tree, rest) <- parseNode input
4 if null rest then Just tree else Nothing
5
6parseNode :: String -> Maybe (MultiwayTree Char, String)
7parseNode [] = Nothing
8parseNode ('^':_) = Nothing
9parseNode (x:rest) = do
10 (children, remaining) <- parseChildren rest
11 pure (MultiwayTree x children, remaining)
12
13parseChildren :: String -> Maybe ([MultiwayTree Char], String)
14parseChildren [] = Nothing
15parseChildren ('^':rest) = Just ([], rest)
16parseChildren input = do
17 (child, afterChild) <- parseNode input
18 (siblings, rest) <- parseChildren afterChild
19 pure (child : siblings, rest)
方法二：显式节点栈
1import Control.Monad (foldM)
2
3stringToMultitreeStack :: String -> Maybe (MultiwayTree Char)
4stringToMultitreeStack input = do
5 (frames, result) <- foldM step ([], Nothing) input
6 case (frames, result) of
7 ([], Just tree) -> Just tree
8 _ -> Nothing
9 where
10 step (_, Just _) _ = Nothing
11 step (frames, Nothing) '^' = close frames
12 step (frames, Nothing) value =
13 Just ((value, []) : frames, Nothing)
14
15 close [] = Nothing
16 close [(value, reversedChildren)] =
17 Just ([], Just (MultiwayTree value (reverse reversedChildren)))
18 close ((value, reversedChildren):(parent, siblings):rest) =
19 let child = MultiwayTree value (reverse reversedChildren)
20 in Just ((parent, child : siblings) : rest, Nothing)
21
22multitreeToStringDL :: MultiwayTree Char -> String
23multitreeToStringDL tree = build tree ""
24 where
25 build (MultiwayTree value children) =
26 (value :) . foldr ((.) . build) id children . ('^' :)
普通字符把新节点框架压栈，^ 关闭栈顶节点并把它接到父节点。根节点关闭后不得再出现字符。编码的差异列表版本同样只用函数组合追加内容。
方法对比
| 方法 | 解析结构 | 特点 |
|---|---|---|
| 递归下降 | 调用栈对应树层级 | 与文法直接对应 |
| 显式节点栈 | 框架保存尚未关闭的节点 | 单次 fold，状态清晰 |
测试
1>>> multitreeToString multitree5
2"afg^^c^bd^e^^^"
3>>> stringToMultitree "afg^^c^bd^e^^^" == Just multitree5
4True
5>>> stringToMultitree "a^junk"
6Nothing
7>>> stringToMultitreeStack (multitreeToString multitree5) == Just multitree5
8True
9>>> multitreeToStringDL multitree5 == multitreeToString multitree5
10True
编码和解析都线性访问字符串，时间复杂度 。