Algorithm to build JSON Object

Question

Inputs are given in below format:-

CHAR->CHAR->CHAR->......any number times = INTEGER

Here, CHAR - any character which represents Key. INTEGER - any integer value which represents value of this relation.

There are number of such sequences given to us. We have to produce JSON format for that.

Example :-

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

Output :-

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

Wrong Case

If any key has value and it going to point to any other key, then it should not possible

Example :-

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

My algorithm :-

I used Linked List data structure for building this pattern.
Use two arrays, Nodes, and Forest, every index represents one character, means 0 represents a, .... 25 represents z.
Nodes contains all the linking from one key to other, an if it end, then it contains array of integer that shows values.
Forest represents all the roots of different trees, for above case, a and c are roots for two trees.
Perform all the linkings and update Nodes, and Forest both array.
Finally at the end, iterate through Forest array and if it true create a tree using this as a root.

This is my algorithm, but it is not correct. Please help me in correcting my algorithm or developing new one.

May help if you post Forest and Node data structures and wrote the algo at least in psedo-code. — wesley.mesquita
– wesley.mesquita, Commented Jan 30, 2014 at 10:54
forest is just an Bool array, where every represents one character form a to z. and Nodes is an array of pointer to dataNode, where dataNode contains one pointer that points to another dataNode, and also contains integers(as a value). These are the data structures that I used in my algorithm. — devsda
– devsda, Commented Jan 31, 2014 at 5:43

score 3 · Accepted Answer · 2014-01-30 13:05:16Z

Use a tree instead. The code is untested (I'm in a hurry), but it should get you started if you understand the logic:

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

While parsing the text, assuming that the lines will be in the correct order (i. e. you won't be inserting into a node that does not yet exist), you can easily build a tree out of this.

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

This does not handle arbitrary whitespace; it should be easy enough to fix, though.

@user529758 CAn you please explain the linking of nodes, by using above example ? I am confused in this part.

Collectives™ on Stack Overflow

Algorithm to build JSON Object

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related