本文介绍了一种使用 JavaScript 解析嵌套括号结构，并提取特定内容的方法，该方法不依赖正则表达式，而是通过构建括号树来实现，可以有效处理括号不平衡的情况，并提供灵活的遍历和过滤机制，适用于需要处理复杂嵌套结构的场景。
在处理包含嵌套括号的字符串时，使用正则表达式可能会变得非常复杂，尤其是在括号嵌套层数较深或存在不平衡括号的情况下。本文提供了一种非正则的解决方案，通过构建一个括号树的数据结构来解析字符串，并提供灵活的遍历方法，以便提取所需的信息。
BracketTree 类
核心在于 BracketTree 类，它负责构建和管理括号树。
class BracketTree {
constructor (brackets, string) {
// ...
}
traverse (callback) {
// ...
}
}构造函数接收两个参数：
立即学习“Java免费学习笔记（深入）”；
- brackets: 一个包含两个字符的字符串，分别表示开括号和闭括号。
- string: 需要解析的字符串。
traverse 方法接收一个回调函数，用于遍历括号树的每个节点。
构建括号树
BracketTree 类的构造函数主要负责解析字符串，并构建括号树。其核心逻辑在于 parse 函数，它递归地遍历字符串，识别开括号和闭括号，并构建树的节点。
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)
};
}parse 函数返回一个对象，表示一个括号节点，包含以下属性：
- children: 子节点数组。
- start: 节点在字符串中的起始位置。
- end: 节点在字符串中的结束位置。
- opened: 是否有对应的开括号。
- closed: 是否有对应的闭括号。
- contents: 节点包含的字符串内容。
遍历括号树
traverse 方法用于遍历括号树的每个节点，并执行回调函数。
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;
}回调函数接收一个参数，包含以下属性：
- root: 括号树的根节点。
- parent: 当前节点的父节点。
- branch: 当前节点的子节点(如果当前节点是分支节点)。
- level: 当前节点的深度。
- nodeId: 当前节点的唯一标识符。
- childId: 当前节点在其父节点中的索引。
- 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 实例，然后定义了一个 filteredTraverse 函数，用于遍历括号树，并根据指定的过滤器提取内容。filteredTraverse 函数接收三个参数：
- caption: 描述过滤器的字符串。
- leafFilter: 用于过滤叶子节点的回调函数。
- branchFilter: 用于过滤分支节点的回调函数。
通过不同的过滤器，可以提取不同类型的内容，例如：
- 忽略不平衡的括号及其所有子节点。
- 忽略不平衡的括号，但包含其子节点。
- 忽略空节点。
- 只显示非空的第一个子节点。
总结
本文提供了一种非正则的解决方案，用于解析包含嵌套括号的字符串。通过构建括号树，可以有效地处理括号嵌套和不平衡的情况，并提供灵活的遍历和过滤机制，以便提取所需的信息。这种方法适用于需要处理复杂嵌套结构的场景，例如解析配置文件、代码或数据。
注意事项:
- 此方法在处理非常大的字符串时，可能会占用较多内存。
- 可以根据实际需求，对 BracketTree 类进行扩展，例如添加更多的方法来操作括号树。
- 在性能要求较高的场景下，可以考虑使用其他更高效的算法。
