21

Can somebody explain to me the algorithm for the Parenthesis Balancing problem?

"Is the string (code) syntax correct on account of matching parentheses couples?"

I can't figure it out apart from the fact that for each " ( " there should be another " ) " for the algorithm to return true.

Thanks!

I found this solution but I do not understand it and I don't want to copy and paste it:

def balance(chars: List[Char]): Boolean = {
    def balanced(chars: List[Char], open: Int): Boolean = {
        if (chars.isEmpty) open == 0
            else
                if (chars.head == '(') balanced(chars.tail,open+1)        
                else
                    if (chars.head == ')') open>0 && balanced(chars.tail,open-1)
                    else balanced(chars.tail,open)
    }      
    balanced(chars,0)
 }
Kara
  • 6,115
  • 16
  • 50
  • 57
user2947615
  • 491
  • 3
  • 5
  • 14

1 Answers1

18

This code recursively checks if string contains matching amount of opening and closing parentheses by calling balanced() on the string without first element.

Expectancy of parentheses in the string is kept in a kind of balance indicator open - positives indicate amount of needed ')' and negatives amount of needed '('. Initial balance is 0.

When recursion reaches end of string it checks if balance is ok (open == 0), e.g. there was matching amount of parentheses seen.

There is also a check (open > 0) to ensure that ')' wasn't encountered before there was '(' it could close.

arkonautom
  • 958
  • 18
  • 29
  • 1
    One last thing... in this line : if (chars.head == ')') open>0 && balanced(chars.tail,open-1) how is the && after the two conditions and it still works? Is it the same as if(chars.head == ')') && open > 0 balanced(chars.tail,open-1) ? – user2947615 Nov 06 '13 at 18:23
  • 3
    if (chars.head == ')') { open>0 && balanced(chars.tail,open-1)} => if (boolean) {boolean && boolean} – arkonautom Nov 06 '13 at 18:25
  • On **if** function returns AND (&&) result of booleans A and B. A) balance indicates there were unclosed '(' before that can be closed by current ')' and B) the rest of the string is balanced. Is "balance" concept clear for you? – arkonautom Nov 06 '13 at 18:35
  • Yes I understand what he means by balance. However I am not understand the case where there is a " ) " i.e these 2 lines: else if (chars.head == ')') open>0 && balanced(chars.tail,open-1) else balanced(chars.tail,open) – user2947615 Nov 06 '13 at 18:39
  • "how is the && after the two conditions and it still works" - there is one expression after **if**. {open>0 && balanced(chars.tail,open-1)} is executed if that **if** condition is true, expression after **else** otherwise. {open>0 && balanced(chars.tail,open-1)} evaluates 2 expressions - A) (open > 0) and B) balanced(...), each to either true T or false F. Last step is operation && on A and B. T && T => T, all other combinations (T && F, F && T, F && F) are F. – arkonautom Nov 06 '13 at 18:47
  • 1
    Now I get that! Thanks for your patience but I am new to scala. Just this I promisee else balanced(chars.tail,open) , when will this line be executed? if there is no ( or ) ? – user2947615 Nov 06 '13 at 18:55
  • Yep. P.S. You should mark answers that solved your problem as accepted ;). – arkonautom Nov 06 '13 at 18:58
  • I just did! Thanks soooo much – user2947615 Nov 06 '13 at 19:54
  • Using a stack is just so much easier than the recursive approach. – Dane_duPlessis Dec 30 '21 at 13:52