[20. valid brackets]

---

One 、 Title Description

Topic link

---

Two 、 How to do it

1. Left parenthesis , Push
2. Right bracket , Left bracket stack matching with right bracket

---

3、 ... and 、 Title code

typedef char STDataType;
typedef struct Stack
{
    
	STDataType* a;
	int top;
	int capacity;
}ST;

void StackInit(ST* ps)
{
    
    assert(ps);
    ps->a=NULL;
    ps->top=0;
    ps->capacity=0;
}
void StackDestroy(ST* ps)
{
    
    assert(ps);
    free(ps->a);
    ps->a=NULL;
    ps->top=ps->capacity=0;
}
void StackPush(ST* ps, STDataType x)
{
    
    assert(ps);
    if(ps->top==ps->capacity)
    {
    
        int newcapacity=(ps->capacity==0) ? 4 : 2*ps->capacity;
        STDataType*tmp=(STDataType*)realloc(ps->a,sizeof(STDataType)*newcapacity);
        if(tmp==NULL)
        {
    
            exit(-1);
        }
        else
        {
    
            ps->a=tmp;
            ps->capacity=newcapacity;
        }
    }
    ps->a[ps->top]=x;
    ps->top++;
}
bool StackEmpty(ST* ps)
{
    
    assert(ps);
    return ps->top==0;
}
void StackPop(ST* ps)
{
    
    assert(ps);
    assert(!StackEmpty(ps));
    ps->top--;
}
STDataType StackTop(ST* ps)
{
    
    assert(ps);
    return ps->a[ps->top-1];
}
int StackSize(ST* ps)
{
    
    assert(ps);
    return ps->top;
}


bool isValid(char * s){
    
    ST st;
    StackInit(&st);
    while(*s)
    {
    
        if(*s=='('||*s=='{'||*s=='[')
        {
    
            StackPush(&st,*s);
            s++;
        }
        else
        {
    
            // Encountered a closing bracket , But there is no data in the stack , explain 
            // There is no left parenthesis in front of it , Mismatch , return false s="]"
            if(StackEmpty(&st))
            {
    
                //[{()}]], In this case, although the stack is empty, data has been entered , Stack is to open up space 
                // So destroy , Prevent memory leaks 
                StackDestroy(&st);
                return false;
            }
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((*s == ')' && top != '(')
             ||(*s == '}' && top != '{')
             ||(*s == ']' && top != '['))
            {
    
                // If s="[[}]", All that's left of the stack is [
                // To prevent memory leaks, destroy the function 
                StackDestroy(&st);
                return false;
            }
            s++;
        }
        
    }
    // If the stack is not empty , It indicates that there are still left parentheses in the stack 
    // There is no match . Return is false s="["
    bool ret=StackEmpty(&st);
    StackDestroy(&st);

    return ret;
    
    
}

---

The above is the whole content of this article , If there are mistakes in the article or something you don't understand , Communicate more with meow bloggers . Learn from each other and make progress . If this article helps you , Can give meow bloggers a concern , Your support is my biggest motivation .