Matching parentheses algorithm in immutable/pure functional Scala with foldLeft and a finite-state machine by William Narmontas (Scala Algorithm #5 - view others)

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.

We have a plain tail-recursive solution as well.

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.

Get access to the Scala solution for £2.29 + VAT/GST.

If you already purchased the solution, please open the link to it from the e-mail we sent you.

Explanation

Please see the tail-recursive version for algorithm explanation. 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).

Scala-specifics

What are the benefits of Folding, versus tail recursion?

State changes become more evident and you may be able to test sub-sequences and behaviours more easily. In fact, what we have built here is an "FSM", a Finite-State Machine.

Another possibility that opens up is that you may now support a stream of parentheses (of indeterminate size!) instead of a fixed-length String. Consider looking up methods like scan and scanLeft.

`foldLeft`

This is like a for-loop iterating through each item, and returning a final result. For example, `List(1, 2, 3).foldLeft(5){case (accumulator, item) => item + accumulator}` has a result of `11`.

However, 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.