斯卡拉 : Is there a better way to evaluate an expression tree?

Question

我正在通过“Scala for the Impatient”一书中的练习来学习 Scala。一个问题问:

/**
   * Q8: Extends the tree in the preceding exercise so that each non-leaf node stores an operator in addition to
   * the child nodes. Then write a function `eval` that computes the value. For example, the tree
   *
   *         +
   *    *    2    -
   *  3   8      5
   *
   * has a value (3 * 8) + 2 + (-5) = 21
   *
   */

我的解决方案如下。你能改进它吗？特别是，我想知道是否有一种方法可以直接匹配函数而不是方法名称。例如，如果我可以写出类似下面的假想语句

case ExprTreeNode(f, children @ _*) if (f == Int.+ || f == Int.-) => children.foldLeft(0) { (acc, elem) => eval(elem) f acc }

然后我可以组合 + 和 - 案例。 * 和 / 也是如此。

sealed abstract class ExpressionTree
case class ExprTreeLeaf(value: Int) extends ExpressionTree
case class ExprTreeNode(op: String, children: ExpressionTree*) extends ExpressionTree

def eval(expr: ExpressionTree): Int = expr match {
  case ExprTreeNode("+", children @ _*) => children.foldLeft(0) { _ + eval(_) }
  case ExprTreeNode("*", children @ _*) => children.foldLeft(1) { _ * eval(_) }
  case ExprTreeNode("/", children @ _*) => children.foldLeft(1) { (acc, elem) => eval(elem) / acc }
  case ExprTreeNode("-", child) => eval(child).unary_- // Order matters here, 'children @ _*' would match 1 child
  case ExprTreeNode("-", children @ _*) => children.foldLeft(0) { (acc, elem) => eval(elem) - acc }
  case leaf: ExprTreeLeaf => leaf.value
}

测试用例:

"Method eval" should "evaluate an expression tree" in {
  val expr = ExprTreeNode("+", ExprTreeNode("*", ExprTreeLeaf(3), ExprTreeLeaf(8)), ExprTreeLeaf(2), ExprTreeNode("-", ExprTreeLeaf(5)))

  eval(expr) should be(21)
}

Answer 1

一些想法:

object TestApp extends App{

  sealed abstract class Tree
  case class Leaf(value: Int) extends Tree
  case class Node(op: String, children: Tree*) extends Tree



  //change to map and reduce to remove need for initial value
  def evalReduce(expr: Tree): Int = expr match {
    case Node("-", child) => evalReduce(child).unary_- // Order matters here, 'children @ _*' would match 1 child
    case Node("+", children @ _*) => children.map(evalReduce).reduceLeft(_+_)
    case Node("*", children @ _*) => children.map(evalReduce).reduceLeft(_*_)
    case Node("/", children @ _*) => children.map(evalReduce).reduceLeft(_/_)
    case Node("-", children @ _*) => children.map(evalReduce).reduceLeft(_-_)
    case leaf: Leaf => leaf.value
  }

  // long to declare plus/minus/divide/multiply functions
  // not much prettier/simpler than evalReduce
  val stringToFunction = Map[String,(Int,Int)=>Int](
    "+"->{(i:Int,j:Int)=>i+j},
    "*"->{(i:Int,j:Int)=>i*j},
    "/"->{(i:Int,j:Int)=>i/j},
    "-"->{(i:Int,j:Int)=>i-j}
  )

  def evalCasesUnified(expr: Tree): Int = expr match {
    case Node("-", child) => evalCasesUnified(child).unary_- // Order matters here, 'children @ _*' would match 1 child
    case Node(s, children @ _*) => children.map(evalCasesUnified).reduceLeft(stringToFunction(s))
    case leaf: Leaf => leaf.value
  }


  sealed abstract class TreeFunctional
  case class LeafFunctional(value: Int) extends TreeFunctional
  case class NodeUnaryFunctional(op: Int=>Int, child: TreeFunctional) extends TreeFunctional
  case class NodeFunctional(op: (Int,Int)=>Int, children: TreeFunctional*) extends TreeFunctional

  def evalFunctional(expr: TreeFunctional): Int = expr match {
    case NodeUnaryFunctional(f, child) => f(evalFunctional(child)) 
    case NodeFunctional(f, children @ _*) => children.map(evalFunctional).reduceLeft(f)
    case leaf: LeafFunctional => leaf.value
  }
  val expr = Node("+", Node("*", Leaf(3), Leaf(8)), Leaf(2), Node("-", Leaf(5)))
  val exprFunctional = NodeFunctional({_+_}, NodeFunctional({_*_}, LeafFunctional(3), LeafFunctional(8)), LeafFunctional(2), NodeUnaryFunctional({-_}, LeafFunctional(5)))

  def plus(i:Int,j:Int):Int = {i+j}
  def minus(i:Int,j:Int):Int = {i-j}
  def minusUnary(i:Int):Int = -i
  def multiply(i:Int,j:Int):Int = {i*j}
  def divide(i:Int,j:Int):Int = {i/j}

  val exprFunctionalNicer = NodeFunctional(plus, NodeFunctional(multiply, LeafFunctional(3), LeafFunctional(8)), LeafFunctional(2), NodeUnaryFunctional(minusUnary, LeafFunctional(5)))

  //but then you could create a case class for each function

  sealed abstract class TreeNamed
  case class Value(value: Int) extends TreeNamed

  abstract class UnaryNode() extends TreeNamed {
    val child: TreeNamed
    def op: Int=>Int
  }
  case class MinusUnary(child:TreeNamed) extends UnaryNode{
    def op = {-_}
  }

  abstract class MultinaryNode() extends TreeNamed {
    val children: Seq[TreeNamed]
    def op: (Int,Int)=>Int
  }

  case class Plus(children:TreeNamed*) extends MultinaryNode{
    def op = {_+_}
  }
  case class Minus(children:TreeNamed*) extends MultinaryNode{
    def op = {_-_}
  }
  case class Multiply(children:TreeNamed*) extends MultinaryNode{
    def op = {_*_}
  }
  case class Divide(children:TreeNamed*) extends MultinaryNode{
    def op = {_/_}
  }

  val exprNamed = Plus(Multiply(Value(3), Value(8)), Value(2), MinusUnary(Value(5)))

  def evalNamed(expr: TreeNamed): Int = expr match {
    case u:UnaryNode => u.op(evalNamed(u.child))
    case m:MultinaryNode => m.children.map(evalNamed).reduceLeft(m.op)
    case leaf: Value => leaf.value
  }


  println(evalReduce(expr))
  println(evalCasesUnified(expr))
  println(evalFunctional(exprFunctional))
  println(evalFunctional(exprFunctionalNicer))
  println(evalNamed(exprNamed))
}