有效的括号（ LeetCode 20 ）
一、题目描述
给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 1、左括号必须用相同类型的右括号闭合。
-
2、左括号必须以正确的顺序闭合。
二、题目解析
有效的括号满足以下几个条件：
- 1、字符串的长度一定是偶数。
- 2、括号的匹配遵循右括号和最近的一个左括号进行匹配，它们匹配成功才有可能是有效的括号
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution {
public boolean isValid(String s) {
// 当字符串长度为奇数的时候，属于无效情况，直接返回 false
if (s.length() % 2 == 1) {
// 无效情况，返回 false
return false;
}
//构建一个栈，用来存储括号
Stack<Character> stack = new Stack<Character>();
// 把字符串转换为数组的形式，方便获取字符串中的每个字符
char charArray[] = s.toCharArray();
// 遍历字符串数组中的所有元素
for( int i = 0 ; i < charArray.length ; i++){
// 获取此时的字符
char c = charArray[i];
// 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
if(c == '('){
// 添加对左括号 （
stack.push('(');
// 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
}else if(c == '['){
// 添加对应的右括号 ]
stack.push('[');
// 如果字符为左括号 { ，那么就在栈中添加对左括号 {
}else if( c == '{'){
// 添加对应的右括号 }
stack.push('{');
// 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
}else {
// 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
// 找不到可以匹配的括号，返回 false
// 比如这种情况 }{，直接从右括号开始，此时栈为空
if(stack.isEmpty()) return false;
// 如果栈不为空，获取栈顶元素
char top = stack.peek();
// 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
if( top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}' ){
// 移除栈顶元素
stack.pop();
}else{
// 如果不相同，说明不匹配，返回 false
return false;
}
}
}
// 遍历完整个字符数组，判断栈是否为空
// 如果栈为空，说明字符数组中的所有括号都是闭合的
// 如果栈为空，说明有未闭合的括号
return stack.isEmpty();
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution {
public:
bool isValid(string s) {
// 当字符串长度为奇数的时候，属于无效情况，直接返回 false
if (s.size() % 2 == 1) {
// 无效情况，返回 false
return false;
}
//构建一个栈，用来存储括号
stack<char> stk ;
// 遍历字符串数组中的所有元素
for( int i = 0 ; i < s.size() ; i++){
// 获取此时的字符
char c = s[i];
// 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
if(c == '('){
// 添加对左括号 （
stk.push('(');
// 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
}else if(c == '['){
// 添加对应的右括号 ]
stk.push('[');
// 如果字符为左括号 { ，那么就在栈中添加对左括号 {
}else if( c == '{'){
// 添加对应的右括号 }
stk.push('{');
// 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
}else {
// 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
// 找不到可以匹配的括号，返回 false
// 比如这种情况 }{，直接从右括号开始，此时栈为空
if(stk.empty()) return false;
// 如果栈不为空，获取栈顶元素
char top = stk.top();
// 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
if( top == '(' && c == ')' || top == '[' && c == ']' || top == '{' && c == '}' ){
// 移除栈顶元素
stk.pop();
}else{
// 如果不相同，说明不匹配，返回 false
return false;
}
}
}
// 遍历完整个字符数组，判断栈是否为空
// 如果栈为空，说明字符数组中的所有括号都是闭合的
// 如果栈为空，说明有未闭合的括号
return stk.empty();
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# // 有效的括号（ LeetCode 20 ）:https://leetcode-cn.com/problems/valid-parentheses
class Solution:
def isValid(self, s: str) -> bool:
# 当字符串长度为奇数的时候，属于无效情况，直接返回 False
if len(s) % 2 == 1:
# 无效情况，返回 False
return False
# 构建一个栈，用来存储括号
stack = list()
# 遍历字符串数组中的所有元素
for c in s :
# 如果字符为左括号 ( ，那么就在栈中添加对左括号 （
if c == '(' :
# 添加对左括号 （
stack.append('(')
# 如果字符为左括号 [ ，那么就在栈中添加对左括号 [
elif c == '[' :
# 添加对应的右括号 ]
stack.append('[')
# 如果字符为左括号 { ，那么就在栈中添加对左括号 {
elif c == '{' :
# 添加对应的右括号 }
stack.append('{')
# 否则的话，说明此时 c 是 ）] } 这三种符号中的一种
else :
# 如果栈已经为空，而现在遍历的字符 c 是 ）] } 这三种符号中的一种
# 找不到可以匹配的括号，返回 False
# 比如这种情况 }{，直接从右括号开始，此时栈为空
if not stack :
return False
# 如果栈不为空，获取栈顶元素
top = stack[-1]
# 将栈顶元素和此时的元素 c 进行比较，如果相同，则将栈顶元素移除
if (top == '(' and c == ')' ) or (top == '[' and c == ']' ) or (top == '{' and c == '}') :
# 移除栈顶元素
stack.pop()
else :
# 如果不相同，说明不匹配，返回 False
return False
# 遍历完整个字符数组，判断栈是否为空
# 如果栈为空，说明字符数组中的所有括号都是闭合的
# 如果栈为空，说明有未闭合的括号
return not stack
