将带括号的数字字符串转换为树

Question

我正在开发一个函数，将带括号的数字字符串转换为树。所以，举个例子，

treeFromString "((1)((3)(4)))" == Right (Nd (Lf 1) (Nd (Lf 3) (Lf 4)))

这是我的尝试。我假设一个格式良好的字符串来解决一个更简单的问题，但类型签名应该是

Either String (BinL' Int)

。

import Data.Char

data BinL' a = Lf a | Nd (BinL' a) (BinL' a) deriving Show

treeFromString :: String -> BinL' Int
treeFromString [] = undefined
treeFromString ('(':cs) = case span isDigit cs of
                            ("", remaining) -> treeFromString cs
                            (digits, remaining) -> Nd (Lf (read digits)) (treeFromString remaining)
                            

当传入的参数为空列表时，我应该返回什么值？

我的总体方法是否是实现我想要的目标的明智方法？

编辑：

有一个补充函数可以将树转换为带括号的字符串。我正在开发的功能应该执行相反的转换。示例：

showBinL' :: Show a => BinL' a -> String

showBinL' (Nd (Lf 1) (Nd (Lf 3) (Lf 4)))
"((1)((3)(4)))"

Answer 1

如果你不太关心效率，我推荐标准的初学者友好方法：

事物的解析器
是字符串的函数
到配对列表
事物和字符串。
——格雷厄姆·赫顿

而且，您很幸运：语言标准

Read

类将其解析器放入此框架中。

reads :: Read a => String -> [(a, String)]

因此，如果您正在构建能够顺利处理此类类型的机制，那么当您需要读取数字时，您可以干净地插入

reads

，事实上甚至可以从读取数字树推广到读取树任何

Read

实例。

所以这是我建议您首先尝试实现的类型。如果你必须有一个特定的类型，你可以在它周围写一个小包装器来转换。

treeFromString :: Read a => String -> [(BinL' a, String)]

一般情况下，如果字符串解析成功，结果列表将有一个元素，包含树和尚未解析的字符串的后缀（如果有）；如果解析失败，结果列表应该为空。

在你坐下来开始编写解析代码之前，首先尝试写下语法通常是一个好主意。这是我对合理语法的猜测：一棵树要么是一片叶子，在这种情况下它直接是该叶子的值，要么它是一个节点，在这种情况下它是被括号包围的两棵树。像这样：

T ::= '(' T T ')'
    | <leaf>

一个实施计划是构建一个小型解析器库，可以将它们组合起来生成此语法。我推荐以下套装：

• 解析器消耗单个字符，并且不返回任何有趣的数据。

  char :: Char -> String -> [((), String)]
  

• 一种对两个解析器进行排序的方法，即解析第一个事物，然后使用第一个解析器中的任何剩余文本来解析第二个事物。

  andThen :: (String -> [(a, String)])
          -> (String -> [(b, String)])
          -> (String -> [((a, b), String)])
  

• 一种交替使用两个解析器的方法，即在同一输入上尝试两个解析器，返回其中一个解析器给出的任何结果。

  orElse :: (String -> [(a, String)])
         -> (String -> [(b, String)])
         -> (String -> [(Either a b, String)])
  

• 一种在解析器成功时转换解析器返回的数据的方法。

  finally :: (String -> [(a, String)])
          -> (a -> b)
          -> (String -> [(b, String)])
  

有了这些，你可以直接将上面的语法音译成解析器：

t :: Read a => String -> [(a, String)]
-- T ::=       '('           T           T                ')'
t      = (char '(' `andThen` t `andThen` t `andThen` char ')' `finally` \(_, (l, (r, _))) -> Nd l r)
--     |         <leaf>
       `orElse` (reads `finally` Lf)