JavaScript 解析嵌套括号：构建 BracketTree 实现精准匹配-js教程-PHP中文网

JavaScript 解析嵌套括号：构建 BracketTree 实现精准匹配

心靈之曲

发布： 2025-08-22 18:24:01

原创

642人浏览过

javascript 解析嵌套括号：构建 brackettree 实现精准匹配

本文介绍了一种使用 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 函数提供了一些示例，展示了如何使用不同的过滤器来选择要处理的节点。

代码解释: