6

私はScalaの初心者で、S99に取り組んでScalaを学ぼうとしています。問題の1つは、文字列からツリーデータ構造への変換に関係しています。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 に答える