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;
}

CodePudding user response：

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

#include <stdio.h>
#include <string.h>
#define log(...) fprintf(stderr, __VA_ARGS__)

static inline int is_opening_bracket (int ich) {
    switch (ich) {
    case '{':    case '(':    case '[':
        return 1;
    default:
        return 0;
    }
}

static inline int is_closing_bracket (int ich) {
    switch (ich) {
    case '}':    case ')':    case ']':
        return 1;
    default:
        return 0;
    }
}

/**
 * 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) return -1;

    char matchBkt[256] = {0}; // makes matching easier
    matchBkt[ (unsigned) '}'] = '{';
    matchBkt[ (unsigned) ']'] = '[';
    matchBkt[ (unsigned) ')'] = '(';

    char bStack [slen   1]; // array stack emulation
    int sTop = -1;
    for (int bi = 0; bi < slen;   bi) {
        int ich = (unsigned) brkts[bi];
        if (is_opening_bracket(ich))
            bStack[  sTop] = ich;       // push on to stack
        else if (is_closing_bracket(ich)) {           // a closing bracket
            if (sTop < 0)               // Stack was empty
                return 1;               // closing bracket before an open
            if (bStack[sTop] == matchBkt[ich])  // is stack top a matching bracket
                --sTop;                 // pop matching bracket from stack
            else
                return 2; // bracket mismatch
        } else // invalid character
            return -2;  // define enums like eInvBracketChar for easier code-read
    }
    if (sTop >= 0) return 3;  // brackets incomplete = mismatch

    return 0; // balanced
}


#define MAX_STRINGS 7
int main ()
{
    log("\n");
    char* strings[MAX_STRINGS] = {"{([])}",
        "{}()[]",
        "{})([]",
        "{([)]}",
        "{{(([[",
        "",
        "{}<>{}"
    };
    for (int si =0; si < MAX_STRINGS;   si) {
        log ("\n%s", strings[si]);
        int error = check_bracket_balance (strings[si], strlen (strings[si]));
        if (error) // handle negative / positive errors separately?
            log ("\tERROR[%d]: Brackets not Balanced", error);
        else
            log ("\tBrackets Balanced");
    }

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

CodePudding user response：

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;    
}