Java 括號匹配問題案例詳解
前言
括號匹配問題算是棧應用中比較經(jīng)典的問題了,在數(shù)據(jù)結(jié)構(gòu)的書中還有各種考試中會出現(xiàn)。最近刷題的時候也遇到了,就想寫一篇文章整理一下。
例題
題目來自Leetcode中國
給定一個只包括 (,),{,},[,] 的字符串,判斷字符串是否有效。
有效字符串需滿足:
1、左括號必須用相同類型的右括號閉合。
2、左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。
示例 1:
輸入: “()”
輸出: true
示例 2:
輸入: “()[]{}”
輸出: true
示例 3:
輸入: “(]”
輸出: false
示例 4:
輸入: “([)]”
輸出: false
示例 5:
輸入: “{[]}”
輸出: true
算法思想
S1:遍歷輸入的括號序列,如果是左括號,進入S2,如果是右括號,進入S3
S2:如果當前遍歷到左括號,則入棧
S3:如果當前遍歷到右括號,則出棧一個元素,看其是否與當前的右括號組成一對,如果不是,則匹配失敗。或者在出棧過程中發(fā)生異常(從空棧中出棧),也匹配失敗
S4:若能順利遍歷完成,檢查棧中是否還有剩余元素,如果有,則匹配失??;如果沒有,則匹配成功。
算法舉例
下面以(({[]}) 序列為例說明算法過程:
1、首先將這個字符串轉(zhuǎn)換成字符數(shù)組,并初始化一個空棧。
2、遍歷到第0個元素,(,為左括號,入棧
3、后面以此類推,遍歷完第3個元素[后,棧空間應該是這樣的
4、遍歷到第4個元素]時,發(fā)現(xiàn)為右括號,此時,從棧頂出棧一個左括號,即[,剛好[與],匹配成一對
5、以此類推,直到第6個元素),都是匹配的
6、此時,序列已經(jīng)遍歷完畢,但是棧不是空的,所以原序列匹配失敗。
代碼
棧類
這里我使用了鏈棧,鏈表就沒有自己寫了,用了Java現(xiàn)成的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; } } } //循環(huán)完畢后,若棧不空,說明左括號個數(shù)大于右括號,不匹配 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; } } } //循環(huán)完畢后,若棧不空,說明左括號個數(shù)大于右括號,不匹配 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("(({[]})")); } }
運行結(jié)果
(({[]})的運行結(jié)果
false
Process finished with exit code 0
與我們之前預測的一致。
到此這篇關(guān)于Java 括號匹配問題案例詳解的文章就介紹到這了,更多相關(guān)Java 括號匹配問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
java.lang.UnsupportedClassVersionError錯誤的解決辦法(附圖文)
這篇文章主要給大家介紹了關(guān)于java.lang.UnsupportedClassVersionError錯誤的解決辦法,"java.lang.UnsupportedClassVersionError"意味著您正在運行的Java版本與編譯該類時使用的Java版本不兼容,需要的朋友可以參考下2023-10-10Java的中l(wèi)ombok下的@Builder注解用法詳解
這篇文章主要介紹了Java的中l(wèi)ombok下的@Builder注解用法詳解,lombok注解在java進行編譯時進行代碼的構(gòu)建,對于java對象的創(chuàng)建工作它可以更優(yōu)雅,不需要寫多余的重復的代碼,在出現(xiàn)lombok之后,對象的創(chuàng)建工作更提供Builder方法,需要的朋友可以參考下2023-11-112020年IntelliJ IDEA最新最詳細配置圖文教程詳解
這篇文章主要介紹了2020年IntelliJ IDEA最新最詳細配置圖文教程詳解,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-02-02Java中String字符串常量池和intern方法源碼分析
在之前的文章中,小編給大家介紹了String字符串的不可變性及其實現(xiàn)原理,其中給大家提到了字符串常量池的概念,那么什么是常量池,String字符串與常量池有什么關(guān)系,本文給大家嘮嘮字符串常量池及String#intern()方法的作用,需要的朋友可以參考下2023-05-05