Java 括號匹配問題案例詳解
前言
括號匹配問題算是棧應用中比較經(jīng)典的問題了，在數(shù)據(jù)結構的書中還有各種考試中會出現(xiàn)。最近刷題的時候也遇到了，就想寫一篇文章整理一下。
例題
題目來自Leetcode中國
給定一個只包括 (，)，{，}，[，] 的字符串，判斷字符串是否有效。
有效字符串需滿足：
1、左括號必須用相同類型的右括號閉合。
2、左括號必須以正確的順序閉合。
注意空字符串可被認為是有效字符串。
示例 1:
輸入: “()”
輸出: true
示例 2:
輸入: “()[]{}”
輸出: true
示例 3:
輸入: “(]”
輸出: false
示例 4:
輸入: “([)]”
輸出: false
示例 5:
輸入: “{[]}”
輸出: true
算法思想
S1：遍歷輸入的括號序列，如果是左括號，進入S2，如果是右括號，進入S3
S2：如果當前遍歷到左括號，則入棧
S3：如果當前遍歷到右括號，則出棧一個元素，看其是否與當前的右括號組成一對，如果不是，則匹配失敗?；蛘咴诔鰲＿^程中發(fā)生異常(從空棧中出棧)，也匹配失敗
S4：若能順利遍歷完成，檢查棧中是否還有剩余元素，如果有，則匹配失?。蝗绻麤]有，則匹配成功。
算法舉例
下面以(({[]}) 序列為例說明算法過程：
1、首先將這個字符串轉換成字符數(shù)組，并初始化一個空棧。
2、遍歷到第0個元素，(，為左括號，入棧
3、后面以此類推，遍歷完第3個元素[后，?？臻g應該是這樣的
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("(({[]})"));
}
}
運行結果
(({[]})的運行結果
false
Process finished with exit code 0
與我們之前預測的一致。
到此這篇關于Java 括號匹配問題案例詳解的文章就介紹到這了,更多相關Java 括號匹配問題內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
java調用百度定位api服務獲取地理位置示例，大家參考使用吧2013-12-12
這篇文章主要介紹了Java與Kotlin互調原理，分享內(nèi)容有Kt調用-Java參數(shù)非null的處理、Java中使用kt關鍵字聲明的變量和方法、Kt調用Java-SAM轉換等內(nèi)容，需要的小伙伴可以參考一下2022-02-02
Java解決No enclosing instance of type PrintListFromTailToHead
這篇文章主要介紹了Java解決No enclosing instance of type PrintListFromTailToHead is accessible問題的兩種方案的相關資料,需要的朋友可以參考下2016-07-07
這篇文章主要介紹了Java將字符串寫入文本文件代碼示例，具有一定借鑒價值，需要的朋友可以參考下。2017-12-12
這篇文章主要介紹了java方法替換word文檔中需要替換的部分操作的相關資料,需要的朋友可以參考下,包括引入依賴、創(chuàng)建業(yè)務方法、測試以及擴展功能,需要的朋友們可以參考下2024-12-12
這篇文章主要介紹了基于Java的代碼審計功能的基礎知識，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-09-09
這篇文章主要介紹了Java如何限制IP訪問頁面，幫助大家完成需求，實現(xiàn)白名單，感興趣的朋友可以了解下2020-09-09
這篇文章主要介紹了Java 回調函數(shù)詳解及使用,附有簡單實例，需要的朋友可以參考下2017-03-03
下面小編就為大家?guī)硪黄狫ava基礎的幾道練習題(分享)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧，希望可以幫到你2021-07-07
SpringBoot線上環(huán)境徹底關閉Swagger-UI的方式
這篇文章主要給大家介紹了SpringBoot線上環(huán)境徹底關閉Swagger-UI的方式,文中給出了詳細的代碼示例供大家參考,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2023-12-12