如何将自定义QA二叉树类型的字符串表示还原为原树结构

你序列化的字符串是规则明确的嵌套括号结构，用递归下降解析即可完成反序列化，以下是两种可直接运行的实现方案：

方案1：手写递归解析（无额外依赖） #

适合轻量场景，不需要引入第三方库：

-- 辅助函数：拆分平衡括号对，返回（括号内完整内容，括号外剩余字符串）
splitBalanced :: String -> (String, String)
splitBalanced s = go 0 0 s
  where
    go cnt pos [] = error "输入字符串括号不匹配"
    go cnt pos (x:xs)
      | x == '(' = go (cnt + 1) (pos + 1) xs
      | x == ')' = if cnt == 1 then (take pos s, drop (pos + 1) s) else go (cnt - 1) (pos + 1) xs
      | otherwise = go cnt (pos + 1) xs

-- 核心解析函数
parseQa :: String -> QA
parseQa s = let inner = init $ tail s -- 去掉当前节点首尾的括号
            in case break (== '(') inner of
                 -- 剩余内容无左括号，说明是Leaf节点
                 (content, "") -> Leaf content
                 -- 存在左括号，拆分问题文本、左右子树分别递归解析
                 (q, leftStr) ->
                   let (_, rightStr) = splitBalanced leftStr
                   in Question (parseQa leftStr) q (parseQa rightStr)

-- 读取文件并解析的完整入口
readQaFromFile :: FilePath -> IO QA
readQaFromFile path = do
  fileContent <- readFile path
  -- 自动去掉文件内容首尾的双引号
  let pureStr = read fileContent :: String
  return $ parseQa pureStr

方案2：Parsec库实现（更健壮） #

如果项目允许引入依赖，用Parsec写的解析器错误提示更友好，扩展性更强：

import Text.Parsec
import Text.Parsec.String (Parser)

qaParser :: Parser QA
qaParser = do
  char '('
  content <- many1 $ noneOf "()"
  -- 没有子节点则为Leaf，有子节点则为Question
  option (Leaf content) $ do
    left <- qaParser
    right <- qaParser
    char ')'
    return $ Question left content right

parseQaParsec :: String -> Either ParseError QA
parseQaParsec = parse qaParser ""

注意事项 #

如果QA的问题/回答文本本身包含括号，需要先修改原有showQa函数对内容中的括号做转义处理，否则会导致解析错误，当前示例没有这类特殊字符可直接运行上述代码。

内容的提问来源于stack exchange，提问作者TheDevWay