20. Valid Parentheses 验证括号

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.

Difficulty: Easy

这道题让我们验证字符串是否是可用的括号,这个字符串只有括号.需要用到栈,当遇到左括号的时候压入到栈里,遇到右括号的时候需要检查栈顶元素是否为对应的左括号,如果不是对应的就返回false.

class Solution {
public:
    bool isValid(string s) {
        stack<char> parentheses;
        for (int i = 0; i<s.size();i++){
            if (s[i]=='('||s[i]=='['||s[i]=='{')
                parentheses.push(s[i]);
            else {
                if (parentheses.empty()) return false;
                if (s[i]==')' && parentheses.top()!='(') return false;
                if (s[i]==']' && parentheses.top()!='[') return false;
                if (s[i]=='}' && parentheses.top()!='{') return false;
                parentheses.pop();
            }
        }
        return parentheses.empty();
    }
};
 
comments powered by Disqus