Java：有效括号字符串验证器

Java实现的有效括号字符串验证器

引言

在编程中，经常需要验证一组字符串中的括号是否正确配对。例如，检查一段代码或表达式中的圆括号、方括号和花括号是否成对出现。这类问题不仅在编程语言解析器中非常重要，也是许多软件开发场景中的基础需求。本文将介绍一种基于Java语言实现的有效括号字符串验证器，并通过JUnit框架对其进行测试。

问题描述

给定一个只包含 '(', ')', '{', '}', '[', ']' 的字符串 s，编写一个函数来检验字符串中的括号是否有效。有效的括号字符串需满足：

开闭括号必须以正确的顺序出现。
每个开括号必须有相应闭括号。
每个闭括号必须有相应开括号。

设计思路

为了解决这个问题，我们可以使用栈的数据结构来追踪每个开括号。当我们遇到一个开括号时，就将其压入栈中；当我们遇到一个闭括号时，就需要检查栈顶的开括号是否与之匹配。如果不匹配或栈为空，则字符串无效。如果遍历完成后栈为空，则说明所有的括号都正确配对。

实现代码

以下是使用Java语言实现的有效括号字符串验证器的代码：

java">import java.util.Stack;public class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char c : s.toCharArray()) {switch (c) {case '(':case '[':case '{':stack.push(c);break;case ')':if (stack.isEmpty() || stack.pop() != '(') return false;break;case ']':if (stack.isEmpty() || stack.pop() != '[') return false;break;case '}':if (stack.isEmpty() || stack.pop() != '{') return false;break;default:// 忽略非括号字符break;}}return stack.isEmpty();}public static void main(String[] args) {Solution solution = new Solution();System.out.println(solution.isValid("()[]{}")); // 应该输出 trueSystem.out.println(solution.isValid("(]"));     // 应该输出 falseSystem.out.println(solution.isValid("([)]"));   // 应该输出 falseSystem.out.println(solution.isValid("{[]}"));   // 应该输出 true}
}

代码解释

初始化栈：使用Stack类创建一个空栈。
遍历字符串：将字符串转换为字符数组，并遍历每个字符。
入栈：遇到开括号时，将其压入栈中。
匹配并出栈：遇到闭括号时，检查栈是否为空，如果为空或栈顶元素与当前闭括号不匹配，则返回false；否则弹出栈顶元素。
返回结果：如果栈为空，则所有括号都已正确配对，返回true；否则返回false。

单元测试

为了确保代码的正确性和健壮性，我们可以使用JUnit框架编写测试用例：

java">import org.junit.Test;
import static org.junit.Assert.*;public class SolutionTest {private Solution solution = new Solution();@Testpublic void testIsValid() {assertTrue(solution.isValid("()"));assertTrue(solution.isValid("()[]{}"));assertFalse(solution.isValid("(]"));assertFalse(solution.isValid("([)]"));assertTrue(solution.isValid("{[]}"));}
}

java">import java.util.Stack;public class Solution {/*** 检查字符串中的括号是否有效配对。** @param s 输入的字符串，只包含'(',')','[',']','{','}'。* @return 如果字符串中的括号有效配对，返回true；否则返回false。*/public boolean isValid(String s) {char[] parentheses = {'(', ')', '[', ']', '{', '}'};int i = 0;char c;int[] sum = {0, 0, 0}; // 用于记录每种括号的数量Stack<Integer> top = new Stack<>(); // 用于存放遇到的开括号// 遍历字符串中的每个字符while (i < s.length) {c = s.charAt(i);// 检查字符是否为开括号for (int j = 0; j <= 2; j++) {if (c == parentheses[j]) {top.push(j); // 将对应的索引值推入栈sum[j]++; // 记录开括号数量增加} else if (c == parentheses[j + 3]) {// 检查字符是否为闭括号if (top.size() == 0 || top.peek() != j) {// 栈为空或栈顶的开括号与当前闭括号不匹配，返回falsereturn false;}top.pop(); // 弹出栈顶的开括号sum[j]--; // 记录开括号数量减少}// 如果既不是开括号也不是闭括号，则忽略}i++;}// 遍历完成之后检查每种括号的数量是否为0for (int j = 0; j <= 2; j++) {if (sum[j] != 0) {// 如果有任何一种括号数量不为0，说明有未配对的括号，返回falsereturn false;}}// 如果所有括号都正确配对，返回truereturn true;}public static void main(String[] args) {Solution solution = new Solution();System.out.println(solution.isValid("()[]{}")); // 应该输出 trueSystem.out.println(solution.isValid("(]"));     // 应该输出 falseSystem.out.println(solution.isValid("([)]"));   // 应该输出 falseSystem.out.println(solution.isValid("{[]}"));   // 应该输出 true}
}

代码解释

初始化变量：
- parentheses 数组存储了所有可能的括号字符。
- sum 数组用于记录每种类型括号的数量。
- top 栈用于存放遇到的开括号的索引值。
遍历字符串：
- 使用 while 循环遍历字符串中的每个字符。
- 使用内部 for 循环检查字符是否为开括号或闭括号。
处理开括号：
- 如果字符是开括号，将其对应的索引值推入栈，并在 sum 数组中对应位置增加计数。
处理闭括号：
- 如果字符是闭括号，检查栈是否为空或栈顶的开括号是否与之匹配。
- 如果不匹配或栈为空，则返回 false。
- 否则，弹出栈顶的开括号，并在 sum 数组中对应位置减少计数。
检查括号数量：
- 在遍历完成后，检查每种括号的数量是否为零。
- 如果有任何一种括号数量不为零，则返回 false。
返回结果：
- 如果所有括号都正确配对，返回 true。