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

Algorithm goal

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

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` (View). Here is the state transition diagram of this implementation. (this is © from www.scala-algorithms.com)

stateDiagram
    [*] --> BalancedStack
    BalancedStack --> [*]
    BalancedStack --> Stacked
    BalancedStack --> Failed
    Stacked --> BalancedStack
    Stacked --> Failed
    Failed --> [*]
            
         
        

Scala Concepts & Hints

State machine

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

Read more

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")

Read more

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 =
  items.foldLeft(initialState)(f)

Read more

Stack Safety

Stack safety is present where a function cannot crash due to overflowing the limit of number of recursive calls.

This function will work for n = 5, but will not work for n = 2000 (crash with java.lang.StackOverflowError) - however there is a way to fix it :-)

In Scala Algorithms, we try to write the algorithms in a stack-safe way, where possible, so that when you use the algorithms, they will not crash on large inputs. However, stack-safe implementations are often more complex, and in some cases, overly complex, for the task at hand.

def sum(from: Int, until: Int): Int =
  if (from == until) until else from + sum(from + 1, until)

def thisWillSucceed: Int = sum(1, 5)

def thisWillFail: Int = sum(1, 300)

Read more

State machine

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

Read more

Algorithm in Scala

36 lines of Scala (version 2.13).

This solution is available for purchase!

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

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

Test cases in Scala

assert(parenthesesAreBalancedFolding("()"))
assert(parenthesesAreBalancedFolding("[()]"))
assert(parenthesesAreBalancedFolding("{[()]}"))
assert(parenthesesAreBalancedFolding("([{{[(())]}}])"))
assert(!parenthesesAreBalancedFolding("{{[]()}}}}"))
assert(!parenthesesAreBalancedFolding("{[(])}"))
def parenthesesAreBalancedFolding(s: String): Boolean = ???