假設表達式中允許包含兩種括號，圓括號和方括號，其嵌套順序隨意，即[()[]]、[([][])]和[]()[]等為正確格式，[(])或([())等均為不正確格式。要求編寫一個程序檢驗括號輸入是否正確。
實現思路
此題我們使用棧的后進先出的原則來實現，思路如下：
如果以]或)開頭那么括號肯定是不匹配的。
將接收到的字符串拆分成單個字符
遍歷入棧
若當前棧空，則直接入棧
若當前棧不為空，則取出棧頂數據與當前數據做對比。若兩個括號匹配，則取出棧頂數據。否則將當前數據入棧
遍歷完成后檢查棧是否為空。若為空則說明校驗成功，否則檢驗失敗
代碼實現
package com.codestd.study.stack;
import java.util.Stack;
/**
* 括號校驗
* @author jaune
* @since 1.0.0
*/
public class BracketChecker {
/**
* 校驗括號是否正確
* @param in 輸入括號字符串
*/
public static boolean check(String in) {
char[] chars = in.toCharArray();
Stack<Character> stack = new Stack<>();
for (char aChar : chars) {
// 如果不是括號字符直接丟棄
if (isBracket(aChar)) {
if (stack.isEmpty()) {
stack.push(aChar);
} else {
char stackChar = stack.peek();
// 注意這里的順序，一定是棧中的是前括號，比較的是后括號才行。順序不能亂。)( 這種格式是錯誤的。
if (checkPairBracket(stackChar, aChar)) {
stack.pop();
} else {
stack.push(aChar);
}
}
}
}
return stack.isEmpty();
}
/**
* 檢驗前括號和后括號是否匹配
* @param ch1 前括號
* @param ch2 后括號
*/
public static boolean checkPairBracket(char ch1, char ch2) {
return ch1 == '(' && ch2 == ')' || ch1 == '[' && ch2 == ']';
}
/**
* 檢查是否為括號字符
*/
public static boolean isBracket(char ch) {
return ch == '(' || ch == ')' || ch == '[' || ch == ']';
}
}
此題中只說了小括號和中括號，如果再加上大括號，或者書名號等成對出現的字符，核心的代碼不用做修改，只需要修改checkPairBracket和isBracket即可。無論多少種括號，校驗的原理都是一樣的。
測試代碼如下：
import static org.assertj.core.api.Assertions.*;
/**
* Test for {@link BracketChecker}
*/
public class BracketCheckerTest {
@Test
public void test() {
String s1 = "[]()[(())()]";
assertThat(BracketChecker.check(s1)).isTrue();
String s2 = ")[]()[]";
assertThat(BracketChecker.check(s2)).isFalse();
String s3 = "[(])[]";
assertThat(BracketChecker.check(s3)).isFalse();
}
}
以上測試代碼已測試通過。由于棧的底層實現是數組或鏈表，所以使用數組的方式也可以解決此問題。只需要一個指針指向數組尾部數據即可。
本站文章版權歸原作者及原出處所有 。內容為作者個人觀點， 并不代表本站贊同其觀點和對其真實性負責，本站只提供參考并不構成任何投資及應用建議。本站是一個個人學習交流的平臺，網站上部分文章為轉載，并不用于任何商業目的，我們已經盡可能的對作者和來源進行了通告，但是能力有限或疏忽，造成漏登，請及時聯系我們，我們將根據著作權人的要求，立即更正或者刪除有關內容。本站擁有對此聲明的最終解釋權。
