# Valid Parentheses

## Valid Parentheses

### 描述

> Given a string `s` 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.

### 例子

> Input: s = "()" 
>
> Output: true
>
> Input: s = "()\[]{}" 
>
> Output: true
>
> Input: s = "(]" 
>
> Output: false

### 解法

[string::npos](http://www.cplusplus.com/reference/string/string/npos/): npos 是一个常数，用来表示不存在的位置，类型一般是std::container\_type::size\_type 许多容器都提供这个东西。取值由实现决定，一般是-1，这样做，就不会存在移植的问题了。

查找字符串a是否包含子串b, 不是用strA.find(strB) > 0而是strA.find(strB) != string:npos。

因为 string::size\_type (由字符串配置器 allocator 定义) 描述的是 size，故需为无符号整数型别。因为缺省配置器以型别 size\_t 作为 size\_type，于是 -1 被转换为无符号整数型别，npos 也就成了该型别的最大无符号值。不过实际数值还是取决于型别 size\_type 的实际定义。不幸的是这些最大值都不相同。事实上，(unsigned long)-1 和 (unsigned short)-1 不同(前提是两者型别大小不同)。因此，比较式 idx == string::npos 中，如果 idx 的值为-1，由于 idx 和字符串string::npos 型别不同，比较结果可能得到 false。

[string.find()](http://www.cplusplus.com/reference/string/string/find/)

```cpp
class Solution {
public:
    bool isValid(string s) {
        string left="([{";
        string right=")]}";
        stack<char> SR;
        for(char c:s){
            if(left.find(c)!=string::npos){
                SR.push(c);
            }else{
                if(SR.empty()||SR.top()!=left[right.find(c)])
                    return false;
                else
                    SR.pop();
            }
        }
        return SR.empty();
    }
};
```