创建递归数据结构使用解析器组合在斯卡拉

我在斯卡拉初学者，对S99努力尝试学习阶。其中一个问题涉及从字符串转换为树数据结构。我可以通过“手动”来完成，我也想看看如何使用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)~,)~)~)))~)))~))），并基于此构建树，而不是使用解析器运算符（如^^或^^^）直接构建树？

来源

2012-12-27 anchorite

有可能与^^干净做到这一点，而你也非常接近：

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-28 00:21:29

哈，我想'JavaTokenParsers'是一些Java库。你再次想出了更好的答案！ – drstevens

你没有'T（。）'''是对的。我离开了'“=>（_ => End）'位。为了清晰起见，我删除了答案。 – drstevens

感谢答案和关于如何解决这类问题的元回答。现在，我需要重新阅读“Scala编程”中有关解析器的章节，以了解我还错过了什么。 – anchorite

创建递归数据结构使用解析器组合在斯卡拉

回答

相关问题