I am trying to write a program to check if a string of brackets is balanced or not. If balanced, I do not want any output. But if it is not balanced then I want it to return the brackets needed to balance it. For example '([])' should be balanced and '({}' should be unbalanced and should return "open: )". The code seems to work fine until I have two or more brackets left open. So if I input '({' my code works but when I add a few more characters like '([])([' it fails because of a stack overflow. I do not understand what the error could be or how to fix it.

Here is my code:

void push(struct sNode** top_ref, int new_data){
    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));

    if (new_node == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }

    new_node->data = new_data;
    new_node->next = (*top_ref);
    (*top_ref) = new_node;
}
int pop(struct sNode** top_ref){
    char res;
    struct sNode* top;
    
    if (*top_ref == NULL) {
        printf("Stack overflow \n");
        getchar();
        exit(0);
    }else {
        top = *top_ref;
        res = top->data;
        *top_ref = top->next;
        free(top);
        return res;
    }
}

// Returns 1 if character1 and character2 are matching left and right Brackets
bool isMatchingPair(char character1, char character2)
{
    if (character1 == '(' && character2 == ')')
        return 1;
    else if (character1 == '{' && character2 == '}')
        return 1;
    else if (character1 == '[' && character2 == ']')
        return 1;
    else
        return 0;
}

// Return 1 if expression is balanced
int areBracketsBalanced(char exp[]){
    int i = 0;
    struct sNode* stack = NULL;

    while (exp[i]){
        if (exp[i] == '{' || exp[i] == '(' || exp[i] == '[')
            push(&stack, exp[i]);

        if (exp[i] == '}' || exp[i] == ')' || exp[i] == ']') {

            if (stack == NULL){
                printf("%d:%c\n",i,exp[i]);
                return 0;
            }else if (!isMatchingPair(pop(&stack), exp[i])){
                printf("%d:%c\n",i,exp[i]);
                return 0;
            }
        }
        i  ;
    }

    if (stack != NULL){
        printf("open: ");
        while(stack!=NULL){
            if(pop(&stack)=='('){
                printf("%c",')');
            }else if(pop(&stack)=='['){
                printf("%c",']');
            }else if(pop(&stack)=='{'){
                printf("%c",'}');
            }
        }
        printf("\n");
        return 0;
    }
    
    return 0;
}

int main(int argc, char* argv[])
{
    char *exp = (char *)malloc(strlen(argv[1]) * sizeof(char));
    for(int i = 0; i<strlen(argv[1]); i  ){
        exp[i] = argv[1][i];
    }
    
    //char exp[] = "([])([";
    areBracketsBalanced(exp);
    
    return 0;
}

CodePudding user response：

As it has been pointed out in comments, your exp in main is wrong as it end up without a zero termination. Actually there is no need for it... just pass argv[1] to the function.

int main(int argc, char* argv[])
{
    if (argc > 1)
    {
        areBracketsBalanced(argv[1]);
    }
    else
    {
        puts("Missing argument");
    }
    
    return 0;
}

Besides that, you have a problem here:

    while(stack!=NULL){
        if(pop(&stack)=='('){
            printf("%c",')');
        }else if(pop(&stack)=='['){
            printf("%c",']');
        }else if(pop(&stack)=='{'){
            printf("%c",'}');
        }
    }

Each of these pop(&stack) will change stack and maybe cause it to be NULL. At worst you do 3 pop-operations before checking for NULL. That's not good.

Change the code so that you have one pop operation before the if statements. Save the result in a local variable that you use for the if statement. Like:

    while(stack!=NULL){
        int value = pop(&stack);
        if(value == '('){
            printf("%c",')');
        }else if(value == '['){
            printf("%c",']');
        }else if(value == '{'){
            printf("%c",'}');
        }
    }