给定一个只包括 ‘(’,‘)’,‘{’,‘}’,‘[’,‘]’ 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = “()”
输出:true
示例 2:
输入:s = “()[]{}”
输出:true
示例 3:
输入:s = “(]”
输出:false
提示:
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
class Solution {
public:
bool isValid(string s) {
stack<char>st;
if(!s.size()%2)return false;
for(const char& c : s){
if(c=='(')st.push(')');
else if(c=='{')st.push('}');
else if(c=='[')st.push(']');
//至此,如果输入的是左括号,则右括号入栈操作完毕
//下面的一定就是输入的右括号,需要进行出栈操作
else if(st.empty())return false;//若空栈则无法出栈,说明少了个左括号
else if(!st.empty()&&st.top()!=c)return false;//不为空,但是输入右括号与(先前左括号对应的)栈中右括号不匹配,说明左右括号不匹配
/* 下面是更精简的写法,平时很少关注这些细节:
else if(st.empty())return false;
else if(st.top()!=c)return false;
//下面的(2)else if(条件1)继承了对上面(1)else if(条件2)的条件,即对于else if,下面的else if是上面else if条件的否定'与':
对于(1)else if(条件1&&条件2||条件3);(2)else if(条件1||条件2)
实际执行(2)else if():
(2)else if(1.!(条件1&&条件2||条件3)&&2.(条件1||条件2))
若(1)(2)的返回东西一样,可以把(2)的条件'或'追加到(1)的条件中
(1)else if(1.(条件1&&条件2||条件3)||2.(条件1||条件2))return same;
*/
/*更精简的写法:
else if(st.empty()||st.top()!=c)return false;*/
else st.pop();//前面的出栈操作是对异常的判定,执行到这表示无异常,则正式出战
}
return (st.empty());//操作完了,但是栈还有残余,说明多了个左括号
}
};