CODEWITHSUNDEEP
cdata-structureslinked-liststacksingly-linked-list
roger_hai
roger_hai

Reputation: 13

valid Parenthese using stack in c

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!

Upvotes: 1

Views: 70

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 311078

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.

Upvotes: 2

Related Questions