算法构建JSON对象

Question

输入如下格式给出： -

煤焦>煤焦> CHAR - > ......任何数量的次= INTEGER

这里，CHAR - 任何代表Key的字符。 INTEGER - 表示此关系值的任何整数值。

有很多这样的序列给我们。我们必须为此制作JSON格式。

例子： -

a->b = 12 
a->b = 20 
a->c->d = 190 
a->d = 300 
a->c->e = 90 
c = 18 

输出： -

{ 
    a : { 
     b :[12, 20], 
     c : { 
      d : [190] 
      e : [90] 
     } 
     d : [300] 
    } 
    c : [18] 
} 

错案

如果任意键具有价值，它会指向任何其他键，那么它应该不可能的，例如：

a : { 
    [15], 
    d : { 
      // something here 
    } 
} 

我的算法： -

1. 我用链表数据结构建立这种模式。
2. 使用两个数组，Nodes和Forest，每个索引代表一个字符，意味着0代表a，.... 25代表z。
3. 节点包含从一个键到另一个键的所有链接，如果它结束，则它包含显示值的整数数组。
4. 森林代表了不同树木的所有根，对于上述情况，a和c是两棵树的根。
5. 执行所有链接并更新节点，并将两个森林都布置成阵列。
6. 最后在最后，遍历Forest数组，如果它真的使用这个作为根创建一棵树。

这是我的算法，但它不正确。请帮我纠正我的算法或开发新算法。

Answer 1

改为使用树。该代码是未经测试（我在赶时间），但它应该让你开始，如果你理解其中的逻辑：

class Node { 
public: 

    typedef enum { 
     Dictionary, 
     Integer 
    } Type; 

    Node(Type t, const std::string &n): type(t), name(n) {} 
    ~Node() { 
     std::unordered_map<std::string, Node *>::const_iterator it; 
     for (it = children.begin(); it != children.end(); it++) 
      delete it->second; // delete it :P 
    } 

    // lazily inserts a child if non-existent yet. Returns it. 
    Node *insert(const std::string &n, Type t, int v) { 
     Node *child = children[n]; 
     if (child == nullptr) { 
      child = new Node(t, n); 
      children[n] = child; 
     } 

     child->vals.push_back(v); 
     return child; 
    } 


    // this is supposed to de-serialize a tree in JSON format 
    void dump(int level, bool hasmore) { 
     for (int i = 0; i < level; i++) 
      std::cout << " "; 

     std::cout << "\"" << name << "\": "; 

     if (type == Node::Dictionary) { 
      std::cout << "{" << std::endl; 

      std::unordered_map<std::string, Node *>::const_iterator it; 
      std::size_t i = 0; 
      for (it = children.begin(); it != children.end(); it++) { 
       it->second->dump(level + 1, i++ + 1 < children.size()); 
      } 

      for (int i = 0; i < level; i++) 
       std::cout << " "; 
      std::cout << "}"; 
     } else { 
      std::cout << "[ "; 
      std::vector<int>::const_iterator it; 
      bool first = false; 
      for (it = vals.begin(); it != vals.end(); it++) { 
       if (first) 
        std::cout << ", "; 
       else 
        first = true; 

       std::cout << *it; 
      } 
      std::cout << " ]"; 
     } 

     if (hasmore) 
      std::cout << ","; 

     std::cout << std::endl; 
    } 

private: 

    std::unordered_map<std::string, Node *> children; // if type == Dictionary 
    std::string name; 

    Type type; 
    std::vector<int> vals; // if type == Integer 
}; 

在解析文本，假定该行会以正确的顺序（即你将不会插入到还不存在的节点中），您可以轻松地构建一个树。

int main() 
{ 
    Node root(Node::Dictionary, "root"); 
    std::string line; 

    // parse line: key path and value 
    while (std::getline(std::cin, line)) { 
     // split line into keypath and number 
     std::size_t eqsign = line.find('='); 
     std::string path = line.substr(0, eqsign); 
     std::string nums = line.substr(eqsign + 1); 
     int num = std::stoi(nums); 

     // Iterate through key path 
     Node *child = &root; 
     std::size_t n = 0, k; 

     while ((k = path.find("->", n)) != std::string::npos) { 
      std::string key = path.substr(n, k - n); 
      child = child->insert(key, Node::Dictionary, 0); 
      n = k + 2; 
      // error handling can be implemented here and in Node::insert(), DIY 
     } 

     std::string key = path.substr(n); 
     child->insert(key, Node::Integer, num); 
    } 

    // then, deserialize our data structure as JSON 
    root.dump(0, false); 
    return 0; 
} 

这不处理任意的空白;但它应该很容易修复。