How can I resolve segmentation fault in my code.?

Question

I am trying to solve the problem of brackets matching i.e. given a sequence of opening and closing parenthesis exp, consisting of ( or ), square brackets [ or ] or curly braces } or {, I need to tell if the given sequence is balanced or not.

Sample Input1:
exp = "[]{}()"

Sample Output1:
Match Successfull....!


----------


Sample Input2:
exp = "[]{(]}()"

Sample Output1:
Match not Successfull....!

PS: empty string is considered a balanced string.
Below is the code written in C where I tried to implement a stack using struct. I implemented the all the necessary function of a stack i.e., pop(), push(), isFull() etc.
However, I am getting segmentation fault. Please help me rectify the error.

#include <stdio.h>
#include <stdlib.h>
struct stack {
    int size;
    int top;
    char *arr;
};

int isEmpty(struct stack *ptr) {
    if (ptr->top == -1)
    {
        return 1;
    }
    return 0;
}

int isFull(struct stack *ptr) {
    if (ptr->top == ptr->size - 1)
    {
        return 1;
    }
    return 0;
}

int push(struct stack *ptr, char val) {
    if (isFull(ptr))
    {
        return 1;
    }
    else
    {
        ptr->top++;
        ptr->arr[ptr->top] = val;
    }
}

int pop(struct stack *ptr) {
    char val;
    if (isEmpty(ptr))
    {
        return 1;
    }
    else
    {
        ptr->top--;
        val = ptr->arr[ptr->top];
        return val;
    }
}

int match(char a, char b) {
    if (a == '{' && b == '}' || a == '(' && b == ')' || a == '[' && b == ']')
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int parMatch(char *exp) {
    struct stack *s = malloc(sizeof(struct stack));
    s->arr = (char *)malloc(s->size * sizeof(char));
    s->size = 100;
    s->top = -1;
    char char_pop;
    for (int i = 0; exp[i] = '\0'; i++)
    {
        if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
        {
            push(s, exp[i]);
        }
        else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
        {
            return 0;
        }
        char_pop = pop(s);
        if (!match(char_pop, exp[i]))
        {
            return 0;
        }
    }
    if (isEmpty(s))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main() {
    char *exp = "[]{}()";
    if (parMatch(exp))
    {
        printf("Match Successfull....!");
    }
    else
    {
        printf("Match not Successfull....!");
    }
    return 0;
}

risingStark · Answer 1 · 2021-03-30T17:45:56.567

The reason why your code results in an error is due to the statement exp[i] = '\0'; in your condition of for loop. This is logically incorrect (explained below) and you just cannot modify strings declared using char*.

Why is that you ask? Read Why do I get a segmentation fault when writing to a “char *s” initialized with a string literal, but not “char s[]”?

You had other several errors as well within your code:

This is not how you assign strings in c, char *exp = "[]{}()";. Although it does work but it generates a warning and is not recommended. Read Assigning strings to arrays of characters.
You have not initialized s->size but you are using it in malloc() in this line s->arr = (char *)malloc(s->size * sizeof(char));.
You declared the return-type of push() function as int but did not return anything after the else condition. This is a potential bug in future. It also results in warnings.
The implementation of your pop() function has logical as well as syntactical flaws. The return-type of pop() function is int but you return char type. Also, you first decrement ptr->top and then return the character at the new ptr->top location i.e, you end up returning the character which is below your current top.
This is not exp[i] = '\0' how you check the terminating condition of for loop for ending char* string in c. You should instead write exp[i] != '\0'.
You return 0; as soon as you encounter ) or } or ]. You should instead check whether you can pop a corresponding opening brace from the stack, if yes then check for further characters else return 0;

Below is the code with all the above-mentioned errors fixed.

#include <stdio.h>
#include <stdlib.h>
struct stack {
    int size;
    int top;
    char *arr;
};

int isEmpty(struct stack *ptr) {
    if (ptr->top == -1)
    {
        return 1;
    }
    return 0;
}

int isFull(struct stack *ptr) {
    if (ptr->top == ptr->size - 1)
    {
        return 1;
    }
    return 0;
}

int push(struct stack *ptr, char val) {
    if (isFull(ptr))
    {
        return 1;
    }
    else
    {
        ptr->top++;
        ptr->arr[ptr->top] = val;
    }
    return 0;
}

char pop(struct stack *ptr) {
    char val;
    if (isEmpty(ptr))
    {
        return '\0';
    }
    else
    {
        val = ptr->arr[ptr->top];
        ptr->top--;
        return val;
    }
}

int match(char a, char b) {
    if ((a == '{' && b == '}') || (a == '(' && b == ')') || (a == '[' && b == ']'))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int parMatch(char exp[]) {
    struct stack *s = malloc(sizeof(struct stack));
    s->size = 100;
    s->arr = (char *)malloc(s->size * sizeof(char));

    s->top = -1;
    char char_pop;
    for (int i = 0; exp[i] != '\0'; i++)
    {
        if (exp[i] == '(' || exp[i] == '{' || exp[i] == '[')
        {
            push(s, exp[i]);
        }
        else if (exp[i] == ')' || exp[i] == '}' || exp[i] == ']')
        {   // You have one closing brace but your stack is empty, then return 0
            if (isEmpty(s))
            {
                return 0;
            }
            else
            {   // If you reach here then it ensures that stack is not empty.
                char_pop = pop(s);
                if (!match(char_pop, exp[i]))
                {
                    return 0;
                }
            }
        }
    }
    if (isEmpty(s))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

int main() {
    char exp[100] = "{}}[](";
    if (parMatch(exp))
    {
        printf("Match Successfull....!");
    }
    else
    {
        printf("Match not Successfull....!");
    }
    return 0;
}

How can I resolve segmentation fault in my code.?

1 Answers1