I would do this in two steps:
- Parse the json
- Find the deepest node of that object.
When you separate your code like that, you wind up with two reusable functions instead of one single-use function, which is always a good thing.
I wrote the json parser as a self executing anonymous function that returns an object. What this does is encapsulate all the helper functions so they aren't exposed to outside functions and results in a object with just one method: decode
.
var JSON = (function() {
function charIsLetter(c) {
return ('A' <= c && c <= 'Z') || ('a' <= c && c <= 'z');
}
function charIsNumber(c) {
return '0' <= c && c <= '9';
}
function decodeInt(s) {
for ( //iterate through the string while it is a number
var i = 0, c = s.charAt(0);
i < s.length && charIsNumber(c);
c = s.charAt(++i)
);
//return [integer, the rest of the string]
return [parseInt(s.substring(0,i), 10), s.substring(i)];
}
function decodeString(s) {
var q = s.charAt(0), //what quotation wraps the string?
str = "";
for (var i=1;i<s.length;i++) { //iterate through the string
c = s.charAt(i);
if (c == "\\") {//if the next quotation is escaped, skip it
i++;
continue;
}
if (c == q)
return [str, s.substring(i+1)]; //return [the string, what comes after it]
str += c;
}
throw "String doesn't have closing quote ("+q+") at: " + s;
}
function decodeObject(s) {
s = s.substring(1); //remove first {
var ob = {}, key, val;
while (true) {
if (s.length == 0)
throw "Reached end of string while looking for '}'";
s = s.replace(/^\s+/m, ""); //remove excess whitespace
if (s.charAt(0) == "}")
return [ob, s.substring(1)]; //return the object and what's left over
key = decode2(s); //key = [decoded string/number/etc, string remaining]
s = key[1].substring(1); //s is now the leftovers, remove ":"
val = decode2(s); //val = [decoded string/number/etc, string remaining]
s = val[1]; //s is now the leftovers
if (s.charAt(0) == ",") //if there is a comma after the value, remove it
s = s.substring(1);
ob[key[0]] = val[0];
}
}
function decodeImproperString(s) {
for ( //iterate the string while the character is a letter
var i = 0, c = s.charAt(0);
i < s.length && charIsLetter(c);
c = s.charAt(++i)
);
return [s.substring(0,i), s.substring(i)]; //return [the string, what comes after it]
}
function decode2(s) {
s = s.replace(/^\s+/m, ""); //remove whitespace from the beginning of the string
var c = s.charAt(0);
if ('0' <= c && c <= '9') //value is a number
return decodeInt(s);
if (c == "'" || c == '"') //value is a string
return decodeString(s);
if (c == '{') //value is an object
return decodeObject(s);
if (charIsLetter(c))
return decodeImproperString(s);
throw "Unexpected character " + c + " at:" + s;
}
return {
decode: function(s) {
var result = decode2(s);
return result[0];
}
};
})();
Now that we've got a way to parse the json, we need a way to find the deepest child. The way I went about doing this is a recursive function that returns the depth of it's children, 0 if it has no object as a child. It increments this depth for it's children and returns the child with the maximum depth.
function deepestObject(ob) {
var ar = []; //array of objects and their depth
for (var key in ob) {
if (ob.hasOwnProperty(key)) {
if (Object.toType(ob[key]) == "object") {
var child = deepestObject(ob[key]);
child.depth++;
ar.push(child);
}
}
}
var max = {depth: 0, children: ob};
for (var i=0; i<ar.length;i++) {
if (ar[i].depth > max.depth)
max = ar[i];
}
return max;
}
I use a helper function is this, Object.toType
. This is a wonderful function thought up by Angus Croll at the Javascript Weblog.
Object.toType = function(obj) {
return ({}).toString.call(obj).match(/\s([a-z|A-Z]+)/)[1].toLowerCase();
}
The deepestObject function doesn't return multiple children if they have the same depth though, this can be changed by using the following instead:
function deepestObject(ob) {
var ar = []; //array of objects and their depth
for (var key in ob) {
if (ob.hasOwnProperty(key)) {
if (Object.toType(ob[key]) == "object") {
var children = deepestObject(ob[key]); //array of deepest children
for (var i=0;i<children.length;i++) { //for each child
var child = children[i];
child.depth++;
ar.push(child);
}
}
}
}
var max = [{depth: 0, children: ob}];
for (var i=0; i<ar.length;i++) {
if (ar[i].depth > max.depth)
max = [ar[i]];
if (ar[i].depth == max[0].depth)
max.push(ar[i]);
}
return max;
}
You can see both working here: single child and mulitple child.