E20.有效的括号

stack, https://leetcode.cn/problems/valid-parentheses/

思路：括号匹配问题简单的一个栈数据结构即可

cpp

class Solution {
public:
    bool isValid(string s) {
        //括号匹配问题 简单的一个栈数据结构即可
        stack<char> st;
        int n=s.size();
        int flag=0;
        for(int i=0;i<n;i++){
            //左进右出
            if(s[i]=='('||s[i]=='{'||s[i]=='['){
                st.push(s[i]);
            }else{
                if(st.empty()) return false;
                char tmp=st.top();
                if(s[i]==')'&&tmp!='('){
                    return false;
                }else if(s[i]==']'&&tmp!='['){
                    return false;
                }else if(s[i]=='}'&&tmp!='{'){
                    return false;
                }
                st.pop();

            }
        }
        if(st.empty())
            return true;
        else return false;
    }
};

思路：注意到括号的匹配与栈的后入先出是一样的，因此用栈的思路去解决，很顺利

cpp

class Solution 
{
public:
    bool isValid(string s) 
    {
        map<char, char> map = { {'(', ')'}, {'[', ']'}, {'{', '}'} };
        vector<char> stack;
        for (char c : s)
        {
            if (map.find(c) != map.end())//左括号，入栈
            {
                stack.push_back(c);
            }
            else
            {
                if (stack.empty() || c != map[stack.back()])//右括号，栈为空或者不匹配，返回false
                {
                    return false;
                }
                stack.pop_back();//右括号，匹配，出栈
            }
        }
        return stack.empty();
        
    }
};

E20.有效的括号 ​

E20.有效的括号