Пошаговая оценка с помощью комбинатора парсеров в scala

Вот очень простая реализация того, что вы пытаетесь сделать:

Во-первых, мы определяем иерархию выражений. Вам нужно будет адаптировать это к вашей конкретной проблеме.

trait Expr {
  def eval: Int
}
case class IntLeaf(n: Int) extends Expr {
  def eval = n
  override def toString = "%d".format(n)
}
case class Sum(a: Expr, b: Expr) extends Expr {
  def eval = a.eval + b.eval
  override def toString = "(%s + %s)".format(a, b)
}

Затем функция, объединяющая только самую нижнюю ветвь.

def combineLeaves(e: Expr): Expr = {
  e match {
    case IntLeaf(n) => IntLeaf(n)
    case Sum(IntLeaf(a), IntLeaf(b)) => IntLeaf(a + b)
    case Sum(a, b) => Sum(combineLeaves(a), combineLeaves(b))
  }
}

Затем функция, которая объединяет дерево по одному уровню за раз, печатая по ходу дела.

def printEval(e: Expr) {
  println(e)
  e match {
    case IntLeaf(n) =>
    case _ => printEval(combineLeaves(e))
  }
}

Теперь парсер. Опять же, вам придется адаптировать это к вашим данным.

object ArithmeticParser extends RegexParsers {
  private def int: Parser[IntLeaf] = regex(new Regex("""\d+""")).map(s => IntLeaf(s.toInt))
  private def sum: Parser[Sum] = ("(" ~> expr ~ "+" ~ expr <~ ")").map { case (a ~ _ ~ b) => Sum(a, b) }
  private def expr = int | sum
  def parse(str: String): ParseResult[Expr] = parseAll(expr, str)
  def apply(str: String): Expr = ArithmeticParser.parse(str) match {
    case ArithmeticParser.Success(result: Expr, _) => result
    case _ => sys.error("Could not parse the input string: " + str)
  }

}

И вот как вы его используете:

scala> printEval(ArithmeticParser("((1 + 7) + ((3 + 9) + 5))"))
((1 + 7) + ((3 + 9) + 5))
(8 + (12 + 5))
(8 + 17)
25

Комбинаторы парсера никогда не дают вам никакой оценки. Используя комбинаторы парсера, вы анализируете входную строку и создаете некоторую структуру данных, представляющую ее. Оценка — это еще один шаг, на котором вы каким-то образом обрабатываете структуру данных и выполняете необходимые упрощения. Следовательно, имея ваше выражение 3+4*7, на этапе синтаксического анализа вы можете построить следующее абстрактное синтаксическое дерево:

   +
  / \
 3   *   
    / \
   4   7

а затем, на этапе оценки, рекурсивно пройтись по дереву и для каждого нелистового узла применить операцию узла к результатам оценки его левого и правого поддеревьев.

Если документация не поможет, вы можете обратиться к главе о комбинаторах синтаксического анализа в Программирование на Scala, первое издание которого доступно бесплатно.

Недавно я также написал сообщение в блоге на комбинаторах парсеров в Scala, где я обсуждаю сценарий, несколько похожий на ваш.