Scala: Make sure braces are balanced

Question

I am running a code to balance brackets in statement. I think i have gotten it correct but it is failing on one particular statement, i need to understand why?

This is the test in particular it is failing "())("

More than the coding i think i need to fix the algo, any pointers?

def balance(chars: List[Char]): Boolean = {

  def find(c: Char, l: List[Char], i: Int): Int={
    if( l.isEmpty ) {
      if(c=='(')
        i+1
      else if(c==')')
        i-1
      else
        i
    }
    else if (c=='(')
      find(l.head, l.tail, i+1)
    else if(c==')')
      find(l.head,l.tail, i-1)
    else
      find(l.head,l.tail, i)

  }

  if(find(chars.head, chars.tail,0) ==0 )
     true
  else
     false

}


balance("())(".toList) //passes when it should fail
balance(":-)".toList)
balance("(if (zero? x) max (/ 1 x))".toList)
balance("I told him (that it's not (yet) done).\n(But he wasn't listening)".toList)

Answer 1

Here is a version:

def balance(chars: List[Char]): Boolean = {
    def inner(c: List[Char], count: Int): Boolean = c match {
        case Nil                   => count == 0           // Line 1
        case ')' :: _ if count < 1 => false                // Line 2
        case ')' :: xs             => inner(xs, count - 1) // Line 3
        case '(' :: xs             => inner(xs, count + 1) // Line 4
        case _ :: xs               => inner(xs, count)     // Line 5
    }
    inner(chars, 0)
}

So in your code, I think you are missing the additional check for count < 1 when you encounter the right paranthesis! So you need an additional else if that checks for both the ')' and count < 1 (Line 2 in the example code above)

Answer 2

You can also use the property of Stack data structure to solve this problem. When you see open bracket, you push it into the stack. When you see close bracket, you pop from the stack (instead of Stack I'm using List, because immutable Stack is deprecated in Scala):

def isBalanced(chars: Seq[Char]): Boolean = {
  import scala.annotation.tailrec

  case class BracketInfo(c: Char, idx: Int)
  def isOpen(c: Char): Boolean = c == '('
  def isClose(c: Char): Boolean = c == ')'
  def safePop[T](stack: List[T]): Option[T] = {
    if (stack.length <= 1) stack.headOption
    else stack.tail.headOption
  }

  @tailrec
  def isBalanced(chars: Seq[Char], idx: Int, stack: List[BracketInfo]): Boolean = {
    chars match {
      case Seq(c, tail@_*) =>
        val newStack = BracketInfo(c, idx) :: stack // Stack.push
        if (isOpen(c)) isBalanced(tail, idx + 1, newStack)
        else if (isClose(c)) {
          safePop(stack) match {
            case Some(b) => isBalanced(tail, idx + 1, stack.tail)
            case None =>
              println(s"Closed bracket '$c' at index $idx was not opened")
              false
          }
        }
        else isBalanced(tail, idx + 1, stack)
      case Seq() =>
        if (stack.nonEmpty) {
          println("Stack is not empty => there are non-closed brackets at positions: ")
          println(s"${stack.map(_.idx).mkString(" ")}")
        }
        stack.isEmpty
    }
  }

  isBalanced(chars, 0, List.empty[BracketInfo])
}

Answer 3

You've made a very simple and completely understandable mistake. The parentheses in )( are balanced, by your current definition. It's just that they're not balanced in the way we would usually think. After the first character, you have -1 unclosed parentheses, and then after the second characte we're back to 0, so everything is fine. If the parenthesis count ever drops below zero, the parentheses cannot possibly be balanced.

Now there are two real ways to handle this. The quick and dirty solution is to throw an exception.

case object UnbalancedException extends Exception

if (i < 0)
  throw UnbalancedException

then catch it and return false in balance.

try {
  ... // find() call goes in here
} catch {
  case UnbalancedException => false
}

The more functional solution would be to have find return an Option[Int]. During the recursion, if you ever get a None result, then return None. Otherwise, behave as normally and return Some(n). If you ever encounter the case where i < 0 then return None to indicate failure. Then in balance, if the result is nonzero or the result is None, return false. This can be made prettier with for notation, but if you're just starting out then it can be very helpful to write it out by hand.