Rodrigo - 24 days ago 5x
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.

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)
}
``````
Source (Stackoverflow)