valid Parenthese using stack in c

Question

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!

Vlad from Moscow · Accepted Answer · 2024-02-14 05:26:44Z

2

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.

edited Feb 14, 2024 at 5:26

answered Feb 13, 2024 at 19:12

Vlad from Moscow

313k27 gold badges204 silver badges358 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Chris Over a year ago

The dangers of typdefing away the * in pointers.

Chris Over a year ago

It isn't being tested for an empty string, because the character at index 1 is being tested. That test seems wholly unnecessary. Eliminate the UB and the loop handles the situation correctly.

Collectives™ on Stack Overflow

valid Parenthese using stack in c

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related