leetcode Valid Parentheses

待我称王封你为后i 2022-08-05 02:45 114阅读 0赞

# 题目 #

Given a string containing just the characters ‘(‘, ‘)’, ‘\{‘, ‘\}’, ‘\[’ and ‘\]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()\[\]\{\}” are all valid but “(\]” and “(\[)\]” are not.  
题目来源：[https://leetcode.com/problems/valid-parentheses/][https_leetcode.com_problems_valid-parentheses]

# 分析 #

借助一个栈，如果遇到的是左括号，则进栈；如果遇到的是右括号，则与栈顶元素比较。与栈顶元素不match，则return false。扫描完字符串后，栈应该为空。

# 代码 #

class Solution {
    private:
        stack<char> my_stack;
    public:
        bool isMatch(char a, char b){
       //a和b是否是一对括号
            if(a == '(' && b == ')')
                return true;
            else if(a == '[' && b == ']')
                return true;
            else if(a == '{' && b == '}')
                return true;
            else
                return false;
        }
        bool isValid(string s) {
            int len = s.length();
            if(len <= 0)
                return true;
            for(int i = 0; i < len ; i++){
                char ch = s.at(i);
                if(ch == '(' || ch == '{' || ch == '[')//左括号入栈
                    this->my_stack.push(ch);
                else{
       //右括号与栈顶元素匹配
                    if(this->my_stack.empty())
                        return false;
                    if(!isMatch(this->my_stack.top(), ch))
                        return false;
                    else
                        this->my_stack.pop();
                }
            }
            return my_stack.empty();//扫描结束后栈应该为空，非空则返回false
        }
    };

[https_leetcode.com_problems_valid-parentheses]: https://leetcode.com/problems/valid-parentheses/