Checking that brackets match (an application of stacks)

This lesson covers checking bracket matching with a stack in Objective-C, with the aim of seeing a practical application of the data structure.

With a stack (last in, first out) you push each opening bracket such as ( or [, and each time a closing bracket arrives you check it against the top of the stack.

The sample code holds the opening bracket for each closing bracket in an NSDictionary called pairs, pushes onto an NSMutableArray when an opening bracket arrives, and checks against the top of the stack when a closing one does. If the stack is empty at the end, the brackets balance.

A common early stumble is handling several kinds of bracket at once (round, square, and curly mixed together). Counting openings and closings is not enough — you have to check they nest in the right order.

Similar thinking sits behind editor auto-completion and syntax checking.

📖 Reference code

BOOL isBalanced(NSString *str) {
    NSMutableArray *stack = [NSMutableArray array];
    NSDictionary *pairs = @{@")": @"(", @"]": @"[", @"}": @"{"};
    for (NSUInteger i = 0; i < str.length; i++) {
        NSString *ch = [str substringWithRange:NSMakeRange(i, 1)];
        if ([ch isEqualToString:@"("] || [ch isEqualToString:@"["] || [ch isEqualToString:@"{"]) {
            [stack addObject:ch];
        } else if ([ch isEqualToString:@")"] || [ch isEqualToString:@"]"] || [ch isEqualToString:@"}"]) {
            if (stack.count == 0 || ![stack.lastObject isEqualToString:pairs[ch]]) {
                return NO;
            }
            [stack removeLastObject];
        }
    }
    return stack.count == 0;
}

NSLog(@"%d", isBalanced(@"(a[b]{c})"));
NSLog(@"%d", isBalanced(@"(a[b)]"));

✍️ Your code

Type your code, then press "Run"

🧪 This site can't compile or run Objective-C directly, so it checks on the spot whether what you typed matches the reference code (scoring happens entirely in your browser — nothing is sent anywhere).