[leetcode simple] 20. Valid brackets stack

20. Valid parenthesis

solution ： Stack

As soon as you see the problem of bracket matching , The first idea is to use stack to realize , Scan the string , If the current character is ’ ( ’ ’ [ ’ ’ { ', Then push it onto the stack , Otherwise pop up the top of the stack , Judge whether the character at the top of the stack matches the current character , If it matches, continue to judge the next character , If there is no match, return false. Attention should be paid to , There are nine endings of the first character ’ ) ’ ’ ] ’ ’ } ’ The situation of , This situation obviously does not match , So before popping the character at the top of the stack, you need to judge whether the current stack is empty , If it is empty , Obviously, the string is invalid , return false

Besides , There are still things like “[[()” The situation of , Therefore, after scanning the string, you need to judge whether the current stack is empty , Empty indicates that the brackets match successfully , The string is valid , return true; Non empty means that the string is invalid , return false

The code is as follows ：

class Solution {
    
public:
    bool isValid(string s) {
    
        stack<char> sta;
        for(int i=0;i<s.length();i++){
    
            if(s[i]=='(' || s[i]=='[' || s[i]=='{'){
    
                sta.push(s[i]);
            }
            else{
    
                if(sta.empty()) return false;
                char temp=sta.top();
                sta.pop();
                if((temp=='('&&s[i]==')') || (temp=='['&&s[i]==']') || (temp=='{'&&s[i]=='}')){
    
                    continue;
                }else{
    
                    return false;
                }
            }
        }
        if(sta.empty()) return true;
        else return false;
    }
};

Use in the problem solution given by Li Kou map Make the process of judging whether it matches more concise , The code is as follows for reference ：

class Solution {
    
public:
    bool isValid(string s) {
    
        int n = s.size();
        if (n % 2 == 1) {
    
            return false;
        }

        unordered_map<char, char> pairs = {
    
            {
    ')', '('},
            {
    ']', '['},
            {
    '}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
    
            if (pairs.count(ch)) {
    
                if (stk.empty() || stk.top() != pairs[ch]) {
    
                    return false;
                }
                stk.pop();
            }
            else {
    
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};