有效的括号(leetcode简单)

今天更新一个栈的经典问题

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

思路：这个题其实就是用栈的特性来解决，利用先进后出

1.首先在接口函数前面加一个栈的数据结构，将其接口函数实现。

栈的数据结构可以看这个：

数据结构初阶之栈_何以过春秋的博客-CSDN博客

2.再创立一个栈，初始化和销毁先写好。

3.接下来讲大体思路：先判断括号入栈出栈的情况，如果是左括号，就入栈，如果是右括号，那么已经入了栈的左括号就出栈，并且要与没有入栈的右括号进行比对，相符就true，不相符就false。至此代码是这样的

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((top=='['&&*s==']')||
            (top=='('&&*s==')')||
            (top=='{'&&*s=='}'))
            {
                ++s;
            }
            else{
                return false;
            }
        }
    }
  
    StackDestroy(&st);
    return true;
}

4.细节：首先入栈时，需要考虑的有：只有左括号怎么办？没有左括号怎么办？

这时就需要改动代码，具体代码如下

bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            //这个判断语句就是为了对付只有右括号的情况
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            STDataType top=StackTop(&st);
            StackPop(&st);
            if((top=='['&&*s==']')||
            (top=='('&&*s==')')||
            (top=='{'&&*s=='}'))
            {
                ++s;
            }
            else{
                StackDestroy(&st);
                return false;
            }
        }
    }
    //这个bool函数就是为了对付只有左括号的情况
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}