Using C to determine if a string contains any imbalanced brackets

Question

I am completing some course work and stuck at this final hurdle! I need to identify if a string contains any bracket imbalances, but I can only use C. I have read that this is a very popular interview question used by some organisations. I have a solution, but I know it is not correct, the answer requires using the stack to push and pop variables. Does anyone have any advice? I appologies for my naivety.

Here is my solution:

int balanced(char line [LINE_LENGTH])
{
    int bracketCount = 0;
        
    for (int counter = 0 ; counter < strlen(line) ; counter++)
    {
        if (line[counter] == '[' || line[counter] == ']' || line[counter] == '(' || line[counter] == ')' || line[counter] == '{' || line[counter] == '}')
        { 
            bracketCount++;
        }
    }
    return bracketCount;
}

Answer 1

Your solution is incorrect: you increment bracketCount for both types of brackets, so the function just returns the total number of brackets, it does not check for proper balancing.

You could improve your approach by incrementing bracketCount for opening brackets and decrementing it on closing brackets: this would detect missing brackets but not imbalance nor mismatched brackets.

You could use different counters for {, [ and ( and keep track of bracket types separately, but you still would not detect nesting errors as in "([)]"

To implement a proper checker, you need to store the opening brackets in a stack where you can check for each closing bracket that it matches the currently open one.

Here is a simple implementation using an array of char as a stack:

int balanced(const char *line) {
    char brackets[LINE_LENGTH];
    char *bp = brackets + LINE_LENGTH;

    *--bp = '\0';
    for (size_t i = 0; line[i] != '\0'; i++) {
        char cc;
        switch (line[i]) {
          case '[':
            cc = ']';
            break;
          case '(':
            cc = ')';
            break;
          case '{':
            cc = '}';
            break;
          case ']':
          case ')':
          case '}':
            if (*bp == '\0') {
                /* stack is empty: unexpected closing bracket */
                printf("offset %zu: no opening bracket for '%c'\n",
                       i, line[i]);
                return 0;
            }
            if (*bp != line[i]) {
                /* nesting error: closing bracket does not match the expected type */
                printf("offset %zu: bad bracket type for '%c', expected '%c'\n",
                       i, line[i], *bp);
                return 0;
            }
            bp++;
            continue;
          default:
            continue;
        }
        if (bp == brackets) {
            /* stack overflow */
            printf("too many open brackets\n");
            return -1;
        }
        *--bp = cc;  /* push the expected closing bracket */
    }
    if (*bp) {
        /* some opening brackets have not been closed */
        printf("missing brackets: %s\n", bp);
        return 0;
    }
    return 1;    
}

Here is a much simpler recursive approach:

#include <stdio.h>

const char *check_brace(const char str[], int endc) {
    while (str) {
        int c = *str++;
        switch (c) {
          case '(': str = check_brace(str, ')'); break;
          case '[': str = check_brace(str, ']'); break;
          case '{': str = check_brace(str, '}'); break;
          case ')':
          case ']':
          case '}':
          case '\0': return (c == endc) ? str : NULL;
        }
    }
    return NULL;
}

int balanced(const char *line) {
    return check_brace(line, '\0') != NULL;
}

int main() {
    char str[80];
    if (fgets(str, sizeof str, stdin)) {
        printf("%d\n", balanced(str, '\0') != NULL);
    }
    return 0;
}

Answer 2

Here is one approach to find out if a string of brackets is balanced or not.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

static inline char match_bracket (const char ch) {
    switch (ch) {
    case '{' : return '}';
    case '}' : return '{';
    case '(' : return ')';
    case ')' : return '(';
    case '[' : return ']';
    case ']' : return '[';
    default:
        fprintf (stderr, "\nERROR: %c is not supported\n", ch);
        exit (1);
    }
}


/**
 * Opening Brackets : [ { (
 * Closing Brackets : ] } )
 * Balanced : No overlapping of brackets & every open has a matching close
 * Example :    {[({})]} - balanced
 *              {[(}{)]} - unbalanced
 * Function returns on first detection of any error
 */
int check_bracket_balance (const char* brkts, const int slen)
{
    if (!brkts || ! (*brkts) || slen < 0) {
        printf ("\tInvalid arguments\n");
        return -1;
    }
    const char* open_brackets = "([{";
    const char* close_brackets = ")]}";

    char bStack [slen + 1]; // array stack emulation
    int sTop = -1;
    for (int bi = 0; bi < slen; ++bi) {
        if (strchr (open_brackets, brkts[bi]))
            bStack[++sTop] = brkts[bi];                 // push on to stack
        else if (strchr (close_brackets, brkts[bi])) {  // a closing bracket
            if (sTop < 0) {  // empty Stack
                printf ("\tExpected %c before %c at %d\n", match_bracket (brkts[bi]), brkts[bi], bi + 1);
                return 1;
            }
            if (bStack[sTop] == match_bracket (brkts[bi])) // is stack-top a matching bracket
                --sTop;     // pop matching bracket from stack
            else {
                printf ("\tExpected %c before %c at %d\n", match_bracket (bStack[sTop]), brkts[bi], bi + 1);
                return 2;
            }
        } else {
            printf ("\tInvalid char %c at %d\n", brkts[bi], bi + 1);
            return -2;  // use enums like eInvBracketChar for easier code-read
        }
    }
    if (sTop >= 0) {
        printf ("\tThere are %d unmatched opening brackets\n", sTop + 1);
        return 3;
    }
    return 0; // balanced
}


#define MAX_STRINGS 8
int main ()
{
    char* strings[MAX_STRINGS] = {"{([])}",
        "{}()[]",
        "{})([]",
        "{([)]}",
        "{{(([[",
        "",
        "{}<>{}",   // assuming <> are invalid
        "Testing"
    };
    printf ("\n");
    for (int si =0; si < MAX_STRINGS; ++si) {
        printf ("\n%s\n", strings[si]);
        int error = check_bracket_balance (strings[si], strlen (strings[si]));
        if (error)
            printf ("\tERROR[%d]: Brackets not Balanced\n", error);
        else
            printf ("\tBrackets Balanced\n");
    }

    printf ("\n");
    return 0;
}