Valid Parentheses

编号 : 20      
难度 : <font color="green">Easy</font>

# 题目 :  
>Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.
>
>An input string is valid if:
>
>1. Open brackets must be closed by the same type of brackets.  
>2. 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  
>

# 解 :  
```Cpp
class Solution {
public:
    bool isValid(string s) {
        /* 查找匹配的括号 */
        map<char, char> match = {
            {')', '('},
            {']', '['},
            {'}', '{'},
        };
        
        /* 区分是左括号还是又括号 */
        string left = "([{";
        string right = ")]}";
        
        /* 用栈保存尚未闭合的左括号 */
        stack<char> openBrackets;
        
        for(auto& ch : s)
        {
            /* 左括号入栈 */
            if(left.find_first_of(ch) != string::npos)
            {
                openBrackets.push(ch);
            }
            else if(right.find_first_of(ch) != string::npos)
            {
                /* 没有左括号时读到右括号 */
                if(openBrackets.empty())
                {
                    return false;
                }
                
                char leftBracket = openBrackets.top();
                if(leftBracket == match[ch])
                {
                    /* 右括号匹配最后一个未闭合的左括号，左括号出栈 */
                    openBrackets.pop();
                }
                else
                {
                    /* 不匹配 */
                    return false;
                }
            }
        }
        
        /* 没有剩下未闭合的左括号 */
        return openBrackets.empty();
    }
};
```

# 分析 :  
这道题要求检查一组完全由括号组成的字符串，是否符合逻辑。   

用一个栈缓存未闭合的左括号，读到左括号就入栈，读到右括号就判断是否和栈顶的左括号匹配，如果匹配就出栈，不匹配就返回`false`。

读完整个字符串后，如果栈是空的，说明括号字符串符合逻辑，否则不符合逻辑。