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