Tree.scala

import scala.util.parsing.combinator._

class Tree[L](val label: L, val children: Seq[Tree[L]]) extends Traversable[Tree[L]] {
    val numOfChildren = children.length

    def this(label: L) = this(label, Seq[Tree[L]]())

    override def toString: String = {
        if (isTerminal) {
            return label.toString
        } else {
            return "(" + label.toString + " " + children.mkString(" ") + ")"
        }
    }

    def foreach[U](f: Tree[L] => U): Unit = {
        f(this)
        children.foreach(_.foreach(f))
    }

    def terminals: Seq[L] = {
        this.withFilter(_.isTerminal).map(_.label).toSeq
    }

    def isTerminal: Boolean = children.isEmpty
    def isBinary: Boolean = numOfChildren == 2
    def isUnary: Boolean = numOfChildren == 1
    def isPreTerminal: Boolean = isUnary && children(0).isTerminal
}

object Tree extends RegexParsers {
    private def labelParser = "[^ ()]+".r

    private def terminalParser: Parser[Tree[String]] = labelParser ^^ {
        result => { new Tree(result) }
    }

    private def posParser = "(" ~> labelParser ~ terminalParser <~ ")" ^^ {
        result => { new Tree(result._1, Seq(result._2)) }
    }

    private def consParser: Parser[Tree[String]] =
        "(" ~> labelParser ~ rep(consParser | posParser) <~ ")" ^^ {
        result => { new Tree(result._1, result._2) }
    }

    def fromString(expr: String): ParseResult[Tree[String]] = parseAll(consParser, expr)
}