c++ - 构建 JSON 对象的算法

Question

输入格式如下:-

CHAR->CHAR->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. Forest 表示不同树的所有根，对于上述情况，a 和 c 是两棵树的根。
5. 执行所有链接并更新 Nodes 和 Forest 两个数组。
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;
}

这不处理任意空格；不过，它应该很容易修复。