Java 括号匹配问题 Java 括号匹配问题案例详解
mgsky1 人气:0前言
括号匹配问题算是栈应用中比较经典的问题了,在数据结构的书中还有各种考试中会出现。最近刷题的时候也遇到了,就想写一篇文章整理一下。
例题
题目来自Leetcode中国
给定一个只包括 (,),{,},[,] 的字符串,判断字符串是否有效。
有效字符串需满足:
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
算法思想
S1:遍历输入的括号序列,如果是左括号,进入S2,如果是右括号,进入S3
S2:如果当前遍历到左括号,则入栈
S3:如果当前遍历到右括号,则出栈一个元素,看其是否与当前的右括号组成一对,如果不是,则匹配失败。或者在出栈过程中发生异常(从空栈中出栈),也匹配失败
S4:若能顺利遍历完成,检查栈中是否还有剩余元素,如果有,则匹配失败;如果没有,则匹配成功。
算法举例
下面以(({[]}) 序列为例说明算法过程:
1、首先将这个字符串转换成字符数组,并初始化一个空栈。
2、遍历到第0个元素,(,为左括号,入栈
3、后面以此类推,遍历完第3个元素[后,栈空间应该是这样的
4、遍历到第4个元素]时,发现为右括号,此时,从栈顶出栈一个左括号,即[,刚好[与],匹配成一对
5、以此类推,直到第6个元素),都是匹配的
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
与我们之前预测的一致。
加载全部内容