当前位置：首页 > web >正文

CT02-20.有效的括号(Java)

web 2025/8/22 11:00:53

1.思路

先把字符串转换成字符数组
逐个遍历字符
如果遇到左括号，入栈。
如果遇到右括号
（1）判断此时栈是否为空，如果为空，说明没有左括号与右括号匹配，返回false。
（2）取出栈顶元素（反证法）
1）如果此时字符是‘）’，并且栈顶元素不等于‘（’，返回false
1）如果此时字符是‘]’，并且栈顶元素不等于‘[’，返回false
1）如果此时字符是‘}’，并且栈顶元素不等于‘{’，返回false
遍历完整个字符串后，检查栈是否为空。所以返回 st.isEmpty();这一行代码本身既可能返回 true 也可能返回 false，具体取决于在程序执行到这一步时，栈里是否还有剩余的元素。
如果栈为空，说明所有的左括号都找到了匹配的右括号。
如果栈不为空，说明有多余的左括号没有被匹配。

2.代码实现

class Solution {public boolean isValid(String s) {Stack<Character> st = new Stack<>();//for(int i=0;i<s.length();i++)for (char c : s.toCharArray()) {//这边为什么不用for(int i=0;i<s.length();i++){if(s.charAt(i）==‘{'||s.charAt(i)=='[')st.push('(');的原因是 到时候push的时候单个元素入栈//另一种写法for (int i = 0; i < s.length(); i++) {//            char c = s.charAt(i);//            // 遍历左括号，将对应的左括号入栈//            if (c == '(' || c == '[' || c == '{') {//                st.push(c); // 应该推入当前遇到的左括号字符//            }//遍历左括号，入栈if (c == '(' || c == '[' || c == '{') {st.push(c);} else//遇到右括号{// 在匹配右括号前，必须检查栈是否为空。// 如果栈为空，说明没有左括号与之对应，直接返回 falseif (st.isEmpty()) {return false;}//对于输入 ()[]{}，你的代码在匹配了 () 之后，就会直接返回 true，完全忽略了后面的 []{}。对于输入 (]，代码会因为 ( 和 ] 不匹配而继续执行，但因为没有处理不匹配的情况，最终可能会给出错误的结果。char top = st.pop();if (top == '(' && c != ')') {return false;}if (top == '[' && c != ']') {return false;}if (top == '{' && c != '}') {return false;}}}return st.isEmpty();}// public static void main(String[] args)// {//     String str="(){}[]";//     solution1 s=new solution1();//     System.out.println(s.isValid(str));// }
}