时间戳

首页 > 解决方案 > HTML字符串格式化函数算法的问题

javascript - HTML字符串格式化函数算法的问题

问题描述

我在某个地方遇到了这个问题，这很有趣。

问题：

编写一个字符串格式化函数，将数据对象转换为格式化的 VALID HTML 字符串

const data = {
  str: 'hello world',
  formatting: [
    {
      type: 'i',
      positions: [2, 4],
    },
    {
      type: 'i',
      positions: [5, 9],
    },
    {
      type: 'b',
      positions: [7, 13],
    }
  ]
}

function outputHTMLString(data) {

}

预期输出：（ 注意：它必须是有效的 HTML）

he<i>ll</i>o<i> w</i><b><i>or</i></b><b>ld</b>

我遇到的问题是，因为它必须是一个有效的 HTML，我需要打破<i/>位置 7。这非常令人困惑。在过去的 1 个小时里，我一直在试图敲打我的头。任何帮助，将不胜感激。

这是我的尝试：（不是很理想）

const data = {
    s: 'hello world',
    formatting: [{
            type: 'i',
            positions: [2, 4],
        },
        {
            type: 'i',
            positions: [5, 9],
        },
        {
            type: 'b',
            positions: [7, 13],
        }
    ]
}

function outputHTMLString(data) {
    const formMap = data.formatting.reduce((acc, elem, index) => {
        for (let p of elem.positions) {
            const e = [p, elem.type];
            acc.push(e);
        }
        return acc;
    }, []);

    formMap.sort((a, b) => {
        return a[0] - b[0];
    });

    // console.log(formMap);

    const len = data.s.length;
    let s = data.s.split('');
    let current;
    const stack = [];
    let last = ''; //i0 = <i>, i1=</i>, b0=<b>, b1=</b>

    for (let [i, arr] of formMap.entries()) {
        //   console.log(i, arr, stack);
        const index = arr[0],
            elem = arr[1],
            topStack = stack[stack.length - 1];
        if (s[index]) {


            if (stack.length) {

                if (topStack === elem) {
                    let current = s[index];
                    s[index] = '';
                    while (stack.length) {
                        s[index] += '</' + stack.pop() + '>';

                    }
                    const next = formMap[i + 1][0];
                    console.log('stack:', stack, index + 1, 'next:', next);
                    if (next > index) {
                        s[index] += '<' + formMap[i + 1][1] + '>';
                    }
                    s[index] += current;
                } else {

                    s[index] = '</' + stack.pop() + '>' + '<' + elem + '>' + '<' + topStack + '>' + (s[index] || '');
                    stack.push(elem, topStack);
                }
            } else {
                s[index] = '<' + elem + '>' + (s[index] || '');
                stack.push(elem);
            }

        } else if (index > len - 1) {
            s[len - 1] = s[len - 1] + '</' + elem + '>';
        }

    }
    console.log(s);

}

console.log(outputHTMLString(data));

标签： javascriptstringalgorithm

解决方案

我可以想到两种方法来解决这个问题。

使用树

定义一个树形数据结构来表示正在构建的 HTML 内容。每个节点都知道它在原始字符串中的start和索引。end要在索引范围内进行格式化，请查找树中与该范围重叠的所有节点。

树是“三元”的，因为除了表示格式化内容的索引start和end索引之外，每个节点都可以在这些索引的左侧和右侧拥有left内容right的子节点。

使用堆栈

对于每个格式化范围，将对插入到列表中，(start, '<tag>')然后(end, '</tag>')按每对的第一个组件排序。按顺序遍历对；当您看到打开的标签时，将标签名称推送到堆栈并写入打开的标签。当你看到一个关闭标签时，如果它的标签名称在堆栈的顶部，则将其弹出并写入关闭标签。

否则，在编写关闭标签时将堆栈中的其他标签名称弹出到临时堆栈中，直到弹出要关闭的标签名称。然后关闭它，并重新打开临时堆栈中的所有标签（以相反的顺序），同时将它们推回主堆栈。

例如，如果当前输出是he<i>ll</i>o<i> w<b>or，接下来要做的是关闭<i>标签，那么我们b从主堆栈弹出并将其推送到临时堆栈，写入输出，从主堆栈</b>弹出并写入输出，然后从临时堆栈中弹出并将其推回主堆栈，写入输出。i</i>b<b>

这是堆栈解决方案的快速实现：

function formatHTML(text, formats) {
    const boundaries = formats.map(f => ({
        tag: f.type, open: true, position: f.positions[0]
    })).concat(formats.map(f => ({
        tag: f.type, open: false, position: f.positions[1]
    }))).sort((a, b) => a.position - b.position);
    const out = [];
    const stack = [];
    var i = 0;
    for (let boundary of boundaries) {
        out.push(text.substring(i, boundary.position));
        if (boundary.open) {
            stack.push(boundary.tag);
            out.push('<', boundary.tag, '>');
        } else {
            const tmp = [];
            while (true) {
                const t = stack.pop();
                out.push('</', t, '>');
                if(t == boundary.tag) { break; }
                tmp.push(t);
            }
            while (tmp.length) {
                const t = tmp.pop();
                stack.push(t);
                out.push('<', t, '>');
            }
        }
        i = boundary.position;
    }
    out.push(text.substring(i));
    return out.join('');
}

这不是最佳的，因为当多个标签应该在同一位置打开或关闭时，它不会尝试以最小化总体所需标签数量的方式对它们进行排序。您的测试用例的输出是：

he<i>ll</i>o<i> w<b>or</b></i><b>ld</b>

推荐阅读