本文介绍了一种使用 JavaScript 解析包含嵌套括号的字符串的通用方法，通过构建 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;
}
}构造函数:
- 接受两个参数：brackets (包含开始和结束括号的字符串，例如 '{}') 和 string (要解析的字符串)。
- 验证 brackets 参数的有效性，确保它是一个包含两个不同字符的字符串。
- 调用 parse 函数，该函数递归地解析字符串并构建树结构。
- this.root 存储解析后的树的根节点。
parse 函数:
立即学习“Java免费学习笔记（深入）”；
- 递归函数，用于解析字符串并构建树结构。
- 维护一个 children 数组，用于存储当前节点的子节点。
- 遍历字符串，当遇到开始括号时，递归调用 parse 函数来解析子树。
- 当遇到结束括号时，返回一个包含子节点、开始位置、结束位置和内容的节点对象。
- 处理括号不平衡的情况。
traverse 函数:
- 接受一个回调函数作为参数，用于遍历树的每个节点。
- 递归地遍历树，并对每个节点调用回调函数。
- 回调函数接受一个包含节点信息的对象作为参数，例如 root、parent、level、nodeId、childId、start、end 和 contents。
使用示例
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 类来解析包含嵌套括号的字符串，并使用 traverse 函数来遍历树的每个节点。 filteredTraverse 函数提供了一些示例，展示了如何使用不同的过滤器来选择要处理的节点。
代码解释:
- 创建 BracketTree 实例: 使用包含嵌套括号的字符串和括号类型创建 BracketTree 实例。
- 定义 filteredTraverse 函数: 此函数用于简化树的遍历和过滤。它接受一个标题、一个叶子节点过滤器和一个分支节点过滤器作为参数。
- 使用不同的过滤器进行遍历: 代码使用 filteredTraverse 函数和不同的过滤器来遍历树，并打印出符合条件的节点的内容。
注意事项
- BracketTree 类可以处理括号不平衡的情况，但需要根据具体需求编写相应的过滤器来处理这些情况。
- traverse 函数的回调函数可以访问节点的各种信息，例如父节点、层级、节点 ID、子节点 ID、开始位置、结束位置和内容。
- 可以根据具体需求编写不同的过滤器来选择要处理的节点。
总结
BracketTree 类提供了一种灵活且强大的方法来解析和遍历包含嵌套括号的字符串。 通过构建树状结构，可以轻松地搜索和提取所需的括号内容，而无需编写复杂的正则表达式。 这种方法特别适用于处理括号不平衡的情况，并可以根据具体需求进行定制。
