I was solving the problem 20. Valid Parentheses in Leetcode using c and when they check this input s ="{[]}" the code returns false instead of true but I don't see any problem with the code:
typedef struct node{
char data;
struct node *next;
}node;
typedef node* stack;
int isEmpty(stack p){
return p ==NULL;
}
void push(stack *p,char x){
node *new = (node*)malloc(sizeof(node));
new->data = x;
new->next = *p;
*p = new;
}
void pop(stack *p){
node *t=*p;
*p=(*p)->next;
free(t);
}
bool isValid(char* s) {
stack p;
if(s[1] == '\0') return false;
for(int i=0;s[i]!= '\0';++i){
if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
push(&p,s[i]);
}
else{
if((s[i]==')' && p->data == '(')||(s[i]==']' && p->data == '[') || (s[i]=='}' && p->data == '{'))
pop(&p);
else return false;
}
}
return isEmpty(p);
}
I really don't see any problem with the code, if you have any suggestion please help!
The function isValid
has undefined behavior (it is isInValid
:)).
For starters the pointer p
is not initialized and has an indeterminate value
stack p;
Secondly, consider for example string "]]"
. For such a string the control will be passed to the if statement
if((s[i]==')' && p->data == '(')||(s[i]==']' && p->data == '[') || (s[i]=='}' && p->data == '{'))
So even if the pointer p
will be initialized as a null pointer expressions like that p->data
are trying to access memory using a null pointer. You need to check at first whether the stack is empty.
Also such a typedef declaration
typedef node* stack;
Where the pointer type is hidden will only confuse readers of the code.
Pay attention to that in the page your provided a reference to the function is declared like
bool isValid( const char* s)
^^^^^
because the passed string is not being changed within the function.