目录
1.题目
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
示例 4：
输入：s = “([)]”
输出：false
示例 5：
输入：s = “{[]}”
输出：true
提示：
1 <= s.length <= 10
4
s 仅由括号 ‘()[]{}’ 组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
2.思路
（1）栈
判断括号的有效性可以使用
栈
这一数据结构：
① 先创建好一个栈
stack
，刚开始时栈为空，并且开始遍历字符串；
② 如果当前字符 c1 为任意一个左括号（即’(‘，‘[’，‘{’中的任意一个），则将其压入栈中，并且继续遍历；
③ 否则就判断栈是否为空，如果栈为空，则说明当前遍历到的右括号（任意一个都是）在栈中没有对应的左括号，所以配对失败，直接返回 false 即可；如果栈不为空，则取出栈顶字符并赋值给 c2，要想配对成功，c2 必须时与 c1 匹配的左括号，所以根据它们的 ASCII 值的组合可以判断是否有效。如果有效则返回步骤 ② 继续遍历，知道遍历结束或直接返回结果为止；
④ 如果遍历结束，当栈为空时，说明全部的括号已经按顺序配对完成，返回true，否则说明栈中还有多余的括号，则返回 false。
相关题目：
LeetCode_递归_回溯算法_中等_22.括号生成
LeetCode_栈_动态规划_困难_32.最长有效括号
LeetCode_回溯_困难_301. 删除无效的括号
LeetCode_栈_中等_856.括号的分数
LeetCode_栈_中等_921.使括号有效的最少添加
3.代码实现（Java）
//思路1————栈
class Solution {
public boolean isValid(String s) {
//字符串长度为奇数时，不可能配对成功，直接返回false即可
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
char c1, c2;
int temp;
for (int i = 0; i < s.length(); i++) {
c1 = s.charAt(i);
if (c1 == '(' || c1 == '[' || c1 == '{') {
//将字符c1添加到栈中
stack.add(c1);
} else {
if (stack.isEmpty()) {
return false;
} else {
//取出栈顶元素并赋值给c2
c2 = stack.pop();
temp = 0 + c1 + c2;
/*
各个括号的ASCII值如下：
'(':40 ')':41 '[':91 ']':93 '{':123 '}':125
取出的括号如果能够正确配对，则只会它们的 ASCII 值之和只会出现 81、184 和 248 这 3 种情况
*/
if (temp != 81 && temp != 184 && temp != 248) {
return false;
}
}
}
}
//遍历结束后，当栈为空时，说明全部的括号已经按顺序配对完成
return stack.isEmpty();
}
}
//另一种写法
class Solution {
public boolean isValid(String s) {
//字符串长度为奇数时，不可能配对成功，直接返回false即可
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (c == '(' || c == '[' || c == '{') {
//字符c为左括号时，将其压入栈顶
stack.push(c);
} else {
//字符为右括号
if (!stack.isEmpty() && stack.peek() == getLeftBracket(c)) {
//取出栈顶元素
stack.pop();
} else {
//不匹配时直接返回false
return false;
}
}
}
//遍历结束后，当栈为空时，说明全部的括号已经按顺序配对完成
return stack.isEmpty();
}
//获取右括号c对应的左括号
public char getLeftBracket(char c) {
if (c == ')') {
return '(';
} else if (c == ']') {
return '[';
} else {
return '{';
}
}
}