[LeetCode] 20. Valid Parentheses 验证括号

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

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"

Output: true

Example 2:

Input: "()[]{}"

Output: true

Example 3:

Input: "(]"

Output: false

Example 4:

Input: "([)]"

Output: false

Example 5:

Input: "{[]}"

Output: true

这道题让我们验证输入的字符串是否为括号字符串，包括大括号，中括号和小括号。这里需要用一个栈，开始遍历输入字符串，如果当前字符为左半边括号时，则将其压入栈中，如果遇到右半边括号时，若此时栈为空，则直接返回 false，如不为空，则取出栈顶元素，若为对应的左半边括号，则继续循环，反之返回 false，代码如下：

class Solution {

public:

    bool isValid(string s) {

        stack<char> parentheses;

        for (int i = ; 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();

    }

};