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

常见算法题目4 - 给定一个字符串，判断是否为有效的括号

web 2025/7/28 5:20:28

算法题目4 - 给定一个字符串，判断是否为有效的括号

1.问题描述

给定一个只包括 ( 、 )、 {、 }、 [、] 的字符串s，即6中括号字符，判断字符串是否有效。
有效字符串需满足：

左括号必须用相同类型的右括号闭合；
右括号必须以正确的顺序闭合。
例如：

输入：s = null
输出：false
输入：s = ""
输出：true
输入：s = "()"
输出：true
输入：s = "()[]{}"
输出：true
输入：s = "([])"
输出：true
输入：s = "([)]"
输出：false
输入：s = "({[)]}"
输出：false

2. 算法解决

2.1 解题思路

可以使用Java中的Stack(栈结构)辅助实现，栈的特点是先进后出(FILO).
①先进行空值判断。null默认返回false,""空字符串默认返回true；
②遍历字符串，使用栈结构存储左括号，遍历到右括号时，判断栈顶元素是否为对应的左括号，是则出栈，否则返回false
③遍历结束后，判断栈是否为空，为空则返回true，否则返回false.

2.2 代码实现

 /*** 题目：有效的括号* 时间复杂度：O(n)、空间复杂度：O(n)** @param s* @return*/public static boolean judgeEffectiveBrace(String s) {// 处理空数据if (s == null) {return false;}if (s.isEmpty()) {return true;}// 将字符串转换为字符数组char[] charArray = s.toCharArray();// 定义栈变量Stack<Character> stack = new Stack<>();// 遍历匹配for (char c : charArray) {// 如果是左括号 则入栈if (c == '(' || c == '{' || c == '[') {stack.push(c);} else {// 如果是右括号，判断栈是否为空if (stack.isEmpty()) {return false;}// 如果栈顶元素为对应的左括号，则出栈Character pop = stack.pop();// 如果匹配到栈顶元素为对应的左括号，则返回trueif (!(pop == '(' && c == ')')&& !(pop == '{' && c == '}')&& !(pop == '[' && c == ']')) {return false;}}}// 遍历结束后，判断栈是否为空，为空则返回true，否则返回falsereturn stack.isEmpty();}

3.测试

调用测试：

public class TestEffectiveBrace {public static void main(String[] args) {String str1 = null;boolean result1 = judgeEffectiveBrace(str1);System.out.println("字符串：" + str1 + "，判断有效的括号：" + result1);String str2 = "";boolean result2 = judgeEffectiveBrace(str2);System.out.println("字符串：" + str2 + "，判断有效的括号：" + result2);String str3 = "()";boolean result3 = judgeEffectiveBrace(str3);System.out.println("字符串：" + str3 + "，判断有效的括号：" + result3);String str4 = "()[]{}";boolean result4 = judgeEffectiveBrace(str4);System.out.println("字符串：" + str4 + "，判断有效的括号：" + result4);String str5 = "([])";boolean result5 = judgeEffectiveBrace(str5);System.out.println("字符串：" + str5 + "，判断有效的括号：" + result5);String str6 = "([)]";boolean result6 = judgeEffectiveBrace(str6);System.out.println("字符串：" + str6 + "，判断有效的括号：" + result6);String str7 = "({[)]}";boolean result7 = judgeEffectiveBrace(str7);System.out.println("字符串：" + str7 + "，判断有效的括号：" + result7);}}