服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - Java 括号匹配问题案例详解

Java 括号匹配问题案例详解

2021-11-29 12:05mgsky1 Java教程

这篇文章主要介绍了Java 括号匹配问题案例详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下

前言

括号匹配问题算是栈应用中比较经典的问题了,在数据结构的书中还有各种考试中会出现。最近刷题的时候也遇到了,就想写一篇文章整理一下。

 

例题

题目来自Leetcode中国
给定一个只包括 (,),{,},[,] 的字符串,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:

输入: “()”
输出: true

示例 2:

输入: “()[]{}”
输出: true

示例 3:

输入: “(]”
输出: false

示例 4:

输入: “([)]”
输出: false

示例 5:

输入: “{[]}”
输出: true

 

算法思想

S1:遍历输入的括号序列,如果是左括号,进入S2,如果是右括号,进入S3
S2:如果当前遍历到左括号,则入栈
S3:如果当前遍历到右括号,则出栈一个元素,看其是否与当前的右括号组成一对,如果不是,则匹配失败。或者在出栈过程中发生异常(从空栈中出栈),也匹配失败
S4:若能顺利遍历完成,检查栈中是否还有剩余元素,如果有,则匹配失败;如果没有,则匹配成功。

 

算法举例

下面以(({[]}) 序列为例说明算法过程:
1、首先将这个字符串转换成字符数组,并初始化一个空栈。

Java 括号匹配问题案例详解

2、遍历到第0个元素,(,为左括号,入栈

Java 括号匹配问题案例详解

3、后面以此类推,遍历完第3个元素[后,栈空间应该是这样的

Java 括号匹配问题案例详解

4、遍历到第4个元素]时,发现为右括号,此时,从栈顶出栈一个左括号,即[,刚好[与],匹配成一对

Java 括号匹配问题案例详解

5、以此类推,直到第6个元素),都是匹配的

Java 括号匹配问题案例详解

6、此时,序列已经遍历完毕,但是栈不是空的,所以原序列匹配失败。

 

代码

栈类

这里我使用了链栈,链表就没有自己写了,用了Java现成的LinkedList<T>

/**
* 栈类,这里使用链栈
*/
class MyStack{
  private int num;
  private LinkedList<Character> data;

  public MyStack(){
      this.num = 0;
      data = new LinkedList<Character>();
  }

  /**
   * 判断栈是否为空
   * @return
   */
  public boolean isEmpty(){
      return num == 0 ? true : false;
  }

  /**
   * 入栈
   * @param ch
   */
  public void push(Character ch){
      this.data.add(ch);
      this.num++;
  }

  /**
   * 出栈
   * @return
   */
  public Character pop(){
  	 //栈为空时,返回' '
      if(this.isEmpty()){
          return ' ';
      }
      Character ch = this.data.remove(data.size()-1);
      this.num--;
      return ch;
  }
}

括号匹配核心算法

  /**
   * 核心方法
   * @param s
   * @return
   */
  public boolean isValid(String s) {
      char[] temp = s.toCharArray();
      MyStack stack = new MyStack();
      boolean flag = true;
      for(int i = 0 ; i < temp.length ; i++){
          //左括号,入栈
          if(temp[i] == '(' || temp[i] == '{' || temp[i] == '['){
              stack.push(temp[i]);
          }
          else{
              //右括号,出栈
              char left = stack.pop();
              //如果从栈中取出空值,说明栈已空,但还有右括号存在,肯定不匹配
              if(left == ' ') {
                  flag = false;
              }
              //如果左右括号不匹配,则失败
              if(!check(left,temp[i])){
                  flag = false;
              }
          }
      }
      //循环完毕后,若栈不空,说明左括号个数大于右括号,不匹配
      if(flag){
          if(!stack.isEmpty()){
              flag = false;
          }
      }
      return flag;
  }
}

完整代码

import java.util.LinkedList;

/**
* 括号匹配问题(Blog)
*/

/**
* 栈类,这里使用链栈
*/
class MyStack{
  private int num;
  private LinkedList<Character> data;

  public MyStack(){
      this.num = 0;
      data = new LinkedList<Character>();
  }

  /**
   * 判断栈是否为空
   * @return
   */
  public boolean isEmpty(){
      return num == 0 ? true : false;
  }

  /**
   * 入栈
   * @param ch
   */
  public void push(Character ch){
      this.data.add(ch);
      this.num++;
  }

  /**
   * 出栈
   * @return
   */
  public Character pop(){
      //栈为空时,返回' '
      if(this.isEmpty()){
          return ' ';
      }
      Character ch = this.data.remove(data.size()-1);
      this.num--;
      return ch;
  }
}

class Solution {

  /**
   * 判定左右括号是否匹配
   * @param left
   * @param right
   * @return
   */
  private boolean check(char left , char right){
      if(left == '('){
          return right == ')' ? true : false;
      }

      if(left == '['){
          return right == ']' ? true : false;
      }

      if(left == '{'){
          return right == '}' ? true : false;
      }
      return false;
  }

  /**
   * 核心方法
   * @param s
   * @return
   */
  public boolean isValid(String s) {
      char[] temp = s.toCharArray();
      MyStack stack = new MyStack();
      boolean flag = true;
      for(int i = 0 ; i < temp.length ; i++){
          //左括号,入栈
          if(temp[i] == '(' || temp[i] == '{' || temp[i] == '['){
              stack.push(temp[i]);
          }
          else{
              //右括号,出栈
              char left = stack.pop();
              //如果从栈中取出空值,说明栈已空,但还有右括号存在,肯定不匹配
              if(left == ' ') {
                  flag = false;
              }
              //如果左右括号不匹配,则失败
              if(!check(left,temp[i])){
                  flag = false;
              }
          }
      }
      //循环完毕后,若栈不空,说明左括号个数大于右括号,不匹配
      if(flag){
          if(!stack.isEmpty()){
              flag = false;
          }
      }
      return flag;
  }
}

public class Main {

  public static void main(String[] args) {
	// write your code here
      Solution solution = new Solution();
      System.out.println(solution.isValid("(({[]})"));
  }
}

 

运行结果

(({[]})的运行结果

false
Process finished with exit code 0

与我们之前预测的一致。

到此这篇关于Java 括号匹配问题案例详解的文章就介绍到这了,更多相关Java 括号匹配问题内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://blog.csdn.net/mgsky1/article/details/90612888

延伸 · 阅读

精彩推荐
  • Java教程springboot 文件上传大小配置的方法

    springboot 文件上传大小配置的方法

    本篇文章主要介绍了springboot 文件上传大小配置的方法,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...

    shi02993492021-01-19
  • Java教程Java设计模式之享元模式实例详解

    Java设计模式之享元模式实例详解

    这篇文章主要介绍了Java设计模式之享元模式,结合实例形式详细分析了享元模式的概念、功能、定义及使用方法,需要的朋友可以参考下...

    炸斯特8142021-04-21
  • Java教程Java用自定义的类作为HashMap的key值实例

    Java用自定义的类作为HashMap的key值实例

    下面小编就为大家带来一篇Java用自定义的类作为HashMap的key值实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...

    服务器之家4342020-07-11
  • Java教程java String[]字符串数组自动排序的简单实现

    java String[]字符串数组自动排序的简单实现

    下面小编就为大家带来一篇java String[]字符串数组自动排序的简单实现。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看...

    jingxian5372020-06-09
  • Java教程什么是Spring Boot

    什么是Spring Boot

    Spring是一个非常受欢迎的Java框架,它用于构建web和企业应用。本文介绍将各种Spring的配置方式,帮助您了解配置Spring应用的复杂性...

    Oopsguy3902020-12-12
  • Java教程springmvc和js前端的数据传递和接收方式(两种)

    springmvc和js前端的数据传递和接收方式(两种)

    本文介绍了springmvc和js前端的数据传递和接收方式(两种),详细的介绍了两种方式,一种是json格式传递,另一种是Map传递,具有一定的参考价值,有兴趣的...

    wushuchu7972021-03-10
  • Java教程Java中json与javaBean几种互转的讲解

    Java中json与javaBean几种互转的讲解

    今天小编就为大家分享一篇关于Java中json与javaBean几种互转的讲解,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小...

    8blues4052021-07-21
  • Java教程Zookeeper和Eureka哪个更好?

    Zookeeper和Eureka哪个更好?

    今天小编就为大家分享一篇关于Zookeeper和Eureka哪个更好?,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看...

    邋遢的流浪剑客4112021-07-15