Creazione di una struttura dati ricorsiva utilizzando parser combinatori in scala

Question

Sono un principiante in scala, lavorando su S99 per provare ad imparare scala. Uno dei problemi riguarda la conversione da una stringa a una struttura dati dell'albero. Posso farlo "manualmente", voglio anche vedere come farlo usando la libreria del parser combinator di Scala.

La struttura dei dati per l'albero è

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

e l'ingresso si doveva essere una stringa, come questo: a(b(d,e),c(,f(g,)))

posso analizzare la stringa utilizzando qualcosa di simile

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

Ma come posso usare la libreria di analisi per costruire l'albero? So che posso usare ^^ per convertire, ad esempio, una stringa in un numero intero. La mia confusione deriva dal bisogno di "conoscere" i sottoalberi sinistro e destro quando si crea un'istanza di Node. Come posso farlo, o è un segno che voglio fare qualcosa di diverso?

sono io meglio prendere la cosa i rendimenti parser ((((((a~()~(((((b~()~d)~,)~e)~)))~,)~(((((c~()~)~,)~(((((f~()~g)~,)~)~)))~)))~)) per l'ingresso esempio di cui sopra), e la costruzione della base di albero che, invece di utilizzare gli operatori parser come ^^ o ^^^ di costruire direttamente l'albero?

Answer 1

E 'possibile fare questo in modo pulito con ^^, e tu sei abbastanza vicino:

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 
} 

E ora:

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

A mio parere il modo più semplice per affrontare questo tipo di problema è quello di digitare i metodi parser con i risultati desiderati e quindi aggiungere le opportune operazioni di mapping con ^^ fino a quando il compilatore è soddisfatto.