Parenthesis Balancing Algorithm

Question

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.

What do you mean exactly with "does not work" ? Do you have an output ? — Zermingore, Sep 30 '16 at 09:48
@Zermingore yes, for the println statement it should return true but it actually return false — user1868607, Sep 30 '16 at 09:50
You could also consider using a combinator parser (e.g. atto) for this kind of problem, although that's a bit overkill here. — Reactormonk, Sep 30 '16 at 09:59
@Reactormonk, just a bit overkill, yes. This is a Coursera course exercise... — The Archetypal Paul, Sep 30 '16 at 10:22
If this is the homework for week 1 of the _Functional Programming Principles in Scala_ (and the test string strongly suggests that it is), this is a breach of Coursera's Honor Code. — Hristo Iliev, Sep 30 '16 at 13:47
Possible duplicate of [Parenthesis Balancing Algorithm recursion](https://stackoverflow.com/questions/19818569/parenthesis-balancing-algorithm-recursion) — Ojasvi Monga, Oct 05 '19 at 05:01

score 2 · Accepted Answer · answered Sep 30 '16 at 10:03

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

that's the one! it can also be solved putting else if instead of the second if. thanks — user1868607, Sep 30 '16 at 10:08

Sandeep Purohit · Answer 2 · 2016-09-30T10:42:31.267

0

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

edited Sep 30 '16 at 10:42

answered Sep 30 '16 at 09:58

Sandeep Purohit

3,652
18
22

There's little point in giving completely different code, even if it works. The OP provides a link to a question with a working example. It was a question about what was wrong with their code, not a request for another solution. – The Archetypal Paul Sep 30 '16 at 10:24
@TheArchetypalPaul its not another solution its same as mentioned in lee answer its is not in same match case so i put it in same and give overall solution – Sandeep Purohit Sep 30 '16 at 10:26
No, it';s completely different. The parameter names have changed, the case statements are badly organised, the orders of tests are different. – The Archetypal Paul Sep 30 '16 at 10:27
@TheArchetypalPaul sorry but i cant copy variable names also same when i try to solve something i just try it on my REPL and i put name whatever in my mind – Sandeep Purohit Sep 30 '16 at 10:30
It's "the same" only in that it's a recursive functiont to solve the problem. In pretty much all other aspects, it's different. It also thinks ")()" is balanced, so it's not even correct. – The Archetypal Paul Sep 30 '16 at 10:32
Well, now it doesn't even compile (you're missing a `(`, ironically) and when that's fixed, it still produces the wrong answer. I won't reply again. – The Archetypal Paul Sep 30 '16 at 10:36
Let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/124635/discussion-between-sandeep-purohit-and-the-archetypal-paul). – Sandeep Purohit Sep 30 '16 at 10:40

Parenthesis Balancing Algorithm

2 Answers2