Reverse Polish Notation calculator in Scala

Question

I wrote an RPN solver in Scala. I'd love to get some feedback on approaches to make this feel more idiomatic.

object ReversePolishNotation {
  private object Operator extends Enumeration {
    val Divides = "/"
    val Times = "*"
    val Plus = "+"
    val Minus = "-"
  }

  import Operator._

  private val stringToOperator = Map[String, (Double, Double) => Double] (
    Divides -> {_ / _},
    Minus -> {_ - _},
    Times -> {_ * _},
    Plus -> {_ + _}
  )

  private def foldFunc(acc: List[Double], tok: String) = acc match {
    case Nil | List(_) => tok.toDouble :: acc
    case head::next::rest => tok match {
      case op @ (Divides | Minus | Times | Plus) => stringToOperator(op) (next, head) :: rest
      case s: String => s.toDouble :: acc
    }
  }

  def solve(tokens: Seq[String]) = 
  tokens.foldLeft(List[Double]())(foldFunc) match {
    case head::Nil => head
    case Nil => throw new Exception("The stack cannot be empty!")
    case head::next::rest => throw new Exception("The stack should only have one value!")
  }
}

Answer 1

Operator

The main issue about this implementation is that Operator is declared as Enumeration, but indeed does not represent an enum: all the vals are String constants, but not instances of the enumerated type. And this usage is not very appropriate.

Well, enums in Scala are rather different from Java and we cannot easily associate items of an enum with methods: that is what you are trying to do with stringToOperator Map. Generally, it's OK, it works, it remains readable, but the Operator type somehow disappears in the code. If you comment out some lines like this

//  private object Operator extends Enumeration {
val Divides = "/"
val Times = "*"
val Plus = "+"
val Minus = "-"
//  }

//  import Operator._

the code will still compile and work: looks like Operator is not really meaningful in this implementation.

I suggest to create a dedicated type that will provide a means of evaluation of expressions expecting two Double args:

abstract class Operator(operation: (Double, Double) => Double) {
  def eval(left: Double, right: Double): Double = operation.apply(left, right)
}

This type is instantiated with target arithmetic operations, each in a dedicated object:

case object Divides extends Operator({ _ / _ })
case object Times extends Operator({ _ * _ })
case object Plus extends Operator({ _ + _ })
case object Minus extends Operator({ _ - _ })

Now we need to parse a raw token, represented initially as a String. A token can correspond to a numeric value or to an operator. We can use Scala's Either construct to represent this choice:

private def parseToken(tok: String): Either[Double, Operator] = tok match {
  case "/" => Right(Divides)
  case "*" => Right(Times)
  case "+" => Right(Plus)
  case "-" => Right(Minus)
  case _ => Left(tok.toDouble)
}

Consequently, the foldFunc is reduced to one-level matcher for cases from this Either reference:

private def foldFunc(acc: List[Double], tok: String) = parseToken(tok) match {
  case Left(num) => acc :+ num
  case Right(op) => op.eval(acc.head, acc.tail.head) :: acc.tail.tail
}

Exceptions

Exception type is too general and is discouraged to be thrown from any method. Try to find semantically more appropriate existing types. For example, in solve function, if the stack is empty or contains more than two elements, it is in an invalid state. There exists IllegalStateException for that and it might be used.

I'd also suggest more informative messages in the exceptions and probably add more checks for the cases when numbers or operators appear in unexpected positions.