Type：medium

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

此题题意为判断一个字符串是否为合法字符，与代码符号规则相同，左括号后面必须有配对的右括号，且同一种类型的左右括号之间必须没有单独的其他括号。

此题解法为开一个left数组，用来储存所有出现过的左括号，当出现右括号时，将它与左括号数组的最后一个左括号进行匹配，看是否为同一种括号，若是，则在数组中删去这个括号，继续遍历；否则返回 false。当遍历到最后数组为空，且没有多余的右括号，则返回 true 。

class Solution {

public:

    bool isValid(string s) {

        string left;

        string right;

        int L=s.length();

        for(int i=0; i<L; i++){

            if(s[i] == '(' || s[i] == '{' || s[i] == '[') left.push_back(s[i]);

            else if(s[i] == ')' || s[i] == '}' || s[i] == ']') right.push_back(s[i]);

            if(i>0 && right.back() == ')') {

                if(left.back() == '('){

                    left.pop_back();

                    right.pop_back();

                }

                else return false;

            }

            else if(i>0 && right.back() == ']') {

                if(left.back() == '['){

                    left.pop_back();

                    right.pop_back();

                }

                else return false;

            }

            else if(i>0 && right.back() == '}') {

                if(left.back() == '{'){

                    left.pop_back();

                    right.pop_back();

                }

                else return false;

            }

        }

        if(left.length() != 0) return false;

        else if(right.length() != 0) return false;

        else return true;

    }

};