LeetCode-20. 有效的括号（栈模拟）

绝地灬酷狼 2022-05-26 10:51 141阅读 0赞

### 20. 有效的括号 ###

[题目描述][Link 1]

--------------------

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

有效字符串需满足：

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

注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
    输出: true

示例 2:

输入: "()[]{}"
    输出: true

示例 3:

输入: "(]"
    输出: false

示例 4:

输入: "([)]"
    输出: false

示例 5:

输入: "{[]}"
    输出: true

*  [括号生成][Link 2] [最长有效括号][Link 3] [删除无效的括号][Link 4]

--------------------

#include<bits/stdc++.h>
    using namespace std;
    /********************提交代码********************/
    bool isValid(char* s)
    {
        char sta[10000];//注意开大一点
        int i,cnt=0,len=strlen(s);
        if(len%2) return false;//奇数
        for(i=0;i<len;++i)
        {
            if(s[i]=='('||s[i]=='['||s[i]=='{')//左括号
               sta[cnt++]=s[i];//入栈
            else if(s[i]==')'||s[i]==']'||s[i]=='}')//右括号
            {
                if(cnt==0) return false;//防止下标越界
                if((sta[cnt-1]=='('&&s[i]==')')||(sta[cnt-1]=='['&&s[i]==']')||(sta[cnt-1]=='{'&&s[i]=='}'))
                    --cnt;//匹配出栈
                else return false;//不匹配
            }
        }
        if(cnt==0) return true;
        return false;
    }
    /***************************************************/
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("F:/cb/read.txt","r",stdin);
        //freopen("F:/cb/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        char s[2000];
        while(cin>>s)
        {
            cout<<isValid(s)<<endl;
        }
        return 0;
    }

遍历字符串，遇到左括号入栈，遇到右括号和栈顶元素比较是否成对匹配：

若匹配则出栈；反之则整个字符串不满足匹配。

只有遍历到最后栈为空则整个字符串满足匹配。

**测试用例：**

((
    [
    (}
    ({
    ()
    ()[]{}
    (]
    ([)]
    {[]}

[Link 1]: https://leetcode-cn.com/problems/valid-parentheses/description/
[Link 2]: https://leetcode-cn.com/problems/generate-parentheses
[Link 3]: https://leetcode-cn.com/problems/longest-valid-parentheses
[Link 4]: https://leetcode-cn.com/problems/remove-invalid-parentheses