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

2024-09-01 17:20

本文主要是介绍Java:有效括号字符串验证器,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

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

引言

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

问题描述

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

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

设计思路

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

实现代码

以下是使用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}
}

代码解释

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

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

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("{[]}"));}
}
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}
}

代码解释

  1. 初始化变量

    • parentheses 数组存储了所有可能的括号字符。
    • sum 数组用于记录每种类型括号的数量。
    • top 栈用于存放遇到的开括号的索引值。
  2. 遍历字符串

    • 使用 while 循环遍历字符串中的每个字符。
    • 使用内部 for 循环检查字符是否为开括号或闭括号。
  3. 处理开括号

    • 如果字符是开括号,将其对应的索引值推入栈,并在 sum 数组中对应位置增加计数。
  4. 处理闭括号

    • 如果字符是闭括号,检查栈是否为空或栈顶的开括号是否与之匹配。
    • 如果不匹配或栈为空,则返回 false
    • 否则,弹出栈顶的开括号,并在 sum 数组中对应位置减少计数。
  5. 检查括号数量

    • 在遍历完成后,检查每种括号的数量是否为零。
    • 如果有任何一种括号数量不为零,则返回 false
  6. 返回结果

    • 如果所有括号都正确配对,返回 true

结论

通过上述方法,我们成功实现了一个简单而高效的括号字符串验证器。该验证器利用栈的先进后出特性,有效地解决了括号配对问题。此外,通过JUnit测试框架,我们还确保了代码的质量和可靠性。这对于软件开发中的各种应用场景都是非常有用的。
有效括号

这篇关于Java:有效括号字符串验证器的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1127571

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权,允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true (Spring security默认会带有ROLE_前缀),去

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程,特意画了如下的类图,包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口,接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类,它们之间的依赖,构建起了整个框架。想要理解整个架构,最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文(security context)的信息。当前操作的用户是谁,该用户是否已经被认证,他拥有哪些角色权限…这些都被保

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

JAVA智听未来一站式有声阅读平台听书系统小程序源码

智听未来,一站式有声阅读平台听书系统 🌟&nbsp;开篇:遇见未来,从“智听”开始 在这个快节奏的时代,你是否渴望在忙碌的间隙,找到一片属于自己的宁静角落?是否梦想着能随时随地,沉浸在知识的海洋,或是故事的奇幻世界里?今天,就让我带你一起探索“智听未来”——这一站式有声阅读平台听书系统,它正悄悄改变着我们的阅读方式,让未来触手可及! 📚&nbsp;第一站:海量资源,应有尽有 走进“智听

浅谈主机加固,六种有效的主机加固方法

在数字化时代,数据的价值不言而喻,但随之而来的安全威胁也日益严峻。从勒索病毒到内部泄露,企业的数据安全面临着前所未有的挑战。为了应对这些挑战,一种全新的主机加固解决方案应运而生。 MCK主机加固解决方案,采用先进的安全容器中间件技术,构建起一套内核级的纵深立体防护体系。这一体系突破了传统安全防护的局限,即使在管理员权限被恶意利用的情况下,也能确保服务器的安全稳定运行。 普适主机加固措施: