Checking NSString for balanced delimiters

Question

My input (NSString)can be ("text"), {("text")} or (“text”){{“text”}}. In all those cases, I have to make sure that an opening delimiter ({) gets its own closing delimiter (}).

For example, {{“text”}) should be marked as an error.

I'm trying NSScanner to accomplish this, and also tried reversing the string and comparing each character looking for its opposite, but've been having some trouble.

What would be the best approach?

This is the latest way I tried going:

NSMutableString *reversedString = [NSMutableString string];
NSInteger charIndex = [_expressionTextField.text length];
while (charIndex > 0) {
    charIndex--;
    NSRange subStrRange = NSMakeRange(charIndex, 1);
    [reversedString appendString:[_expressionTextField.text substringWithRange:subStrRange]];
}

NSString *mystring = _expressionTextField.text;

NSLog(@"%@", reversedString);
for (int i = 0; i < reversedString.length; i++) {
    if ([mystring characterAtIndex:i] == [reversedString characterAtIndex:(reversedString.length -i)]) {
        NSLog(@"Closed the bracket");
    }
}

Answer 1

I had a crack at it, using NSScanner. I think this'll be a little faster than vikingosegundo's for very long strings, because I'm just marching straight through one character at a time. There's no searching or substring-making. For most purposes, it probably won't make a difference.

/// Takes a string and a dictionary of delimiter pairs in which the keys are the
/// opening characters of the pairs and the values the closers. Returns YES if the 
/// delimiters in the string are balanced, otherwise NO. Ignores any characters
/// not present in the dictionary.
///
/// Note: Does not support multi-character delimiters.
BOOL stringHasBalancedDelimiters(NSString * s, NSDictionary * delimiterPairs)
{
    NSMutableArray * delimiterStack = [NSMutableArray array];

    NSString * openers = [[delimiterPairs allKeys] componentsJoinedByString:@""];
    NSString * closers = [[delimiterPairs allValues] componentsJoinedByString:@""];
    NSCharacterSet * openerSet = [NSCharacterSet characterSetWithCharactersInString:openers];
    NSCharacterSet * closerSet = [NSCharacterSet characterSetWithCharactersInString:closers];
    NSMutableCharacterSet * delimiterSet = [openerSet mutableCopy];
    [delimiterSet formUnionWithCharacterSet:closerSet];

    NSScanner * scanner = [NSScanner scannerWithString:s];

    while( ![scanner isAtEnd] ){

        // Move up to the next delimiter of either kind
        [scanner scanUpToCharactersFromSet:delimiterSet intoString:nil];

        NSString * delimiter;
        // Could be a closer.
        if( [scanner WSSScanSingleCharacterFromSet:closerSet intoString:&delimiter] ){
            // Got a paired closer; pop the opener off the stack and continue.
            NSString * expected = [delimiterStack lastObject];
            if( [expected isEqualToString:delimiter] ){
                [delimiterStack removeLastObject];
                continue;
            }
            // Not the right closer, but if the members of the pair are
            // identical, treat as an opener.
            else if( [delimiterPairs[delimiter] isEqualToString:delimiter] ){
                [delimiterStack addObject:delimiterPairs[delimiter]];
                continue;
            }
            // Otherwise this is a failure.
            else {
                return NO;
            }
        }

        // Otherwise it's an opener (or nothing, thus the if).
        if( [scanner WSSScanSingleCharacterFromSet:openerSet intoString:&delimiter] ){
            [delimiterStack addObject:delimiterPairs[delimiter]];
        }
    }

    // Haven't failed and nothing left to pair? Success.
    return [delimiterStack count] == 0;
}

I added a method to NSScanner to make my life easier. This way we don't have to scan a bunch of characters (since delimiters can be next to each other) and then split them apart into separate NSStrings.

@interface NSScanner (WSSSingleCharacter)

