解析顺序树遍历的序列化

Question

我想将字符串(顺序树遍历的序列化)解析为JSON对象(树的节点和边缘)。

问题

如何提取节点之间的边缘？

字符串表示

字符串包含节点和节点(边缘)之间的依赖关系。

前向符号将是一个简单的'>‘，空的(或反向的一个级别)符号将是一个简单的'<’字符.

示例：

'1>2>5<6<<3>4>7(<<<<)'

提取元素

为了提取元素(节点、边缘)，我使用regexp对字符串进行预处理。

var network_info = '1>2>5<6<<3>4>7(<<<<)';
var network_elements = network_info.replace(/(\(<*\))/,'').match(/<|>|[0-9]/g);

结果是

Array [ "1", ">", "2", ">", "5", "<", "6", "<", "<", "3", ">", "4", ">", "7"]

提取节点

为了提取节点，我定义了函数"getNodes“。

function getNodes(network_elements) {
    var nodes = [];
    var node_id = 1;

    for (var i = 0; i < network_elements.length; i++) {
        if(network_elements[i] != '<' && network_elements[i] != '>') {
            var node = {};
            node.id = node_id++;
            node.label = network_elements[i];
            nodes.push(node);
        }
    }
    return nodes;
}

结果是包含节点id和标签的JSON对象列表

[
{id: 1, label: '1'},
{id: 2, label: '2'},
{id: 3, label: '5'},
{id: 4, label: '6'},
...]

问题:边缘

边缘的结果应该如下所示(从和表示相应节点的id)。

[
{id: 1, from: 1, to: 2},
{id: 2, from: 2, to: 3},
{id: 3, from: 2, to: 4},
{id: 4, from: 1, to: 5},
{id: 5, from: 5, to: 6},
{id: 6, from: 6, to: 7}
]

示例伪码

var edges = [];
var edge_id = 1;
var from_node_id = 1;
var to_node_id = 2;

LOOP:

    GET from_node_id

    var edge = {};
    edge.id = edge_id++;
    edge.from = from_node_id;
    edge.to = to_node_id++;
    edges.push(edge);

树结果

字符串'1>2>5<6<<3>4>7(<<<<)‘的树如下所示

示例树

任何帮助都是非常感谢的。

非常感谢-tao

Answer 1

可以使用节点堆栈跟踪根的当前路径。推送堆栈上的初始节点。然后，当您看到>X时，从当前堆栈的顶部添加一个左边沿到节点X，并在堆栈上推送X。当您看到<...< Y时，为每个<从堆栈中弹出一个节点，然后从堆栈顶部添加一个新的右边缘到Y。

您似乎对JSON的细节没有任何问题。我会让你自己解决的。