How to make balancing group capturing?

问题:

Let's say I have this text input.

 tes{}tR{R{abc}aD{mnoR{xyz}}}

I want to extract the ff output:

 R{abc}
 R{xyz}
 D{mnoR{xyz}}
 R{R{abc}aD{mnoR{xyz}}}

Currently, I can only extract what's inside the {}groups using balanced group approach as found in msdn. Here's the pattern:

 ^[^{}]*(((?'Open'{)[^{}]*)+((?'Target-Open'})[^{}]*)+)*(?(Open)(?!))$

Does anyone know how to include the R{} and D{} in the output?

回答1:

I think that a different approach is required here. Once you match the first larger group R{R{abc}aD{mnoR{xyz}}} (see my comment about the possible typo), you won't be able to get the subgroups inside as the regex doesn't allow you to capture the individual R{ ... } groups.

So, there had to be some way to capture and not consume and the obvious way to do that was to use a positive lookahead. From there, you can put the expression you used, albeit with some changes to adapt to the new change in focus, and I came up with:

(?=([A-Z](?:(?:(?'O'{)[^{}]*)+(?:(?'-O'})[^{}]*?)+)+(?(O)(?!))))

[I also renamed the 'Open' to 'O' and removed the named capture for the close brace to make it shorter and avoid noises in the matches]

On regexhero.net (the only free .NET regex tester I know so far), I got the following capture groups:

1: R{R{abc}aD{mnoR{xyz}}}
1: R{abc}
1: D{mnoR{xyz}}
1: R{xyz}

Breakdown of regex:

(?=                         # Opening positive lookahead
    ([A-Z]                  # Opening capture group and any uppercase letter (to match R & D)
        (?:                 # First non-capture group opening
            (?:             # Second non-capture group opening
                (?'O'{)     # Get the named opening brace
                [^{}]*      # Any non-brace
            )+              # Close of second non-capture group and repeat over as many times as necessary
            (?:             # Third non-capture group opening
                (?'-O'})    # Removal of named opening brace when encountered
                [^{}]*?     # Any other non-brace characters in case there are more nested braces
            )+              # Close of third non-capture group and repeat over as many times as necessary
        )+                  # Close of first non-capture group and repeat as many times as necessary for multiple side by side nested braces
        (?(O)(?!))          # Condition to prevent unbalanced braces
    )                       # Close capture group
)                           # Close positive lookahead

---

The following will not work in C#

I actually wanted to try out how it should be working out on the PCRE engine, since there was the option to have recursive regex and I think it was easier since I'm more familiar with it and which yielded a shorter regex :)

(?=([A-Z]{(?:[^{}]|(?1))+}))

regex101 demo

(?=                    # Opening positive lookahead
    ([A-Z]             # Opening capture group and any uppercase letter (to match R & D)
        {              # Opening brace
            (?:        # Opening non-capture group
                [^{}]  # Matches non braces
            |          # OR
                (?1)   # Recurse first capture group
            )+         # Close non-capture group and repeat as many times as necessary
        }              # Closing brace
    )                  # Close of capture group
)                      # Close of positive lookahead

回答2:

I'm not sure a single regex would be able to suit your needs: these nested substrings always mess it up.

One solution could be the following algorithm (written in Java, but I guess the translation to C# won't be that hard):

/**
 * Finds all matches (i.e. including sub/nested matches) of the regex in the input string.
 * 
 * @param input
 *          The input string.
 * @param regex
 *          The regex pattern. It has to target the most nested substrings. For example, given the following input string
 *          <code>A{01B{23}45C{67}89}</code>, if you want to catch every <code>X{*}</code> substrings (where <code>X</code> is a capital letter),
 *          you have to use <code>[A-Z][{][^{]+?[}]</code> or <code>[A-Z][{][^{}]+[}]</code> instead of <code>[A-Z][{].+?[}]</code>.
 * @param format
 *          The format must follow the <a href= "http://docs.oracle.com/javase/7/docs/api/java/util/Formatter.html#syntax" >format string
 *          syntax</a>. It will be given one single integer as argument, so it has to contain (and to contain only) a <code>%d</code> flag. The
 *          format must not be foundable anywhere in the input string. If <code>null</code>, <code>ééé%dèèè</code> will be used.
 * @return The list of all the matches of the regex in the input string.
 */
public static List<String> findAllMatches(String input, String regex, String format) {

    if (format == null) {
        format = "ééé%dèèè";
    }
    int counter = 0;
    Map<String, String> matches = new LinkedHashMap<String, String>();
    Pattern pattern = Pattern.compile(regex);
    Matcher matcher = pattern.matcher(input);

    // if a substring has been found
    while (matcher.find()) {
        // create a unique replacement string using the counter
        String replace = String.format(format, counter++);
        // store the relation "replacement string --> initial substring" in a queue
        matches.put(replace, matcher.group());
        String end = input.substring(matcher.end(), input.length());
        String start = input.substring(0, matcher.start());
        // replace the found substring by the created unique replacement string
        input = start + replace + end;
        // reiterate on the new input string (faking the original matcher.find() implementation)
        matcher = pattern.matcher(input);
    }

    List<Entry<String, String>> entries = new LinkedList<Entry<String, String>>(matches.entrySet());

    // for each relation "replacement string --> initial substring" of the queue
    for (int i = 0; i < entries.size(); i++) {
        Entry<String, String> current = entries.get(i);
        // for each relation that could have been found before the current one (i.e. more nested)
        for (int j = 0; j < i; j++) {
            Entry<String, String> previous = entries.get(j);
            // if the current initial substring contains the previous replacement string
            if (current.getValue().contains(previous.getKey())) {
                // replace the previous replacement string by the previous initial substring in the current initial substring
                current.setValue(current.getValue().replace(previous.getKey(), previous.getValue()));
            }
        }
    }

    return new LinkedList<String>(matches.values());
}

Thus, in your case:

String input = "tes{}tR{R{abc}aD{mnoR{xyz}}}";
String regex = "[A-Z][{][^{}]+[}]";
findAllMatches(input, regex, null);

Returns:

R{abc}
R{xyz}
D{mnoR{xyz}}
R{R{abc}aD{mnoR{xyz}}}

回答3:

Balancing groups in .Net regular expressions give you control over exactly what to capture, and the .Net regex engine keeps a full history of all captures of the group (unlike most other flavors that only capture the last occurrence of each group).

The MSDN example is a little too complicated. A simpler approach for matching nestes structures would be:

(?>
    (?<O>)\p{Lu}\{   # Push to the O stack, and match an upper-case letter and {
    |                # OR
    \}(?<-O>)        # Match } and pop from the stack
    |                # OR
    \p{Ll}           # Match a lower-case letter
)+
(?(O)(?!))        # Make sure the stack is empty

or in a single line:

(?>(?<O>)\p{Lu}\{|\}(?<-O>)|\p{Ll})+(?(O)(?!))

Working example on Regex Storm

In your example it also matches the "tes" at the start of the string, but don't worry about that, we're not done.

With a small correction we can also capture the occurrences between the R{...} pairs:

(?>(?<O>)\p{Lu}\{|\}(?<Target-O>)|\p{Ll})+(?(O)(?!))

Each Match will have a Group called "Target", and each such Group will have a Capture for each occurrences - you only care about these captures.

Working example on Regex Storm - Click on Table tab and examine the 4 captures of ${Target}

See also:

• What are regular expression Balancing Groups?