有效的括号
输入一个字符串，其中包含 `[](){}` 六种括号，请你判断这个字符串组成的括号是否有效。
举几个例子：
Input: "()[]{}"
Output: true
Input: "([)]"
Output: false
Input: "{[]}"
Output: true解决这个问题之前，我们先降低难度，思考一下，**如果只有一种括号 `()`**，应该如何判断字符串组成的括号是否有效呢？
假设字符串中只有圆括号，如果想让括号字符串有效，那么必须做到：
**每个右括号 `)` 的左边必须有一个左括号 `(` 和它匹配**。
比如说字符串 `()))((` 中，中间的两个右括号**左边**就没有左括号匹配，所以这个括号组合是无效的。
那么根据这个思路，我们可以写出算法：
boolean isValid(String str) {
// 待匹配的左括号数量
int left = 0;
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == '(') {
left++;
} else {
// 遇到右括号
left--;
}
// 右括号太多
if (left == -1)
return false;
}
// 是否所有的左括号都被匹配了
return left == 0;
}如果只有圆括号，这样就能正确判断有效性。对于三种括号的情况，我一开始想模仿这个思路，定义三个变量 `left1`，`left2`，`left3` 分别处理每种括号，虽然要多写不少 if else 分支，但是似乎可以解决问题。
但实际上直接照搬这种思路是不行的，比如说只有一个括号的情况下 `(())` 是有效的，但是多种括号的情况下， `[(])` 显然是无效的。
仅仅记录每种左括号出现的次数已经不能做出正确判断了，我们要加大存储的信息量，可以利用栈来模仿类似的思路。栈是一种先进后出的数据结构，处理括号问题的时候尤其有用。
我们这道题就用一个名为 `left` 的栈代替之前思路中的 `left` 变量，遇到左括号就入栈，遇到右括号就去栈中寻找最近的左括号，看是否匹配：
boolean isValid(String str) {
Stack<Character> left = new Stack<>();
for (char c : str.toCharArray()) {
if (c == '(' || c == '{' || c == '[')
left.push(c);
else { // 字符 c 是右括号
if (!left.empty() && leftOf(c) == left.peek())
left.pop();
else
// 和最近的左括号不匹配
return false;
}
}
// 是否所有的左括号都被匹配了
return left.empty();
}
char leftOf(char c) {
if (c == '}') return '{';
if (c == ')') return '(';
return '[';
}原文地址：https://blog.csdn.net/Sloent/article/details/135708965
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！