Parentheses balancing Algorithm with recursion in Scala

If you are writing compilers for any language, it’s common practice to parse text and check for parsing errors. One of such task is Parentheses balancing. Now we can look at simple Algorithm for Parentheses balancing with recursion as an Algorithmic design.

1.Algorithm for Parentheses balancing

Recursively checks if string contains matching amount of opening and closing parentheses by calling  isBalanced()  on the string without first element.
Expectancy of parentheses in the string is kept in a kind of balance indicator numOfPositions – 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 (numOfPositions == 0), e.g. there was matching amount of parentheses seen.
There is also a check ( numOfPositions > 0 ) to ensure that ‘)’ wasn’t encountered before there was ‘(‘ it could close.

2.Parentheses Balancing in Scala


Leave a Comment