您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關Java中括號匹配問題的示例分析的內容。小編覺得挺實用的,因此分享給大家做個參考,一起跟隨小編過來看看吧。
題目來自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
與我們之前預測的一致。
感謝各位的閱讀!關于“Java中括號匹配問題的示例分析”這篇文章就分享到這里了,希望以上內容可以對大家有一定的幫助,讓大家可以學到更多知識,如果覺得文章不錯,可以把它分享出去讓更多的人看到吧!
免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。