6

我是 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)~,)~)~)))~)))~))对于上面的示例输入），并基于它构建树，而不是使用解析器运算符^^或^^^直接构建树？

4

1 回答 1

5

可以使用 干净地执行此操作^^，并且您非常接近：

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 . .) .)))

在我看来，解决此类问题的最简单方法是使用您想要的结果键入解析器方法，然后添加适当的映射操作，^^直到编译器满意为止。

于 2012-12-28T00:21:29.440 回答