🔎前言:
在之前我們學過了堆疊與佇列，本次我們就學習一下如何利用堆疊去解決一個經典基礎問題，那就是括號匹配問題，希望能夠幫助大家理解解決這個問題，
📘 博客主頁：to Keep博客主頁
🙆歡迎關注，👍點贊，📝留言評論
?首發時間：2021年12月30日
📨 博主碼云地址：博主碼云地址
📕參考書籍：java核心技術 卷1
📢編程練習：牛客網+力扣網
由于博主目前也是處于一個學習的狀態，如有講的不對的地方，請一定聯系我予以改正！！！
文章目錄
- 🔎題目描述:
- 🎹問題分析：
- 🎄1 可能存在左括號多的情況
- 🎄2 可能存在右括號多的情況
- 🎄3 存在括號不匹配的情況
- 🔐總結解題思路：
- ?代碼實作：
🔎題目描述:
給定一個只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字串 s ，判斷字串是否有效，
有效字串需滿足：
左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合
題目鏈接:括號匹配問題
🎹問題分析：
🎄1 可能存在左括號多的情況
🎄2 可能存在右括號多的情況
🎄3 存在括號不匹配的情況
🔐總結解題思路：
1 我們在遍歷字串的程序中，需要先取得堆疊頂的元素與右括號比較，看是否匹配，如果匹配才能出堆疊，
2 在出堆疊的程序中，如果堆疊為空，說明右括號多了，如果發現堆疊頂元素與右括號不是匹配的括號，那么就需要直接return了
3 在整個字串遍歷結束之后，我們要判斷一下堆疊是否為空，如果為空，說明是匹配的，否則就是左括號偏多的情況，
?代碼實作：
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(int i = 0;i<s.length();i++){
char ch = s.charAt(i);
if(ch=='('||ch=='['||ch=='{'){
stack.push(ch);//左括號進堆疊
}else{
if(stack.empty()){//堆疊為空，右括號多了
return false;
}else{
char ch1 = stack.peek();//取堆疊頂元素
if(ch1=='('&& ch ==')'||ch1=='{'&&ch=='}'||ch1=='['&&ch==']'){
stack.pop();//匹配出堆疊
}else{
return false;//括號不匹配
}
}
}
}
if(!stack.empty()){
return false;//堆疊不為空，左括號偏多了
}
return true;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/398675.html
標籤：java