20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

 

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

 

提示：

1 <= s.length <= 104

s 仅由括号 '()[]{}' 组成

通过次数1,479,883提交次数3,357,490

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/valid-parentheses

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

注意：

剪枝技巧：当s为单数时必定返回false;

代码：

class Solution {

public:

    bool isValid(string s) {

        stack<char> box;

        if(s.size()%2==1)return false;

       for(int i=0;i<s.size();i++){

           if(s[i]=='(')box.push(')');

           else if(s[i]=='[')box.push(']');

           else if(s[i]=='{')box.push('}');

           else if(box.empty()||s[i]!=box.top())return false;

           else box.pop();

       }

       return box.empty();

    }

};

注意：

for循环中的第四个判断要把box.empty()放在前面，不然有可能操作空栈然后出现异常