Erstellen einer rekursiven Datenstruktur mit Parser-Kombinatoren in Scala

Question

Ich bin ein Anfänger in scala, arbeiten an S99 zu versuchen, scala zu lernen. Eines der Probleme beinhaltet die Umwandlung von einer Zeichenfolge in eine Baumdatenstruktur. Ich kann es "manuell" machen, indem ich auch sehen möchte, wie man es mit Scalas Parser-Kombinator-Bibliothek macht.

Die Datenstruktur für den Baum ist

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

Und die Eingabe soll eine Zeichenfolge, so sein: a(b(d,e),c(,f(g,)))

ich die Saite etwas wie

trait Tree extends JavaTokenParsers{ 
    def leaf: Parser[Any] = ident 
    def child: Parser[Any] = node | leaf | "" 
    def node: Parser[Any] = ident~"("~child~","~child~")" | leaf 
} 

mit parsen

Aber wie kann ich die Parsing-Bibliothek verwenden, um den Baum zu erstellen? Ich weiß, dass ich ^^ verwenden kann, um beispielsweise eine Zeichenfolge in eine Ganzzahl zu konvertieren. Mein verwirrendes kommt von benötigt, um die linken und die rechten Unterbäume beim Erstellen einer Instanz von Node zu kennen. Wie kann ich das tun, oder ist das ein Zeichen, dass ich etwas anderes machen will?

Bin ich besser dran, die Sache der Parser zurückkehrt ((((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) zum Beispiel Eingangs oben) nehmen und den Aufbau des Baumes basiert darauf, dass, anstatt Betreiber Verwendung Parser wie ^^ oder ^^^ den Baum direkt zu bauen?

Answer 1

Es ist möglich, dies mit ^^ sauber zu tun, und Sie sind ziemlich nah:

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 
} 

Und jetzt:

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

Meiner Meinung nach ist der einfachste Weg, diese Art von Problem zu nähern Geben Sie die Parsermethoden mit den gewünschten Ergebnissen ein, und fügen Sie dann die entsprechenden Zuordnungsoperationen mit ^^ hinzu, bis der Compiler zufrieden ist.