判定括号是否匹配
[!Tip]
本节源代码见Github链接🔗
问题描述
使用栈来判定括号是否匹配。对于给定大表达式，可以使用栈来实现括号匹配判断算法。这个算法在编译器中非常重要。解析器每次读入一个字符，如果字符是一个开分隔符（如(、{或[），那么将其入栈。若读入的是一个闭分隔符（如)、}、或]），那么将栈顶的开分隔符出栈，并与闭分隔符比较。如果两者匹配，则继续解析字符串。如果不匹配，解析器显式匹配错误。
核心思路
- 分别维护开、闭分隔符；
- 创建一个栈；
- 遍历字符串，并判断字符：
- 如果当前字符不是开/闭字符，则忽略；
- 如果是一个开分隔符，那么将其入栈；
- 如果是一个闭分隔符，但栈内无元素，则提示错误；
- 如果栈顶元素不是待处理字符相匹配的开分隔符，则提示匹配错误。
- 字符串处理结束后，如果栈不为空，则提示匹配错误。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 判定括号是否匹配
*
* @className: SymbolMatching
* @author: Max Solider
* @date: 2023-03-06 22:50
*/
public class SymbolMatching {
// 1.分别维护开、闭分隔符，以及他们之间匹配关系
final static List openSymbolList = new ArrayList() {
{
add("(");
add("{");
add("[");
}
};
final static List closeSymbolList = new ArrayList() {
{
add(")");
add("}");
add("]");
}
};
final static Map symbolMap = new HashMap() {
{
put(")", "(");
put("}", "{");
put("]", "[");
}
};
/**
* 判定括号是否匹配
* @param str 待判定字符串
* @return 判定结果
*/
public static boolean matchSymbol(String str) {
// 2.创建栈
LLStack llStack = new LLStack();
// 3.遍历字符串
for (char s : str.toCharArray()) {
if (openSymbolList.contains(String.valueOf(s))) {
llStack.push(String.valueOf(s));
} else if (closeSymbolList.contains(String.valueOf(s))) {
if (llStack.isEmpty()) {
return false;
}
String top = llStack.pop();
if (!top.equals(symbolMap.get(String.valueOf(s)))) {
return false;
}
}
}
// 4.判断栈内是否为空，不为空则说明有字符未被匹配
if (!llStack.isEmpty()) {
return false;
}
return true;
}
public static void main(String[] args) {
String str = "(A+B)+(C-D)";
System.out.println("The result of matching is " + matchSymbol(str));
str = "((A+B)+(C-D)";
System.out.println("The result of matching is " + matchSymbol(str));
str = "((A+B)+[C-D])";
System.out.println("The result of matching is " + matchSymbol(str));
str = "{(A+B)+(C-D))";
System.out.println("The result of matching is " + matchSymbol(str));
}
}
时间复杂度
时间复杂度为O(n)，用于扫描长度为n的字符串。
空间复杂度
空间复杂度为O(n)，用于栈空间。