ExprEvaluator.sc

sealed trait Expr
case class BinOp(left: Expr, op:String, right: Expr) extends Expr
case class Literal(value: Int) extends Expr
case class Variable(name: String) extends Expr

trait ExprParser[T] { def parse(s: String): T }
object ExprParser {
  implicit object ParseLiteral extends ExprParser[Literal] { 
    def parse(s: String): Literal = Literal(s.toInt)
  }
  implicit object ParseVariable extends ExprParser[Variable] {
    def parse(s: String): Variable = Variable(s)
  }
  implicit object ParseBinOp extends ExprParser[BinOp] {
    def parse(s: String): BinOp = {
      val binOpPattern = "\\(([0-9]+) (\\+|\\-|\\*) ([0-9]+)\\)".r 
      s match {
        case binOpPattern(left, op, right) => BinOp(Literal(left.toInt), op, Literal(right.toInt))
        case _ => throw new IllegalArgumentException("invalid expression: $s")
      }
    }
  }
}

def parse[T](s:String)(implicit parser: ExprParser[T]) = {
  parser.parse(s)
}

def evaluate(expr: Expr): Int = {
  expr match {
    case BinOp(left, "+", right) => evaluate(left) + evaluate(right)
    case BinOp(left, "*", right) => evaluate(left) * evaluate(right)
    case Literal(value) => value
    // TODO: case Variable(name) => name
  }
}

val literal =  parse[Literal]("1")
assert(literal.value == 1)

val variable = parse[Variable]("x")
assert(variable.name == "x")

val binPlusOp = parse[BinOp]("(1 + 1)")
assert(binPlusOp == BinOp(Literal(1), "+", Literal(1)))
assert(evaluate(binPlusOp) == 2)

val binMultiplyOp = parse[BinOp]("(4 * 2)")
assert(binMultiplyOp == BinOp(Literal(4), "*", Literal(2)))
assert(evaluate(binMultiplyOp) == 8)