CODEWITHSUNDEEP
scalafunctional-programming
user1868607
user1868607

Reputation: 2600

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("Just (some (random) sentence).\n(That doesn't work)".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.

Upvotes: 0

Views: 690

Answers (2)

Sandeep Purohit
Sandeep Purohit

Reputation: 3692

You can try below code may be its work for you in above example there is also problem if you have "sss)fff(" its also give true so it will wrong logically

def balance(chars: List[Char]): Boolean = {
    def balrec(chars: List[Char], accr: Int, accl: Int): Boolean = {
      chars match {
        case head :: tail =>
          if (head.equals('(')) balrec(tail, accr + 1, accl)
          else if (head.equals(')') && (accr > accl || accr == 0)) balrec(tail, accr, accl + 1)
          else balrec(tail, accr, accl)
        case Nil => if (accr == accl) true else false
      }
    }

    balrec(chars, 0, 0)
  }

Upvotes: 0

Lee
Lee

Reputation: 144136

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)
}

Upvotes: 2

Related Questions