Balanced parentheses algorithm in immutable/pure functional Scala with tail-call recursion optimisation by William Narmontas (Scala Algorithm #1)

Problem

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

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.

Solution

View on Scastie (online Scala code playground, in a new window) if you would like to play around with this code, run it, add new test cases, all from your web browser without installing Scala.

val OpenToClose = Map(
  '{' -> '}',
  '[' -> ']',
  '(' -> ')'
)

val CloseToOpen = OpenToClose.map { case (k, v) => v -> k }.toMap

def parenthesesAreBalanced(s: String): Boolean = {
  if (s.isEmpty) true
  else {

    /**
    @position is the current position to look at
    @stack is the stack of open parentheses
     **/
    @scala.annotation.tailrec
    def go(position: Int, stack: List[Char]): Boolean = {
      /**
      Terminating condition - when we reach the end, position == s.length is true.
      When we reach it, we must check if the stack of opening characters is empty.
       */
      if (position == s.length) stack.isEmpty
      else {
        val char = s(position)
        val isOpening = OpenToClose.contains(char)
        val isClosing = CloseToOpen.contains(char)
        if (isOpening)
          go(position + 1, char :: stack)
        else if (isClosing) { // is closing
          val expectedCharForMatching = CloseToOpen(char)
          stack match {
            case `expectedCharForMatching` :: rest =>
              go(position + 1, rest)
            case _ =>
              false
          }
        } else false
      }
    }

    go(position = 0, stack = List.empty)
  }
}

/** Test cases **/
def test(f: String => Boolean): Unit = {
  assert(f("()"))
  assert(f("[()]"))
  assert(f("{[()]}"))
  assert(f("([{{[(())]}}])"))

  assert(!f("{{[]()}}}}"))
  assert(!f("{{[](A}}}}"))
  assert(!f("{[(])}"))
}

test(parenthesesAreBalanced)

Explanation

Also please find an alternative solution using a foldLeft state machine which makes a streamed implementation possible.

This means that we need to keep track of the most recent opening bracket, and if the next bracket we approach is a closing bracket that is not the latest bracket, we terminate with a failure, whereas if it is another opening bracket, this is the bracket we consider as the latest, and if it is another closing bracket that matches the latest opening bracket, the new latest opening bracket is "popped". This description is enough to suggest to us that we should use a "stack" structure, and implement our logic as described.

In Scala, a List is equivalent to a stack, it is a structure in the form List[T] = ::(head: T, tail: List[T]) | Nil

We could solve this problem in a standard mutable style, but this would not be the immutable Scala way of doing things.

In Scala, tail recursion enables you to rewrite a mutable structure such as a while-loop, into an immutable structure.

Effectively, in rough pseudo-code,



    go(params) =
      if ( terminate(params) )
        computeResult(fromParams = params)
      else
        go(params = nextIterationParams(fromParams = params))

    result = go(initialParams)
        

becomes (after compiling):



    var currentParams = initialParams
    while(!terminate(currentParams)) {
      currentParams = nextIterationParams(fromParams = currentParams)
    }
    result = computeResult(currentParams)
        

What are the benefits of tail recursion?

Tail recursion in Scala utilises a principle known as tail-call optimisation. It allows one to write iterative algorithms (that would otherwise would be complicated while-loops) in immutable form.

What are the benefits of immutability?

It becomes easier to reason about your code, and you always know that you can re-run a function as many times as you wish without causing unexpected side effects.