括號(hào)匹配校驗(yàn)
假設(shè)表達(dá)式中允許包含兩種括號(hào)又碌，圓括號(hào)和方括號(hào)，其嵌套順序隨意裕循，即[()[]]椎扬、[([][])]和[]()[]等為正確格式，[(])或([())等均為不正確格式谓晌。要求編寫(xiě)一個(gè)程序檢驗(yàn)括號(hào)輸入是否正確别垮。
思路整理
此題我們使用棧的后進(jìn)先出的原則來(lái)實(shí)現(xiàn)，思路如下：
- 如果以
]或)開(kāi)頭那么括號(hào)肯定是不匹配的扎谎。 - 將接收到的字符串拆分成單個(gè)字符
- 遍歷入棧
- 若當(dāng)前椞枷耄空，則直接入棧
- 若當(dāng)前棧不為空毁靶，則取出棧頂數(shù)據(jù)與當(dāng)前數(shù)據(jù)做對(duì)比胧奔。若兩個(gè)括號(hào)匹配，則取出棧頂數(shù)據(jù)预吆。否則將當(dāng)前數(shù)據(jù)入棧
-
遍歷完成后檢查棧是否為空龙填。若為空則說(shuō)明校驗(yàn)成功，否則檢驗(yàn)失敗
956be32c0c934679801e1600a530d56cpng
代碼實(shí)現(xiàn)
package com.codestd.study.stack;
import java.util.Stack;
/**
* 括號(hào)校驗(yàn)
* @author jaune
* @since 1.0.0
*/
public class BracketChecker {
/**
* 校驗(yàn)括號(hào)是否正確
* @param in 輸入括號(hào)字符串
*/
public static boolean check(String in) {
char[] chars = in.toCharArray();
Stack<Character> stack = new Stack<>();
for (char aChar : chars) {
// 如果不是括號(hào)字符直接丟棄
if (isBracket(aChar)) {
if (stack.isEmpty()) {
stack.push(aChar);
} else {
char stackChar = stack.peek();
// 注意這里的順序，一定是棧中的是前括號(hào)岩遗，比較的是后括號(hào)才行扇商。順序不能亂。)( 這種格式是錯(cuò)誤的宿礁。
if (checkPairBracket(stackChar, aChar)) {
stack.pop();
} else {
stack.push(aChar);
}
}
}
}
return stack.isEmpty();
}
/**
* 檢驗(yàn)前括號(hào)和后括號(hào)是否匹配
* @param ch1 前括號(hào)
* @param ch2 后括號(hào)
*/
public static boolean checkPairBracket(char ch1, char ch2) {
return ch1 == '(' && ch2 == ')' || ch1 == '[' && ch2 == ']';
}
/**
* 檢查是否為括號(hào)字符
*/
public static boolean isBracket(char ch) {
return ch == '(' || ch == ')' || ch == '[' || ch == ']';
}
}
此題中只說(shuō)了小括號(hào)和中括號(hào)案铺，如果再加上大括號(hào)，或者書(shū)名號(hào)等成對(duì)出現(xiàn)的字符梆靖，核心的代碼不用做修改控汉，只需要修改checkPairBracket和isBracket即可。無(wú)論多少種括號(hào)返吻，校驗(yàn)的原理都是一樣的姑子。
測(cè)試代碼如下：
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();
}
}
以上測(cè)試代碼已測(cè)試通過(guò)。由于棧的底層實(shí)現(xiàn)是數(shù)組或鏈表测僵，所以使用數(shù)組的方式也可以解決此問(wèn)題街佑。只需要一個(gè)指針指向數(shù)組尾部數(shù)據(jù)即可。
行編輯程序
一個(gè)簡(jiǎn)單的行編輯器程序的功能是：接收用戶從終端輸入的程序或數(shù)據(jù)捍靠，對(duì)用戶輸入的一行數(shù)據(jù)做處理舆乔，#表示退格鍵，刪除#前的一個(gè)字符剂公。@表示@符號(hào)之前的數(shù)據(jù)均無(wú)效希俩。
比如用戶輸入了 gosd##od實(shí)際有效字符是good，當(dāng)用戶輸入了pgm@progre#am實(shí)際有效的是program纲辽。
思路分析
將一行的字符依次讀入棧中颜武，遇到#取出棧頂數(shù)據(jù)，若遇到@則清空棧拖吼。
實(shí)現(xiàn)
import java.util.Arrays;
import java.util.Stack;
import java.util.stream.Collectors;
/**
* 行編輯器
*
* @author jaune
*/
public class LineEditor {
public String handle(String line) {
char[] chars = line.toCharArray();
Stack<Character> stack = new Stack<>();
for (char ch : chars) {
if (stack.isEmpty()) {
if (ch != '#' && ch != '@') {
stack.push(ch);
}
} else {
if (ch == '#') {
stack.pop();
} else if (ch == '@') {
stack.clear();
} else {
stack.push(ch);
}
}
}
Character[] res = new Character[stack.size()];
stack.toArray(res);
stack.clear();
return Arrays.stream(res).map(String::valueOf).collect(Collectors.joining());
}
}
