Rodrigo Rodrigo - 2 months ago 16
Scala Question

Parenthesis Balancing Algorithm

I'm working with a little program in scala for checking if certain expression iis correctly formed with respect to the opening and closing of parentheses. It is the problem as here but my own program.

def balance(chars: List[Char]): Boolean = {
def balanced(chars: List[Char], opened: Int, closed: Int): Boolean = {
if (chars.isEmpty && opened == closed) true
else if (opened < closed) false
else {
if (chars.head == '(') balanced(chars.tail, opened + 1, closed)
if (chars.head == ')') balanced(chars.tail, opened, closed + 1)
else balanced(chars.tail, opened, closed)
}
}
balanced(chars, 0, 0)


}

println(balance("I told him (that it's not (yet) done).\n(But he wasn't listening)".toList))

The problem is that for example it does not work for this example. I traced the program an apparently the problem comes when we return from the recursive calls but I cannot figure out what the error is.

Lee Lee
Answer

In

else {
    if (chars.head == '(') balanced(chars.tail, opened + 1, closed)
    if (chars.head == ')') balanced(chars.tail, opened, closed + 1)
    else balanced(chars.tail, opened, closed)
}

You have two independent if expressions when you want to treat them as a single case expression. If chars.head == '(' is true the recursive call is made but the result is ignored and the second if is evaluated. This will cause the else branch to be taken which effectively ignored the ( found in the first expression. You can use a match e.g.

chars match {
  case Nil => opened == closed
  case '('::cs => balanced(cs, opened + 1, closed)
  case ')'::cs => balanced(cs, opened, closed + 1)
  case _::cs => balanced(cs, opened, closed)
}