創建遞歸數據結構使用解析器組合在斯卡拉

我在斯卡拉初學者，對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

創建遞歸數據結構使用解析器組合在斯卡拉

回答

相關問題