String matching balanced pairs of braces

Question

I am trying to extract from a string in Mathematica all instances of

\newcommand{ABC}{DEF}

Where ABC and DEF are general expressions that may contain matching { and }.

Clearly, if ABC and DEF do not contain { or } the following Mathematica command will do the job:

StringCases[string, 
 Shortest["\\newcommand{" ~~ __ ~~ "}{" ~~ __ ~~ "}"]]

as can be seen as applied to

string = "asdkashdkj\\newcommand{ABC}{DEF}asdahgsjagsd\\newcommand{\
ABC}{DwewEF}ahgdajhdgj\\newcommand{ABC}{DEF}";

unfortunately, once ABC or DEF get more complex, e.g.:

string = "\\newcommand{ABC{asdas}{asdsad}}{DEF}";

I no longer get what I want, which would be \\newcommand{ABC{asdas}{asdsad}}{DEF}.

Is there any easy way to do this?

Thanks!

Answer 1

You can test whether braces are balanced with something like (version simplified by Guess who it is.):

ClearAll[balancedBracesQ]
balancedBracesQ[str_String] := StringCount[str, "{"] === StringCount[str, "}"]

And use it in string pattern in following way:

StringCases[
    "a\\newcommand{ABC{asdas}{asdsad}}{DEF{x}y}asdkashdkj\
\\newcommand{ABC}{DEF}asdahgsjagsd\\newcommand{ABC}{DwewEF}ahgdajhdgj\
\\newcommand{ABC}{DEF}"
    , 
    Shortest[
        "\\newcommand{" ~~ (arg1__ /; balancedBracesQ[arg1]) ~~ 
        "}{" ~~ (arg2__ /; balancedBracesQ[arg2]) ~~ "}"
    ]
]
(* {
    "\\newcommand{ABC{asdas}{asdsad}}{DEF{x}y}",
    "\\newcommand{ABC}{DEF}",
    "\\newcommand{ABC}{DwewEF}",
    "\\newcommand{ABC}{DEF}"
} *)

---

Since useless benchmarks are always fun, let's make some.

Needs["GeneralUtilities`"]

ClearAll[testedFunctions, "Global`extractNewCommnad*"]

