Coursera Scala Functional Programming 1st Week balance brackets

Main.scala

  /**
   * Criteria: Every closing parenthesis ) must have a unique opening ( parenthesis before it
   *
   * For every closing parenthesis, we search for the first opening parenthesis and remove it, and keep going
   */
  def balance(chars: List[Char]): Boolean =
    (chars.indexOf(')'), chars.indexOf('(')) match {
      case (leftMostClosing, leftMostOpening) if leftMostClosing == -1 && leftMostOpening != -1 => false    // no closing / some opening => fail
      case (leftMostClosing, leftMostOpening) if leftMostClosing == -1 && leftMostOpening == -1 => true     // no closing or opening => ok
      case (leftMostClosing, leftMostOpening) if leftMostClosing != 1 && leftMostOpening == -1 => false     // closing but no opening => fail
      case (leftMostClosing, leftMostOpening) if leftMostClosing != -1 && leftMostOpening != -1             // first closing before first opening
        && leftMostClosing < leftMostOpening => false
      case (leftMostClosing, leftMostOpening) => balance(                                                   // first closing after first opening => strip them and recurse
        chars
          .zipWithIndex
          .filter(tuple => tuple._2 != leftMostClosing && tuple._2 != leftMostOpening)
          .map(tuple => tuple._1)
      )
    }

@deigote

IntelliJ complains about cyclomatic complexity of the above (too many cases), how can I refactor it to be better? Function should determine whether parenthesis are balanced in a string, which the above does

@inakianduaga balanced in the traditional sense (i.e nested parenthesis are allowed)? * Criteria: Every closing parenthesis ) must have a unique opening ( parenthesis before it confuses me a bit. It seems the nested parenthesis are not allowed.

In any case, for the solution listed in this gist, I'd argue that the pattern matching eloquence is lost due to the usage of ifs to express the conditions. Always pattern match from most specific to least (this is the case also for tradicional if-else if-else nests).

Might be that your approach is the usual in "official" scala style, but something like the following is way less noisy and (I believe) has the same meaning:

case (-1, -1) => true
case (-1, _) => false
case (_, -1) => false
case (leftMostClosing, leftMostOpening) => if (....) false else balance(...)

The rest of the comment goes for "nested parenthesis are allowed", which is what I thought at the beginning

It's still not the most flexible solution. In imperative style this is always done with a mutable stack (push on open, pop on close and compare) and a loop. I'd suggest:

• Implement it using that imperative approach
• then try to make your initial solution work with any type of parenthesis (brackets, curly braces, a collection of pairs of random symbols passed as a parameters...), and compare the difficulty of that with doing the same for the stack based one.
• last, go all functional by replacing the the mutable stack and the loop by an immutable stack and recursion

That'd be my approach to understand the whole thing better :-) .

In the end it looks like your solution, the generalization to a list of symbols is trivial

  /**
   * Determine if the string has balanced symbols
   */
  def balancePair(chars: List[Char], pair: (Char, Char)): Boolean =
    (chars.indexOf(pair._1), chars.indexOf(pair._2)) match {
      case (-1, -1)      => true                                     // no closing or opening
      case (-1, left)    => false                                    // no closing / some opening
      case (right, -1)   => false                                   // closing but no opening
      case (right, left) =>
        if
          (right != -1 && left != -1 && right < left) false          // first closing before first opening
        else
          balancePair(                                               // first closing after first opening => strip them and recurse
            chars
              .zipWithIndex
              .filter(tuple => tuple._2 != right && tuple._2 != left)
              .map(_._1),
            pair
          )
    }

  /**
   * Determine if the string is balanced against a list of symbols
   */
  def balancePairs(chars: List[Char], pairs: List[(Char, Char)]): Boolean = !pairs.map(balancePair(chars, _)).exists(!_)

@inakianduaga now go for the "nested is allowed" version :-)