# How to get the longest bracket pairs from a string

In C#, we can use regular expression to do some balancing groups, like we can get

{<aa <bbb> <bbb> aa>, <<dfa>a>}


from

"xx <aa <bbb> <bbb> aa> yy<<dfa>a>"


using the regular expression

<((?<gro><)|(?<-gro>>)|[^<>])*(?(gro)(?!))>


We can get the syntax coloring with for instance RegexBuddy:

How to realize this in Mathematica?

I prefer using regular expression to do this, but Mathematica just supports some basic usage in regular expressions, and doesn't support advanced usage such as dynamic regular expression and balancing groups.

PS: Another example: how to get {[ab*[c]d], (b(x99))} from "dd9[ab*[c]d]esiddx(45x(b(x99))"?

• Do you mean in an expression, in a string, in a notebook? Or something else? Sep 2, 2016 at 15:05
– yode
Sep 2, 2016 at 15:10
• Just to summarize this question: The .NET flavor of regular expressions has a unique feature called "balancing groups". How can the same thing be achieved in Mathematica, which uses another flavor of regular expressions? Sep 2, 2016 at 15:57
• @C.E. We can do it by any method,I just want to use regular expressions more. :)
– yode
Sep 2, 2016 at 16:47
• Assuming you are trying to match the highlighted angle brackets expression above, the following piece of code does the job (although it requires applying twice the relevant function): StringReplace[ StringReplace[str, RegularExpression["(\\<[a-z]+\\>)+?"] :> "*"], RegularExpression["(\\<.+?\\>)"] :> "*"] where str is the expression to match. Sep 2, 2016 at 19:17

First Case

str = "xx <aa <bbb> <bbb> aa> yy<<dfa>a>";
StringCases[str,
RegularExpression["(?P<a><([^<>]|(?P>a))*>)"]
]
(* {"<aa <bbb> <bbb> aa>", "<<dfa>a>"} *)


This works as follows:

• (?P<a> ...) names a the pattern <([^<>]|(?P>a))*>.
• The string or substring matching this pattern must start with < and end with >.
• Within these characters, the pattern ([^<>]|(?P>a)) can be repeated 0 or more times.
• This subpattern says that no character can be < or >. If such a character is met while reading the string, then the pattern a is called by (?P>a) and we start again at bullet 2 with the substring starting with this character.

Second Case

str2 = "dd9[ab*[c]d]esiddx(45x(b(x99))"
StringCases[str2,
RegularExpression["(?P<a>(\$|$)([^\$$\$\$$$]|(?P>a))*(\$$|$$/extract_tex]))"] ] (* {"[ab*[c]d]", "(b(x99))"} *)  This works as above. Here, instead of < at the beginning of the (sub)string, we allow for [ or ( with (\$|$). The other modifications are in line with this change. Note that this regular expression may not be satisfying for cases such as str3 = "dd9[ab*[c]d)esiddx(45x(b(x99))"; (* The square bracket after d is replaced by a parenthesis. *) StringCases[str3, RegularExpression["(?P<a>(\\[|\$$)([^\\[\$\\($]|(?P>a))*(\$$|$$/extract_tex]))"] ] (* {"[ab*[c]d)", "(b(x99))"} *)  The first element starts with a [ and ends with ). This can be avoided by adding a pattern and a condition test on this pattern: StringCases[str3, RegularExpression["(?P<a>((?P<b>\$)|$)([^\\[\$\$$$]|(?P>a))*(?(b)\$$|$$/extract_tex]))"] ] (* {"[c]", "(b(x99))"} *)  The starting [ is referred to as b. The pattern (?(b)\$$|\\)) tells us that if b had a match, then the character to match should be ], or otherwise ).

• (+100) Related answer by WReach which is worthy to read along with this. Sep 9, 2016 at 11:25
• @AlexeyPopkov Thanks for the bounty!
– user31159
Sep 10, 2016 at 11:35
• Also strongly related: "Match opening and closing parentheses?" Jan 7, 2018 at 9:37

This works:

str = "xx <aa <bbb> <bbb> aa> yy<<dfa>a>";

StringCases[str, "<" ~~ Shortest@s___ ~~ ">" /; StringCount[s, "<"] == StringCount[s, ">"]]

{"<aa <bbb> <bbb> aa>", "<<dfa>a>"}


Or equivalently

StringCases[str,
s : RegularExpression["<.*?>"] /; StringCount[s, "<"] == StringCount[s, ">"]]

{"<aa <bbb> <bbb> aa>", "<<dfa>a>"}


Of course it isn't a pure regex approach: the method uses Condition. Similar approach is used in this answer of mine where an extended explanation of joint working of Condition together with lazy quantifier Shortest (or *? in regex) is given.

The second problem can be solved using two patterns of the same type as alternatives:

Clear[balanced]
balanced[{l_, r_}] :=
HoldPattern[(left : l ~~ Shortest@s___ ~~ right : r) /;
StringCount[s, left] == StringCount[s, right]]

str2 = "dd9[ab*[c]d]esiddx(45x(b(x99))";

StringCases[str2, balanced /@ {{"[", "]"}, {"(", ")"}}]

{"[ab*[c]d]", "(b(x99))"}


Or we can combine them into single pattern as follows:

StringCases[str2, (left : "[" | "(" ~~ Shortest@s___ ~~ right : "]" | ")") /;
MatchQ[{left, right}, {"[", "]"} | {"(", ")"}] &&
StringCount[s, left] == StringCount[s, right]]

{"[ab*[c]d]", "(b(x99))"}


Not a regular expression but counting the left and right separators to find positions where they're equal in number can find top level bracket pairs:

str1 = "xx<aa<bbb> <bbb>aa>yy<<dfa>a>";
str2 = "dd9[ab*[c]d]esiddx(45x(b(x99))";

f[l_, r_, str_] := Module[{sum, pos},
sum = Accumulate[StringCases[str, l | r] /. {l -> 1, r -> -1}];
pos = First /@ StringPosition[str, (l | r)];
Partition[(First /@
SplitBy[Transpose[{sum, pos}], #[[1]] == 0 &])[[All, 2]], 2]
];


Works for strings with complete pairs:

f["<", ">", str1]
f["[", "]", str2]
{{3, 19}, {22, 29}}
{{4, 12}}


But does not work for e.g. f["(", ")", str2]because str2 has one more opening ( than ).

• (+1) I used similar technique in this answer (section "Closing braces counting approach"). Sep 3, 2016 at 10:50

My original answer (seen in the comments) was based on the simple idea that you can first identify the bracketed expressions at the last (deeper) level (so to speak) and then progress 'upwards' by matching bracketed expressions one level up, by applying pattern matching based on regular expressions sequentially, as many times as there are levels of enclosed bracketed terms.

The original code did this for the demo string

str="xx <aa <bbb> <bbb> aa> yy<<dfa>a>"

by first identifying the inner bracketed expressions by means of

tmp=StringReplace[str, RegularExpression["(\\<[a-z]+\\>)+?"] :> "*"]

After the execution of the above code, tmp contains the following string

tmp="xx <aa * * aa> yy<*a>"

where an asterisk ('*') denotes successful matching.

Now, since there is another level of brackets, the approach is to apply the pattern matching once more as in:

StringReplace[tmp, RegularExpression["(\\<.+?\\>)"] :> "*"]

which outputs

"xx * yy*"

Note, once more, how the asterisks match bracketed expressions at this 'upper' level of the initial expression.

Therefore, it seems plausible to be able to construct a recursive pattern matching function (not presented here) that is based on regular expressions that performs the required task.