- (BOOL)WSSScanSingleCharacterFromSet:(NSCharacterSet *)charSet intoString:(NSString * __autoreleasing *)string;

@end

@implementation NSScanner (WSSSingleCharacter)

- (BOOL)WSSScanSingleCharacterFromSet:(NSCharacterSet *)charSet intoString:(NSString *__autoreleasing *)string
{
    if( [self isAtEnd] ) return NO;

    NSUInteger loc = [self scanLocation];
    unichar character = [[self string] characterAtIndex:loc];

    if( [charSet characterIsMember:character] ){
        if( string ){
            *string = [NSString stringWithCharacters:&character length:1];
        }
        [self setScanLocation:loc+1];
        return YES;
    }
    else {
        return NO;
    }
}

@end

A few tests:

NSDictionary * delimiterPairs = @{@"{" : @"}",
                                  @"[" : @"]",
                                  @"\"" : @"\"",
                                  @"'" : @"'",
                                  @"(" : @")"};
// Balanced simple nesting
NSString * s = @"{(\"text\")}";
// Balanced complex nesting
NSString * t = @"{({}'(text)[\"\"]')text}";
// Balanced symmetrical delimiters at beginning and end of string, as
// well as after both an opener and closer from a different pair
NSString * u = @"\"\"(\"text\"\"\")\"\"";
// Out of order
NSString * v = @"{(\"text)\"}";
// Unpaired at the beginning
NSString * w = @"\"{text}";
// Unpaired at the end
NSString * x = @"\"'text'\"(";
// Unpaired in the middle
NSString * y = @"[(text)']";

for( NSString * string in @[s, t, u, v, w, x, y] ){
    BOOL paired = stringHasBalancedDelimiters(string, delimiterPairs);
    NSLog(@"%d", paired);
}

Answer 2

You must keep track of the latest delimiter symbols and there occurrence.

You can us a stack for that: through each found opening delimiter on it. When you find the right closing one, delete the last one.

#import <Foundation/Foundation.h>

int main(int argc, const char * argv[])
{

    @autoreleasepool {

        NSMutableArray *stack = [NSMutableArray array];
        NSString *text = @"(“text”){{“text”}}}";
        NSArray *delimiterPairs = @[@[@"(", @")"],@[@"{", @"}"]];

        NSMutableString *openingDelimiters = [@"" mutableCopy];
        NSMutableString *closingDelimiters = [@"" mutableCopy];
        [delimiterPairs enumerateObjectsUsingBlock:^(NSArray *pair, NSUInteger idx, BOOL *stop) {
            [openingDelimiters appendString:pair[0]];
            [closingDelimiters appendString:pair[1]];
        }];

        NSScanner *scanner = [NSScanner scannerWithString:text];
        __block BOOL unbalanced = NO;
        while (![scanner isAtEnd] && !unbalanced) {
            [scanner scanUpToCharactersFromSet:[NSCharacterSet characterSetWithCharactersInString:[openingDelimiters stringByAppendingString:closingDelimiters]]
                                    intoString:NULL];
            NSString *currentDelimiter = [text substringWithRange:NSMakeRange([scanner scanLocation], 1)];
            if ([openingDelimiters rangeOfString:currentDelimiter].location != NSNotFound) {
                [stack addObject:currentDelimiter];
            } else {
                [delimiterPairs enumerateObjectsUsingBlock:^(NSArray *pair, NSUInteger idx, BOOL *stop) {
                    if([currentDelimiter isEqualToString:pair[1]]){
                        if([stack count] == 0) {
                            unbalanced = YES;
                        } else if ([[stack lastObject] isEqualToString:pair[0]]) {
                            [stack removeLastObject];
                        }
                        *stop = YES;
                    }
                }];
            }
            scanner.scanLocation +=1;
        }
        if ([stack count])
            unbalanced = YES;            
    }
    return 0;
}

If the delimiter don't match, the bool unbalanced will be YES;