Parenthesis Balancing Algorithm recursion
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.
user2947615
Updated on June 06, 2022Comments
-
user2947615 almost 2 years
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) }