Find this approach useful?
Share it around!
object MatchingBrackets {
private val brackets = Map('(' -> ')', '{' -> '}', '[' -> ']')
private val ends = Set(')', '}', ']')
def isValid(stack: List[Char], char: Char): Boolean =
stack.length > 0 && stack.head == char
def safeTail(stack: List[Char]): List[Char] = {
if (!stack.isEmpty) stack.tail else stack
}
def isPaired(input: String): Boolean = {
input
.foldLeft((List[Char](), true))((tup, chr) =>
tup match {
case (stack, valid) if ends.contains(chr) =>
(safeTail(stack), valid && isValid(stack, chr))
case (stack, valid) if (brackets.contains(chr)) =>
(brackets(chr) :: stack, valid)
case _ => tup
}
) match {
case (stack, isValid) => stack.isEmpty && isValid
}
}
}
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 starts by calling the foldLeft() method on the input String.
It is initialized with an empty List for the "stack" and true for a validity flag, both wrapped in a tuple.
Note that the immutable Stack
exists only for historical reason and as an analogue of mutable stacks.
Instead of an immutable stack you can just use a list.
The mutable Stack was deprecated since version 2.12.0.
Stack is an inelegant and potentially poorly-performing wrapper around List.
Use a List assigned to a var instead.
The tuple and each character from the input is passed into the lambda.
A match is used to destructure the tuple and uses the contains() method
to check if the character is an ending bracket.
If so, then a new tuple is created, passing all but the first element of the List and setting the validity flag to if
it was already true and whether the ending bracket is valid.
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 a new tuple is created, passing the associated ending bracket prepended to the List along with the validity flag as is.
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 pass the tuple as is to the next iteration of foldLeft().
After the foldLeft() is done, its final tuple is passed to a match, where it is destructured.
The method returns whether the stack List is empty and if the validity flag is true.
