输入格式如下:-
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
}
}
我的算法:-
- 我使用链表数据结构来构建这个模式。
- 使用两个数组,Nodes和Forest,每个索引代表一个字符,即0代表a,.... 25代表z。
- 节点包含从一个键到另一个键的所有链接,如果它结束,则它包含显示值的整数数组。
- Forest 表示不同树的所有根,对于上述情况,
a
和c
是两棵树的根。 - 执行所有链接并更新 Nodes 和 Forest 两个数组。
- 最后,遍历 Forest 数组,如果为真,则使用它作为根创建一棵树。
这是我的算法,但不正确。请帮助我纠正我的算法或开发新算法。
最佳答案
改用树。该代码未经测试(我很着急),但如果您理解逻辑,它应该可以帮助您入门:
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;
}
这不处理任意空格;不过,它应该很容易修复。
关于c++ - 构建 JSON 对象的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21454233/