Recursive pattern in NSRegularExpression

Question

Similar question to Recursive pattern in regex, but in Objective-C.

I want to find the ranges or substrings of outer brackets.

Example input:

NSString *input = @"{a {b c}} {d e}";

Example result:

// yeah, I know, we can't put NSRange in an array, it is just to illustrate
NSArray *matchesA = @[NSMakeRange(0, 9), NSMakeRange(10, 5)];  // OK
NSArray *matchesB = @[NSMakeRange(1, 7), NSMakeRange(11, 3)];  // OK too

NSArray *outputA = @[@"{a {b c}}", @"{d e}"];  // OK
NSArray *outputB = @[@"a {b c}", @"d e"];      // OK too

Unfortunately, NSRegularExpression does not accept ?R apparently. Any alternative to match the outer brackets?

Answer 1

Going for manual solution.

Assuming:

NSString *text = @"{a {b c}} {d e}";

nice solution without regex

NSUInteger len = text.length;
unichar buffer[len + 1];
[text getCharacters:buffer range:NSMakeRange(0, len)];
NSMutableOrderedSet<NSValue *> *results = [NSMutableOrderedSet orderedSet];
NSInteger depth = 0;
NSUInteger location = NSNotFound;
for (NSUInteger i = 0; i < len; i++) {
    if (buffer[i] == '{')
    {
        if (depth == 0)
            location = i;
        depth++;
    }
    else if (buffer[i] == '}')
    {
        depth--;
        if (depth == 0)
            [results addObject:[NSValue valueWithRange:NSMakeRange(location, i - location + 1)]];
    }
}

return results;

ugly solution with regex

NSString *innerPattern = @"\\{[^{}]*\\}";
NSRegularExpression *innerBracketsRegExp = [NSRegularExpression regularExpressionWithPattern:innerPattern options:0 error:nil];
// getting deepest matches
NSArray<NSTextCheckingResult *> *deepestMatches = [innerBracketsRegExp matchesInString:text options:0 range:NSMakeRange(0, text.length)];
// stripping them from text
text = [text stringByReplacingOccurrencesOfString:innerPattern withString:@"" options:NSRegularExpressionSearch range:NSMakeRange(0, text.length)];
// getting new deepest matches
NSArray<NSTextCheckingResult *> *depth2Matches = [innerBracketsRegExp matchesInString:text options:0 range:NSMakeRange(0, text.length)];

// merging the matches of different depth
NSMutableOrderedSet<NSValue *> *results = [NSMutableOrderedSet orderedSet];
for (NSTextCheckingResult *cr in depth2Matches) {
    [results addObject:[NSValue valueWithRange:cr.range]];
}
for (NSTextCheckingResult *cr in deepestMatches) {
    __block BOOL merged = NO;
    [results enumerateObjectsUsingBlock:^(NSValue * _Nonnull value, NSUInteger idx, BOOL * _Nonnull stop) {
        if (merged)
            [results replaceObjectAtIndex:idx withObject:[NSValue valueWithRange:NSMakeRange(value.rangeValue.location + cr.range.length, value.rangeValue.length)]];
        else if (NSLocationInRange(cr.range.location, value.rangeValue))
        {
            [results replaceObjectAtIndex:idx withObject:[NSValue valueWithRange:NSMakeRange(value.rangeValue.location, value.rangeValue.length + cr.range.length)]];
            merged = YES;
        }
        else if (cr.range.location < value.rangeValue.location)
        {
            [results insertObject:[NSValue valueWithRange:cr.range] atIndex:idx];
            merged = YES;
        }
    }];
    if (!merged)
        [results addObject:[NSValue valueWithRange:cr.range]];
}

return results;