Trying to understand parenthesis balancing recursion in Scala

Viewed 724

I am new to Scala and functional programming. Disclaimer: yes, I am taking the Scala course on Coursera, and yes, this is part of the assignment. My only goal here is to get some help to understand how this solution works in order to develop my own solution and familiarize with functional programming.

I am stuck on this implementation of the recursive algorithm to check for parenthesis balancing. I simply don't get:

  1. how the functions are structured
  2. how the evaluation of the boolean expression occurs
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)
}

My first doubt is the following. The inner function immediately starts by evaluating the boolean expression

if (chars.isEmpty) open == 0

My understanding (maybe wrong) is that here both expressions will be evaluated: chars.isEmpty and open==0. However, the argument open doesn't seem to be yet defined anywhere. So why don't I get an error? Second, I simply cannot get the line:

if (chars.head == '(') balanced(chars.tail,open+1)

Where will balanced(chars.tail,open+1) be evaluated and how?

Suppose I want to check whether "(" has balanced parentheses.

if (chars.isEmpty) open == 0

Will return False, then

if (chars.head == '(') balanced(chars.tail,open+1)

The first expression will be TRUE, but the second one? "(" doesn't have a tail, and again I don't see how open+1 works, since the integer open has not been defined anywhere. I am pretty confused.

1 Answers
Related