括号匹配校验
假设表达式中允许包含两种括号，圆括号和方括号，其嵌套顺序随意，即[()[]]、[([][])]和[]()[]等为正确格式，[(])或([())等均为不正确格式。要求编写一个程序检验括号输入是否正确。
思路整理
此题我们使用栈的后进先出的原则来实现，思路如下：
- 如果以
]或)开头那么括号肯定是不匹配的。 - 将接收到的字符串拆分成单个字符
- 遍历入栈
- 若当前栈空，则直接入栈
- 若当前栈不为空，则取出栈顶数据与当前数据做对比。若两个括号匹配，则取出栈顶数据。否则将当前数据入栈
-
遍历完成后检查栈是否为空。若为空则说明校验成功，否则检验失败
956be32c0c934679801e1600a530d56cpng
代码实现
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();
}
}
以上测试代码已测试通过。由于栈的底层实现是数组或链表，所以使用数组的方式也可以解决此问题。只需要一个指针指向数组尾部数据即可。
行编辑程序
一个简单的行编辑器程序的功能是：接收用户从终端输入的程序或数据，对用户输入的一行数据做处理，#表示退格键，删除#前的一个字符。@表示@符号之前的数据均无效。
比如用户输入了 gosd##od实际有效字符是good，当用户输入了pgm@progre#am实际有效的是program。
思路分析
将一行的字符依次读入栈中，遇到#取出栈顶数据，若遇到@则清空栈。
实现
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());
}
}
