Program logic error


#1

I am a beginner trying to learn Scala.

This is a small program I tried to write to calculate expressions in the correct order -

object Calc extends App {
    while (true) {
        val input: String = scala.io.StdIn.readLine("> ")
        println(evaluate(input))
    }


    def evaluate(input: String) = {
        val finput = input.replace(" ", "")
        var elems = new Array[String](finput.length())
        var last = elems.length
        for (i <- 0 to last - 1) {
            elems(i) = finput.substring(i, i + 1)
        }
        val operators: Array[String] = Array("/", "*", "+", "-")
        for (i <- 0 to operators.length) {
            while (elems contains operators(i)) {
                val pos = elems.indexOf(operators(i))
                val a = elems(pos-1).toInt
                val b = elems(pos+1).toInt
                var found = 0
                elems(pos) match {
                    case "/" => found = a/b
                    case "*" => found = a*b
                    case "+" => found = a+b
                    case "-" => found = a-b
                }
                elems(pos-1) = found.toString()
                last = last - 2
                for (j <- pos to last) {
                    elems(j) = elems(j + 2)
                }
            }
        }
        elems(0)
    }
}

This program does not work, I get a runtime error at elems(j) = elems(j + 2). Could someone tell me why?
Also, is the program design okay?


#2

Well the proximate cause of your exception is the line
for (j <- pos to last) { ...
The to() method on RichInt is inclusive on the range, so you’re walking off the end of the array when trying to shift the trailing elements forward. To get past that immediate problem, you could use until() instead:
for (j <- pos until last) { ...

This will no longer cause the exception, but now you’re likely to loop infinitely on simple input expressions, because you’re doing your search for operators (while (elems contains operators(i))) on the entire elems array, not just the first last elements.

Also, is the program design okay?

Well, you’re trying to handle a well-known problem (“parsing and evaluating an expression”) in a known very difficult fashion: in-place mutation of the input. To do this, you’re keeping and mutating state all over the place, and this is going to end up very very hard to reason about (and get correct in all cases).

An alternate approach might be to first tokenize the input (that will make it easier to support multi-digit numbers as well as things like parenthesis, etc), but do this not-in-place. You can build a parsed expression from this.

A good place to start might be to investigate “parser combinators”, and use a standard scala implementation of this. This should make it quite straightforward to define your grammar and parse valid inputs while rejecting invalid inputs. Evaluating your parsed expression into a final value should then be quite straightforward, and is left as a further exercise to the OP.