построить JSON объект

Question

Входы приведены в формате ниже: -

характеризуе-> характеризуе-> СИМ -> ...... любое число раз = INTEGER

Здесь CHAR - любой символ, который представляет Ключ. 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. Я использовал Linked структуру данных списка для создания этого рисунка.
2. Используйте два массива, узлы и лес, каждый индекс представляет один символ, означает, что 0 представляет a, .... 25 представляет z.
3. Узлы содержат все ссылки из одной клавиши в другую, если она заканчивается, то она содержит массив целых чисел, который показывает значения.
4. Лес представляет собой все корни разных деревьев, для вышеуказанного случая, a и c являются корнями для двух деревьев.
5. Выполните все ссылки и обновите узлы и левый массив.
6. Наконец, в конце, итерации через массив леса, и если это правда, создайте дерево, используя это как корень.

Это мой алгоритм, но это неверно. Пожалуйста, помогите мне в исправлении моего алгоритма или разработке нового.

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; 
} 

Это не обрабатывает произвольные пробелы; однако его должно быть достаточно легко исправить.