我是 Scala 的初学者,致力于 S99尝试学习Scala。问题之一涉及从字符串转换为树数据结构。我可以“手动”做到这一点,因为我还想看看如何使用 Scala 的解析器组合器库来做到这一点。
树的数据结构是
sealed abstract class Tree[+T]
case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T] {
override def toString = "T(" + value.toString + " " + left.toString + " " + right.toString + ")"
}
case object End extends Tree[Nothing] {
override def toString = "."
}
object Node {
def apply[T](value: T): Node[T] = Node(value, End, End)
}
输入应该是一个字符串,像这样:
a(b(d,e),c(,f(g,)))
我可以使用类似的东西解析字符串
trait Tree extends JavaTokenParsers{
def leaf: Parser[Any] = ident
def child: Parser[Any] = node | leaf | ""
def node: Parser[Any] = ident~"("~child~","~child~")" | leaf
}
但是如何使用解析库来构建树呢?我知道我可以使用
^^
例如,将某个字符串转换为整数。我的困惑来自于在创建 Node
的实例时需要“知道”左右子树.我该怎么做,或者这是否表明我想做一些不同的事情?我是否最好使用解析器返回的东西(对于上面的示例输入
(((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~))
),并基于它构建树,而不是使用像 ^^
这样的解析器运算符?或 ^^^
直接建树?
最佳答案
可以使用 ^^
干净利落地做到这一点。 ,你相当接近:
object TreeParser extends JavaTokenParsers{
def leaf: Parser[Node[String]] = ident ^^ (Node(_))
def child: Parser[Tree[String]] = node | leaf | "" ^^ (_ => End)
def node: Parser[Tree[String]] =
ident ~ ("(" ~> child) ~ ("," ~> child <~ ")") ^^ {
case v ~ l ~ r => Node(v, l, r)
} | leaf
}
现在:
scala> TreeParser.parseAll(TreeParser.node, "a(b(d,e),c(,f(g,)))").get
res0: Tree[String] = T(a T(b T(d . .) T(e . .)) T(c . T(f T(g . .) .)))
在我看来,解决此类问题的最简单方法是使用您想要的结果键入解析器方法,然后使用
^^
添加适当的映射操作。直到编译器满意为止。
关于parsing - 在 Scala 中使用解析器组合器创建递归数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14062619/