Follow

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use
Contact

Problems Building a stack using dynamic memory (C)

I am trying to learn data structures, therefore I made an exercise which we read a string from the user, and then we evaluate the string, to check if the parentheses are well formatted, such as input: ((), output: no, they are not well formatted. Although when I try to run my code, not only does it gives the wrong output, put it shows me the error: free(): invalid pointer. I ran valgrind with my code and it shows me: Invalid free() ... Address.. is 12 bytes before a block of size 16 alloc´d I will post a snippet of my code below.
I am a beginner so any help would be appreciated, I am all ears for criticism too.

typedef struct {
    int *v;    
    int cap;    
    int sz;
} stack;

stack *build() {
    stack *new = (stack *)malloc(sizeof(stack));
    new->v = (int *)malloc(sizeof(int) * 4);
    new->cap = 4;
    new->sz = 0;
    return new;
}

int is_empty(stack *s) {
    return s->sz == 0;
}

int push(stack *s, int e) {
    int success = 1;

    if (s->sz == s->cap) {
        int *tmp = (int *)realloc(s->v, (s->cap + 1) * sizeof( int));
        if ((success = tmp != NULL)) {
            s->v = tmp;
            ++s->cap;
        }
    }

    if (success) {
        s->v[s->sz++] = e;
    }

    return success;
}

int top(stack *s) {
    return *(s->v);
}

int pop(stack *s) {
    int value;

    if (is_empty(s))
        return -1;

    value = *(s->v);
    s->v--;
    s->sz--;
    return value;   
}

void destroy(stack *s) {
    s->v -= s->sz + 1;
    free(s->v);
    free(s);
}

int match(char p1, char p2) {
    if (p1 == '(')
        return (p1 - p2) == '(' - ')';
    else if (p1 == '[')
        return (p1 - p2) == '[' - ']';
    else
        return (p1 - p2) == '{' - '}';
}

int main() {
    int c;
    stack *s = build();
    while ((c = getchar()) != EOF && c != '\n') {
        if (c == '(' || c == '[' || c == '{')
             push(s, c);
        else if (c == ')' || c == ']' || c == '}') {
            if (!match(pop(s), c)) {
                printf("no\n");
                destroy(s);
                return 0;
            }
        }
    }
    puts((is_empty(s)) ? "yes" : "no");
    destroy(s);
    return 0;
}

>Solution :

MEDevel.com: Open-source for Healthcare and Education

Collecting and validating open-source software for healthcare, education, enterprise, development, medical imaging, medical records, and digital pathology.

Visit Medevel

The problem is in pop() and destroy(): you modify s->v instead of updating s->sz. Pass a modified value of s->v to free causes undefined behavior, which valgrind catches.

Here is a modified version:

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

typedef struct {
    int *v;    
    int cap;    
    int sz;
} stack;

stack *build(void) {
    stack *new = (stack *)malloc(sizeof(*new));
    new->v = (int *)malloc(sizeof(int) * 4);
    new->cap = 4;
    new->sz = 0;
    return new;
}

int is_empty(stack *s) {
    return s->sz == 0;
}

int push(stack *s, int e) {
    if (s->sz == s->cap) {
        int *tmp = (int *)realloc(s->v, (s->cap + 1) * sizeof(int));
        if (tmp == NULL)
            return 0;
        s->v = tmp;
        s->cap += 1;
    }
    s->v[s->sz++] = e;
    return 1;
}

int top(stack *s) {
    if (is_empty(s))
        return -1;
    else
        return s->v[s->sz - 1];
}

int pop(stack *s) {
    if (is_empty(s))
        return -1;
    else
        return s->v[--s->sz];
}

void destroy(stack *s) {
    free(s->v);
    free(s);
}

int match(char p1, char p2) {
#define MATCH(a, b)  if (p1 == (a)) return p2 == (b)
    MATCH( '(' , ')' );
    MATCH( '[' , ']' );
    MATCH( '{' , '}' );
    return 0;
}

int main() {
    int res = 0;
    int c;
    stack *s = build();
    while ((c = getchar()) != EOF && c != '\n') {
        if (c == '(' || c == '[' || c == '{')
            push(s, c);
        else
        if (c == ')' || c == ']' || c == '}') {
            if (!match(pop(s), c)) {
                res = 1;
                break;
            }
        }
    }
    if (res == 0 && !is_empty(s))
        res = 2;
    puts(res == 0 ? "yes" : "no");
    destroy(s);
    return res;
}
Add a comment

Leave a Reply

Keep Up to Date with the Most Important News

By pressing the Subscribe button, you confirm that you have read and are agreeing to our Privacy Policy and Terms of Use

Discover more from Dev solutions

Subscribe now to keep reading and get access to the full archive.

Continue reading