extractNewCommnadOP[str_String] := StringCases[str, Shortest["\\newcommand{" ~~ __ ~~ "}{" ~~ __ ~~ "}"]]
extractNewCommnadWReach[str_String] := StringCases[str, RegularExpression["\\\\newcommand({([^{}]|(?1))*})(?1)"]]
With[{balancedBracesQ = StringCount[#, "{"] === StringCount[#, "}"] &},
    extractNewCommnadJkuczm[str_String] := StringCases[str, Shortest["\\newcommand{" ~~ (arg1__ /; balancedBracesQ[arg1]) ~~ "}{" ~~ (arg2__ /; balancedBracesQ[arg2]) ~~ "}"]]
]
extractNewCommnadAmr[str_String] := Cases[Characters[str] //. {{a___, "{", inside : Except["{" | "}"] ..., "}", b___} :> {a, \[BlackKing][inside], b}, Flatten[{a___, Characters["\\newcommand"], in1_\[BlackKing], in2_\[BlackKing], b___}] :> {a, \[WhiteQueen][in1, in2], b}} /. {\[BlackKing] -> ("{" <> StringJoin[##] <> "}" &), \[WhiteQueen] -> NewCommand}, nc_NewCommand :> "\\newcommand" <> nc[[1]] <> nc[[2]]]

testedFunctions = Symbol /@ Names["Global`extractNewCommnad*"];

Number of occurrences of searched pattern:

BenchmarkPlot[Select[testedFunctions, #@"\\newcommand{x}{y}\\newcommand{x}{y}" === {"\\newcommand{x}{y}", "\\newcommand{x}{y}"} &], StringRepeat["\\newcommand{x}{y}", #] &]

Length of argument of "newcommand":

BenchmarkPlot[Select[testedFunctions, #@"\\newcommand{xx}{y}" === {"\\newcommand{xx}{y}"} &], "\\newcommand{" <> StringRepeat["x", #] <> "}{y}" &]

Number of braces pairs inside "newcommand" argument:

BenchmarkPlot[Select[testedFunctions, #@"\\newcommand{{x}}{{y}}" === {"\\newcommand{{x}}{{y}}"} &], "\\newcommand{" <> StringRepeat["{x}", #] <> "}{" <> StringRepeat["{y}", #] <> "}" &]

Number of braces pairs outside of "newcommand":

BenchmarkPlot[Select[testedFunctions, #@"\\newcommand{x}{y}{z}" === {"\\newcommand{x}{y}"} &], "\\newcommand{x}{y}" <> StringRepeat["{z}", #] &]

Clearly WReach's solution wins hands down.

Answer 2

I suppose that the set of answers won't be complete without the contribution of a cryptic RegularExpression...

$pattern = RegularExpression["\\\\newcommand({([^{}]|(?1))*})(?1)"];

The pattern works for simple cases:

StringCases[#, $pattern]& @
  "XXX\\newcommand{ABC}{DEF}XXX\\newcommand{GHI}{JKL}XXX\\newcommand{MNO}{PQR}"

(* { "\\newcommand{ABC}{DEF}",
     "\\newcommand{GHI}{JKL}", 
     "\\newcommand{MNO}{PQR}" } *)

... and more complicated cases:

StringCases[#, $pattern]& @
  "\\newcommand{XXX{ABC}XXX{DEF}XXX}{XXX{GHI}XXX}\\newcommand{JKL}{MNO}\\oldcommand{XXX}"

(* { "\\newcommand{XXX{ABC}XXX{DEF}XXX}{XXX{GHI}XXX}",
     "\\newcommand{JKL}{MNO}" } *)

... and even cases with nested occurrences:

StringCases[#, $pattern]& @
  "\\newcommand{ABC}{\\newcommand{DEF}{\\newcommand{GHI}{JKL}}}\\oldcommand{XXX}{XXX}"

(* { "\\newcommand{ABC}{\\newcommand{DEF}{\\newcommand{GHI}{JKL}}}" } *)

If desired, we can use Overlaps -> True to extract those nested cases as well:

StringCases[#, $pattern, Overlaps -> True]& @
  "\\newcommand{ABC}{\\newcommand{DEF}{\\newcommand{GHI}{JKL}}}\\oldCommand{XXX}{XXX}"

(* { "\\newcommand{ABC}{\\newcommand{DEF}{\\newcommand{GHI}{JKL}}}",
     "\\newcommand{DEF}{\\newcommand{GHI}{JKL}}",
     "\\newcommand{GHI}{JKL}" } *)

What Does All This Gibberish Mean?

Let's consider the pattern in detail:

RegularExpression["\\\\newcommand({([^{}]|(?1))*})(?1)"]

\\\\ matches a single backslash. The desired single backslash is escaped once to account for Mathematica string syntax. Each resulting backslash must then be escaped a second time to account for regular expression syntax. Thus we end up with four backslashes. newcommand, of course, matches that self-same literal text.

The main part of the pattern, in outline, looks like this: ({...})(?1). {...} matches some text surrounded by braces. This pattern is "captured" by wrapping it with parentheses: ({...}). This pattern is then re-used by inserting a back-reference to it: (?1). The significance of the 1 is that it is referencing the #1 (i.e. first) capture group. Note that (?1) does not refer to the text matched by the first pattern, but rather it refers to the pattern itself. The construction will match different text from the first occurrence, but according to the same pattern.

Now let's return to the subpattern which we elided above: ([^{}]|(?1))*. This defines a second capture group containing alternatives which can be repeated zero or more times, (...|...)*. Each occurrence must be either a non-brace character ([^{}]) or any text that matches that outer pattern #1 that we captured earlier.

Purists will note that we do not need to capture these inner alternatives, so the inner group should really be expressed as a non-capturing group, (?:...)*. This detail is largely irrelevant in practice, so I opted to reduce the amount of line noise in the pattern.

Using Named Patterns For Safety

As discussed in (72724), using positional pattern back-references such as (?1) can sometimes give unpredictable results in Mathematica. We can change the pattern to use named back-references for safety:

$pattern2 = RegularExpression["\\\\newcommand(?P<x>{([^{}]|(?P>x))*})(?P>x)"];

StringCases[#, $pattern2, Overlaps -> True]& @
  "\\newcommand{ABC}{\\newcommand{DEF}{\\newcommand{GHI}{JKL}}}"

(* { "\\newcommand{ABC}{\\newcommand{DEF}{\\newcommand{GHI}{JKL}}}",
     "\\newcommand{DEF}{\\newcommand{GHI}{JKL}}",
     "\\newcommand{GHI}{JKL}" } *)

The first capture group (...) is replaced by the syntax (?P<x>...) which assigns the name x to the group. Each pattern back-reference (?1) is then replaced with an explicit back-reference to that name, (?P>x).

Answer 3

Here is my possibly over-engineered, potentially incomplete approach:

string = "asdkashdkj\\newcommand{ABC}{DEF}asdahgsjagsd\\newcommand{ABC}{DwewEF}ahgdajhdgj\\newcommand{ABC}{DEF}\\newcom\\newcommand{ABC{asdas}{asds{}ad}}{DEF}";

step1 = Characters[string] //. {
   {a___, "{", inside : Except["{" | "}"] ..., "}", 
     b___} :> {a, \[BlackKing][inside], b},
   Flatten[{a___, Characters["\\newcommand"], in1_\[BlackKing], 
      in2_\[BlackKing], b___}] :> {a, \[WhiteQueen][in1, in2], b}}

step2 = step1 /. {
    \[BlackKing] -> ("{" <> StringJoin[##] <> "}" &),
    \[WhiteQueen] -> NewCommand};

step3 = Cases[step2, _NewCommand];

Grid[List @@@ step3, Dividers -> All, FrameStyle -> LightGray]

Regardless of its potential misgivings, notice how particularly cool this program is: