Recursion

object MatchingBrackets {
  private val brackets = Map('(' -> ')', '{' -> '}', '[' -> ']')
  private val ends = Set(')', '}', ']')

  private def isValid(stack: List[Char], char: Char): Boolean =
    stack.length > 0 && stack.head == char
  private def safeTail(stack: List[Char]): List[Char] = {
    if (!stack.isEmpty) stack.tail else stack
  }

  def isPaired(input: String): Boolean = {
    isPairedRecur(input, List[Char]())
  }

  @scala.annotation.tailrec
  private def isPairedRecur(input: String, stack: List[Char]): Boolean = {
    if (input.isEmpty) return stack.isEmpty
    (input.head, stack) match {
      case (chr, stack) if ends.contains(chr) =>
        if (isValid(stack, chr))
          isPairedRecur(input.tail, safeTail(stack))
        else
          false
      case (chr, stack) if (brackets.contains(chr)) =>
        isPairedRecur(input.tail, brackets(chr) :: stack)
      case _ => isPairedRecur(input.tail, stack)
    }
  }
}

This approach starts by defining a Map for associating beginning brackets with their ending brackets. A Set is defined to hold the ending brackets.

A private helper method is defined to determine if an ending bracket is valid. Another private helper method returns all but the first element from a List, or returns the List as is if it is already empty.

The isPaired() method returns the result of calling the private recursive method, to which it passes the input String. and an empty List for the "stack".

The recursive method is annotated with the @tailrec annotation to verify that the method can be compiled with tail call optimization.

A tail call is a particular form of recursion where the last call in the method is a call to the same method and nothing else.

In other words, if the last call in recurMe() is recurMe(arg1, arg2) + 1, the + 1 makes the recursion non-tail recursive.

If the last call in recurMe() is recurMe(arg1, arg2, acc + 1), then the recursion is a tail call, because only the method is being called with no other operation being peformed on it.

If the input String is empty, then the method returns if the "stack" List is empty.

The head method is used to get the first character in the input String. It is wrapped in a tuple with the "stack" List, which is passed to the match.

The pattern matching uses the contains() method to check if the character is an ending bracket. If so, and it is valid, then the recursive method calls itself, passing the tail of the input String and all but the first element of the "stack" List. If it is not a valid ending bracket, then the recursive method immediately returns false.

If the character is not an ending bracket, then the contains() method is used to check for it being a beginning bracket. If so, then the recursive method calls itself, passing the tail of the input String and the the associated ending bracket prepended to the "stack" List.

Note that the operations on the List create a new List, thus supporting immutability.

If the character is not any bracket, then the underscore (_) wildcard is used to have the the recursive method call itself, passing the tail of the input String and the "stack" List as is.