Posted on May 16, 2023

The fastest way to find closing brackets

Recently I stumbled across the problem to find pairs of brackets in a string. A simple solution could be:

 let s = "the quick { brown } { fox } jumps" let ar = s.split("}").map((t,i,ar) => (i<ar.length-1) ? t+"}" : t ) console.log(ar)

This gives us a nice result, which was ok in my case:

0: 'the quick { brown }'
1: ' { fox }'
2: ' jumps'

This works, but fails for nested brackets. So, how can we deal with paired brackets? If we are evaluating strings on a character basis, we can implement some kind of fancy recursion, but this tends to be slow.

Here is my solution:

let s, tmp, part = '', ar = [] s = "the quick { brown { fox }} jumps" // split and restore brackets, last element has not bracket!  tmp = s.split("}").map((t, i, ar) => (i < ar.length - 1) ? t + '}' : t) // fill the result array 'ar' tmp.forEach((t) => { // set or extend part part = (part === '') ? t : part + t // find pairs if (part.split('{').length === part.split('}').length) { // equal number of brackets? ar.push(part.trim()) // => push out part = '' } }) console.log(ar)

part.split('{').length gives us the number of brackets + 1, so it is easy to compare the number of opening and closing brackets. This gives us the desired result