本文介绍了一种使用 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 类进行扩展，例如添加更多的方法来操作括号树。
- 在性能要求较高的场景下，可以考虑使用其他更高效的算法。
评论（已关闭）
评论已关闭