本文旨在提供一个通用的、非正则表达式的解决方案，用于解析包含嵌套括号的字符串，并提取特定部分。通过构建一个括号树，我们可以轻松地遍历和搜索所需的匹配项，即使在存在未闭合括号的情况下也能有效工作。本教程将详细介绍如何使用 BracketTree 类来实现这一目标，并提供多种过滤遍历示例，以满足不同的提取需求。
在处理包含嵌套括号的字符串时，正则表达式可能会变得复杂且难以维护。尤其是在括号嵌套层数不确定，或者存在未闭合括号的情况下，正则表达式的编写和调试会变得非常困难。本文介绍一种基于树形结构的解析方法，可以有效地解决这类问题。
BracketTree 类
BracketTree 类用于构建和遍历括号树。以下是该类的详细说明：
class BracketTree {
constructor (brackets, string) {
if (typeof brackets != 'string' || brackets.length != 2 || brackets[0] == brackets[1]) {
return null;
}
let opening = brackets[0];
let closing = brackets[1];
function parse (start) {
let children = [];
let pos = start;
loop: while (pos < string.length) {
switch (string[pos]) {
case opening:
let child = parse(pos + 1);
children.push(child);
if (child.end == string.length) {
break loop;
}
pos = child.end;
break;
case closing:
if (start == 0) {
children = [{
children, start, end: pos, opened: false, closed: true,
contents: string.slice(0, pos)
}];
}
else {
return {
children, start, end: pos, opened: true, closed: true,
contents: string.slice(start, pos)
};
}
}
pos++;
}
return (start == 0)? {
children, start, end: string.length, opened: false, closed: false,
contents: string
}: {
children, start, end: string.length, opened: true, closed: false,
contents: string.slice(start)
};
}
this.root = parse(0);
}
traverse (callback) {
if (typeof callback != 'function') {
return false;
}
let root = this.root;
let input = root.contents;
let nodeId = 0;
function recurse (parent, level) {
function callbackLeaf (start, end) {
callback({
root, parent, level,
nodeId: nodeId++, childId: childId++,
start, end, contents: input.slice(start, end)
});
}
function callbackBranch (branch) {
return callback({
root, parent, branch, level,
nodeId: nodeId++, childId: childId++
});
}
let children = parent.children;
let childId = 0;
if (children.length == 0) {
callbackLeaf(parent.start, parent.end);
return;
}
callbackLeaf(parent.start, children[0].start - children[0].opened);
if (callbackBranch(children[0])) {
recurse(children[0], level+1);
}
for (var i = 0; i < children.length-1; i++) {
callbackLeaf(children[i].end + children[i].closed, children[i+1].start - children[i+1].opened);
if (callbackBranch(children[i+1])) {
recurse(children[i+1], level+1);
}
}
callbackLeaf(children[i].end + children[i].closed, parent.end);
}
recurse(root, 0);
return true;
}
}构造函数：
立即学习“Java免费学习笔记（深入）”；
- constructor(brackets, string)：接受两个参数，brackets 是一个包含开始和结束括号的字符串，string 是要解析的字符串。如果 brackets 的格式不正确，则返回 null。
方法：
- traverse(callback)：接受一个回调函数作为参数，用于遍历括号树的每个节点。回调函数接收一个包含节点信息的对象作为参数，包括 root（根节点）、parent（父节点）、branch（当前节点，如果它是分支节点）、level（节点层级）、nodeId（节点ID）、childId（子节点ID）、start（节点开始位置）、end（节点结束位置）和 contents（节点内容）。
使用示例
以下是一些使用 BracketTree 类的示例：
let input = 'NOT OPENED {3}2}1}***{avatarurl {id {message}}} blah blah blah {1{2{3} NOT CLOSED';
let tree = new BracketTree('{}', input);
function filteredTraverse (caption, leafFilter, branchFilter) {
console.log(`${'-'.repeat(29 - caption.length/2)} ${caption} `.padEnd(60, '-'));
leafFilter ??= () => true;
branchFilter ??= () => true;
tree.traverse((args) => {
if (args.branch) {
return branchFilter(args);
}
if (leafFilter(args)) {
console.log(`${' '.repeat(args.level)}<${args.contents}>`);
}
});
}
filteredTraverse(
'Ignore unbalanced and all their descendants',
null,
({branch}) => branch.opened && branch.closed
);
filteredTraverse(
'Ignore unbalanced but include their descendants',
({parent}) => parent.opened == parent.closed
);
filteredTraverse(
'Ignore empty',
({start, end}) => start != end
);
filteredTraverse(
'Show non-empty first children only',
({childId, start, end}) => childId == 0 && start != end
);代码解释：
- 创建 BracketTree 实例： 使用包含嵌套括号的字符串创建一个 BracketTree 实例。
- filteredTraverse 函数： 定义一个 filteredTraverse 函数，用于简化遍历过程。它接受一个标题 caption，以及两个可选的过滤函数 leafFilter 和 branchFilter。leafFilter 用于过滤叶子节点，branchFilter 用于过滤分支节点。
-
遍历示例： 通过调用 filteredTraverse 函数，展示了不同的过滤遍历示例：
- 忽略未闭合括号及其所有子节点： 只处理完全闭合的括号。
- 忽略未闭合括号，但包含其子节点： 处理所有括号，即使它们未完全闭合。
- 忽略空节点： 排除内容为空的括号。
- 只显示非空的第一个子节点： 只显示每个父节点的第一个非空子节点。
注意事项
- BracketTree 类假设输入的括号是成对出现的，并且开始和结束括号是不同的。
- traverse 方法会遍历整个括号树，因此在处理大型字符串时，性能可能会受到影响。
- 回调函数可以根据需要访问节点的信息，并执行相应的操作。
总结
本文介绍了一种使用 BracketTree 类解析包含嵌套括号的字符串的方法。这种方法避免了使用复杂的正则表达式，并且可以有效地处理未闭合括号的情况。通过遍历括号树，可以轻松地提取所需的匹配项，并执行各种操作。该方法在处理需要解析嵌套结构的场景中非常有用，例如解析配置文件、处理编程语言代码等。
