Matching parentheses algorithm in immutable/pure functional Scala with foldLeft and a state machine

Problem

Algorithm to check parentheses in a String are balanced. This problem is also known as:

  • On Codility: Stacks and Queues: Brackets - Determine whether a given string of parentheses (multiple types) is properly nested.
  • On HackerRank: Balanced Brackets - Given strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

Parentheses in a String are balanced when an opening bracket is followed by another opening bracket or by a closing bracket of the same time.

For example, ([]) is balanced, but ([) and ([)] are not.

We have a plain tail-recursive solution as well: ParenthesesTailRecursive

Solution

This solution is available for purchase!

Upon purchase, you will be able to Register an account to access solutions on multiple devices.

We use Stripe for secure payment processing.


Alternatively, get unlimited solutions for $3.99 per month!

'Unlimited Scala Algorithms' gives you access to all solutions!

Test cases

assert(parenthesesAreBalancedFolding("()"))
assert(parenthesesAreBalancedFolding("[()]"))
assert(parenthesesAreBalancedFolding("{[()]}"))
assert(parenthesesAreBalancedFolding("([{{[(())]}}])"))
assert(!parenthesesAreBalancedFolding("{{[]()}}}}"))
assert(!parenthesesAreBalancedFolding("{[(])}"))

Scala Concepts

foldLeft and foldRight

A 'fold' allows you to perform the equivalent of a for-loop, but with a lot less code.

def foldMutable[I, O](
    initialState: O
)(items: List[I])(f: (O, I) => O): O = {
  var result: O = initialState
  items.foreach { item => result = f(result, item) }
  result
}

Becomes:

def foldMutable[I, O](initialState: O)(items: List[I])(f: (O, I) => O): O =
  items.foldLeft(initialState)(f)

So you can see how ta Scala solution that is immutable can be represented in a mutable form. Reverse is also possible.

The big difference is that to the user it is immutable, because you only specify the next value by adding an item to an accumulator.

This presents many possibilities, most important of which is to be able to develop code in a highly predictable and obvious manner, whereas in standard for-loops, many complications can arise (wrong indices, unexpected mutations).

def getUniqueCharacters(string: String): Set[Char] = {
  var setOfCharacters = Set.empty[Char]
  string.foreach { character =>
    setOfCharacters = setOfCharacters + character
  }
  setOfCharacters
}

assert(getUniqueCharacters("ABCDEABC") == Set('A', 'B', 'C', 'D', 'E'))

And in an immutable fashion:

def getUniqueCharacters(string: String): Set[Char] = {
  string.foldLeft(Set.empty[Char])(_ + _)
}

assert(getUniqueCharacters("ABCDEABC") == Set('A', 'B', 'C', 'D', 'E'))

The rule of thumb is: if you want a single result, use `foldLeft`, if you want a set of intermediate results, use scanLeft and scanRight.

Pattern Matching

Pattern matching in Scala lets you quickly identify what you are looking for in a data, and also extract it.

assert("Hello World".collect {
  case character if Character.isUpperCase(character) => character.toLower
} == "hw")

assert("Hello World".filter(Character.isUpperCase).map(_.toLower) == "hw")

assert((1 to 10).collect {
  case num if num % 3 == 0 => "Fizz"
  case num if num % 5 == 0 => "Buzz"
}.toList == List("Fizz", "Buzz", "Fizz", "Fizz", "Buzz"))

Pattern matching is used by methods like Collect, but can also be easily integrated into normal functions.

Pattern matches are effectively "Partial Functions", of type PartialFunction[Input, Output] which is isomorphic to Input => Option[Output]. See Option Type.

State machine

A state machine is the use of `sealed trait` to represent all the possible states of a 'machine' in a hierarchical form

A great example is in the ParenthesesFoldingStateMachine.

What are the benefits of State machine folding, versus tail recursion?

State changes become more evident and you may be able to test sub-sequences and behaviours more easily.

Another possibility that opens up is that you may now support a stream of parentheses (of indeterminate size!) instead of a fixed-length String.

It works particularly well with scanLeft and scanRight and foldLeft and foldRight as well as Tail Recursion.

Simple parser to find text between brackets

sealed trait BracketParser {
  def next(char: Char): BracketParser
}

object BracketParser {
  case object NoBracketFound extends BracketParser {
    override def next(char: Char): BracketParser =
      if (char == '(') CollectingBracket("") else this
  }
  final case class CollectingBracket(textSoFar: String) extends BracketParser {
    override def next(char: Char): BracketParser =
      if (char == ')') CompletedCollection(textSoFar)
      else CollectingBracket(textSoFar + char)
  }
  final case class CompletedCollection(result: String) extends BracketParser {
    override def next(char: Char): BracketParser = this
  }
}

assert(
  "it works (yes?)"
    .foldLeft[BracketParser](BracketParser.NoBracketFound)(_.next(_)) ==
    BracketParser.CompletedCollection("yes?")
)

While this could be implemented simply with a Regular Expression, if you have any more variations, the complexity becomes unmanageable - this is where state machines really help out. Please see ParenthesesFoldingStateMachine for a good example.

Please also see the article: The most important streaming abstraction

Explanation

Please see the tail-recursive version for algorithm explanation: ParenthesesTailRecursive. The two are nearly equivalent, except that the folding version goes through the whole string (which may not be optimal - but there is an optimisation to make it more efficient using `.view`