本文旨在提供一种使用 JavaScript 处理嵌套括号结构的通用解决方案，该方案不依赖正则表达式，而是通过构建括号树来实现对括号内特定部分内容的提取。这种方法可以有效处理括号不平衡的情况，并提供灵活的遍历和过滤机制，适用于需要处理复杂嵌套结构的场景。
括号树的构建
核心思想是将输入的字符串解析成一棵树，树的每个节点代表一个括号对及其内部的内容。以下是实现这一过程的 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);
}
}这段代码定义了一个 BracketTree 类，其构造函数接收两个参数：brackets (一个包含开始和结束括号的字符串，例如 "{}") 和 string (需要解析的字符串)。parse 函数递归地遍历字符串，当遇到开始括号时，创建一个新的子节点并递归调用 parse 函数。当遇到结束括号时，返回当前节点的信息。
树的遍历
为了提取括号内的内容，我们需要遍历构建好的括号树。BracketTree 类提供了一个 traverse 方法，它接受一个回调函数作为参数，并在遍历树的每个节点时调用该回调函数。
立即学习“Java免费学习笔记（深入）”；
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;
}traverse 方法使用递归的方式遍历树，并在每个节点上调用回调函数。回调函数接收一个包含节点信息的对象，例如节点的层级、父节点、子节点等。
示例与应用
以下是一个使用 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 对象，然后定义了一个 filteredTraverse 函数，该函数接受一个标题和两个过滤器函数作为参数。filteredTraverse 函数使用 traverse 方法遍历树，并根据过滤器函数来决定是否打印节点的内容。
这个示例展示了如何使用 BracketTree 类来处理包含嵌套括号的字符串，并提取特定的内容。通过自定义过滤器函数，可以灵活地控制提取的内容。
注意事项与总结
- 性能考量: 对于非常大的字符串，递归的 parse 函数可能会导致性能问题。可以考虑使用迭代的方式来优化性能。
- 错误处理: 可以添加更完善的错误处理机制，例如当括号不匹配时抛出异常。
- 灵活性: BracketTree 类可以很容易地扩展以支持不同的括号类型。
总而言之，使用括号树是一种处理嵌套括号结构的强大方法。它比正则表达式更灵活，并且可以处理括号不平衡的情况。通过自定义遍历和过滤机制，可以轻松地提取括号内的特定内容。这种方法适用于需要处理复杂嵌套结构的各种场景，例如代码解析、数据提取等。
