有效的括号

一、问题描述

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

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
  题目链接：有效的括号。

二、题目要求

样例 1

输入： s = "()"
输出： true

样例 2

输入： s = "([)]"
输出： false

考察

1. 字符串、栈、哈希
2. 建议用时20~35min

三、问题分析

这一题需要用到栈的相关知识点，如果没了解过栈的可以看一下这一篇文章，栈其实就是先进后出的存储结构。

对于这一题的有效括号，我们可以先定义哈希表m特定化不同的6个括号。

map<char,int>m={{'(',1},{'{',2},{'[',3},
                {')',4},{'}',5},{']',6}};

如上面的动态图所示：

只要前3个括号出现，那么就存储到栈里面去，后三个出现那么肯定要进行括号匹配消除的。消除的话，如果和栈第一个括号匹配成功，那么就弹出栈顶。

如果匹配不成功，后三个括号入栈，那就完了，因为无论你后面有再多的括号，它也匹配不了，直接退出就行。

四、编码实现

class Solution {
public:
    bool isValid(string s) {
        int i,n=s.size();//初始化数据
        bool flag=true;//一开始判断匹配成功
        stack<char>k;
        map<char,int>m={{'(',1},{'{',2},{'[',3},//哈希存储括号
                        {')',4},{'}',5},{']',6}};
        for(i=0;i<n;i++)//循环判断
        {
            if(m[s[i]]<=3)//前三个直接存储
                k.push(s[i]);
           
            else if(!k.empty()&&m[s[i]]-3==m[k.top()])//后三个与栈顶匹配消除
                    k.pop();
            else//匹配失败
            {
                flag=false;
                break;
            }
        }
        if(!k.empty())//如果栈不为空，那也匹配失败
            flag=false;
        return flag;//返回结果
        
    }
};