Bracket Balancing checker always gives incorrect output

Question

I am trying to create a function that uses linked list to check whether an expression is balanced (no. of opening brackets = no. of closing brackets) or unbalanced. But my function always gives "unbalanced" as the output.

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

struct LL
{
    char data;
    struct LL *next;
};

int isEmpty(struct LL *top)
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int isFull(struct LL *top)
{
    struct LL *n = malloc(sizeof(struct LL *));
    if (n == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

struct LL *push(struct LL *top, char x)
{
    if (isFull(top))
    { 
        printf("Stack Overflow\n");
    }
    else
    {
        struct LL *n = malloc(sizeof(struct LL));
        n->data = x;
        n->next = top;
        top = n;
    }
    return top;
 }

 struct LL *pop(struct LL *top)
 {
    if (isEmpty(top))
    {
        printf("Stack Underflow\n");
    }
    else
    {
        struct LL *n = malloc(sizeof(struct LL));
        n = top;
        top = top->next;
        free(n);
    }
    return top;
 }

 int BracketBalancing (char *exp)
 {
    struct LL *top = malloc(sizeof(struct LL));
    top->next = NULL;
    for (int i = 0; exp[i] != '\0'; i++)
    {
        if (exp[i] == '(')
        {
            push(top, exp[i]);
        }
        else if (exp[i] == ')')
        {
            if (isEmpty(top))
            {
                return 0;
            }
            pop(top);
        }
    }
    if (isEmpty(top))
    {
        return 1;
    }
    else
    {
        return 0;
    }
  }

Main code:

int main(int argc, char const *argv[])
{
    int n;
    char *expression = (char *)malloc(sizeof(char));
    printf("Enter the length of the expression for Bracket Balancing\n");
    scanf("%d", &n);
    printf("Enter the expression for Bracket Balancing\n");
    for (int i = 0; i < n; i++)
    {
        scanf("%c ", &expression[i]);
    }
    getchar();
    if (BracketBalancing(expression))
    {
        printf("The expression is balanced\n");
    }
    else if (!BracketBalancing(expression))
    {
        printf("This expression is unbalanced\n");
    }
    return 0;
}

For Example:

Input:

Enter the length of the expression for Bracket Balancing 
4
Enter the expression for Bracket Balancing
1+()

Output:

This expression is unbalanced

In the above example, no. of opening brackets = no. of closing brackets (it is a balanced expression) but still the output generated is "This expression is unbalanced". Kindly correct my code.

Answer 1

This is how you initialize your list:

struct LL *top = malloc(sizeof(struct LL));
top->next = NULL;

And this is isEmpty():

int isEmpty(struct LL *top)
{
    if (top == NULL)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

But: top starts with a value != NULL, so isEmtpy() will not return 1, although our list should be empty in the beginning.

Your implementation of push() should work fine when you pass NULL, so you can just initialize struct LL *top = NULL; instead of creating the first element rightaway.

there other bugs in your code, e.g.:

• in pop() you do

    struct LL *n = malloc(sizeof(struct LL));
    n = top;
  

thus, the result of malloc() is directly overwritten() in the next line

• in isFull() you produce a memory leak as you call malloc() and never use or free() the buffer returned. That function doesn't make sense anyway, just check the result of malloc()s where your really want to use the buffer returned.

** Edit **

What I haven't seen before, you also never use the return value of push() and pop() so the new top determined by these function is lost. Replace push(top, ...); by top = push(top,...); and pop(top); by top = pop(top);

Answer 2

Yes, but...

First of all, as std::array is just a tiny wrapper around a plain array, both simple_2D_array and std_2D_array will have exactly the same memory layout.

Next, that memory layout would be the same as the one of a 1D array of size 20 but there will be a strong difference between the 1D array and any of the 2D ones

• for the 1D array, the declared size of the array is the total size of the object: it is legal to use for example arr[6].
• for the 2D objects, the declared size of any integer array is only 4. On a strict language point of view, as pointer arithmetics is only define inside an array it is illegal (thus Undefined Behaviour) to browse the whole array as if it was a 1D array of size 20.

Of course, any common compiler will accept that and produce the expected output because it used to be a common idiom and rejecting it would break a lot of legacy code. Yet it is not valid C++ (I have no reference at the moment, but it has been discussed on SO...)