Calculate a mathematical expression stored in String - Scala

Question

I have a String like val s = "5 - 3 + 2" (there can be any number of additions/substractions). Using pattern matching I would like to calculate this expression (so for this example result would be 4). My first idea is to do something like this:

object calculator{
    val s = "5 - 3 + 2"
    val Pattern = "(\\d+)".r

    def main(args: Array[String]) {
       val matches = Pattern.findAllIn(s).toArray
       for (mymatch <- matches) mymatch.toInt
       var sum = 0
       matches.foreach(sum += _)
       println(sum)   
    }
}

It doesn't even assume that I can have substractions (I don't know how to do this), but there is an error: type mismatch; found : String#3416175 required: Int#1078

Another approach is to have a matcher and somehow evaluate these expressions there:

val Pattern = ((?:\\d+\\s*[-+]\\s+)*\\d+).r
def matcher(expression: String): Any = expression match {
        case Pattern(expression) => expression //evaluate expression here?
        case _ => "wrong expression"
    }

Any ideas how to achieve this?

Answer 1

If your expression contains only additions and substractions you can use something like this:

val expression = "5 - 3 + 2"

def evaluate(expression: List[String]): Int = expression match {
    case l :: "+" :: r :: rest => evaluate((l.toInt + r.toInt).toString :: rest)
    case l :: "-" :: r :: rest => evaluate((l.toInt - r.toInt).toString :: rest)
    case value :: Nil => value.toInt
}

val expressionElements = expression.split("\\s").toList

val result = evaluate(expressionElements)

println(s"$expression = $result")

Detailed explanation how pattern matching works you can find here (http://lampwww.epfl.ch/~emir/written/MatchingObjectsWithPatterns-TR.pdf) but I try to explain this particular example step by step.

First of all you have to understand how List can be constructed.

val list = List(1, 2, 3) 
val list = 1 :: 2 :: 3 :: Nil
(two lists with 3 elements: 1, 2, 3)

So our expression is something like this:

  val expressionElements = expression.split("\\s").toList  
//val expressionElements = "5" :: "-" :: "3" :: "+" :: "2" :: Nil

evaluate function supports three cases:

1. addition - case l :: "+" :: r :: rest =>
2. substraction - case l :: "-" :: r :: rest =>
3. "value" - case value :: Nil =>

First evaluate call , which is (tail) recursive function, will be something like this:

evaluate ("5" :: "-" :: "3" :: "+" :: "2" :: Nil) = "5" :: "-" :: "3" :: "+" :: "2" :: Nil match {
   case l   :: "-" :: r   :: rest              => evaluate (l - r :: rest)
 //case "5" :: "-" :: "3" :: "+" :: "2" :: Nil => evaluate (5 - 3 :: "+" :: "2" :: Nil)
 //case "5" :: "-" :: "3" :: "+" :: "2" :: Nil => evaluate ("2"   :: "+" :: "2" :: Nil)
}

Second call:

evaluate ("2" :: "+" :: "2" :: Nil) = "2" :: "+" :: "2" :: Nil match {
  case l   :: "+" :: r   :: rest  => evaluate (l + r :: rest)
//case "2" :: "+" :: "2" :: Nil   => evaluate (2 + 2 :: rest)
//case "2" :: "+" :: "2" :: Nil   => evaluate ("4"   :: Nil)
}

And third call:

evaluate ("4"   :: Nil) = "4"   :: Nil match {
  case value :: Nil => value.toInt
//case "4"   :: Nil => "4".toInt
}

So expression is evaluated to 4.

Answer 2

Is there a reason you would want to do this with a regex? There are other solutions out there...

You could create a far more powerful solution using parser combinators. Take a look at this blog post from Don Roby that shows exactly this.

You could use Dijkstra's Two Stack algorithm like in this stackoverflow, or better yet from Princeton here.

Answer 3

import scala.reflect.runtime.currentMirror
import scala.tools.reflect.ToolBox

val expr = "2*(2+3)"

val toolbox = currentMirror.mkToolBox()
val calc = toolbox.eval(toolbox.parse(expr))

The result is

calc: Any = 10