Парсинг JSON с помощью JavaScript


Мне нужно написать код JavaScript, который будет принимать JSON строку, распарсить его, и вернуть имена наиболее глубоко вложенные свойства. Например, для этих входных данных:

var json = 
"{\
foo: {\
  bar: 'something',\
  baz: {\
    jack: 'other',\
  },\
  bob: {\
    bill: 'hello',\
    bilbo: 11,\
      baggins: {\
        fizz: 'buzz'\
        finger: 'bang'\
      }\
    }\
  }\
}";

она должна вернуться ['шипение', 'палец']. Есть несколько предостережений:

  • парсинг должно быть сделано "вручную"- т. е. я не могу использовать функцию eval или JS библиотеку для парсинга JSON с
  • значения в JSON собственность гарантированно быть строками, числами или предметами, т. е. никаких массивов

Вот что я придумал до сих пор. Основной функцией является findDeepestLeaveNodes. На данный момент код немного неэффективен, так как он имеет в два раза перебрать всю входную строку. Я хотел бы улучшить, если это возможно, а также предложения по улучшению качества кода.

var constants = {
    BLOCK_START: '{',
    BLOCK_END: '}'
};

function findDeepestLeaveNodes(json) {

    var maxNesting = getMaxNesting(json);
    var currentNestLevel = 0;
    var results = [];
    var jsonLength = json.length;

    for (var currentCharIndex = 0; currentCharIndex < jsonLength; currentCharIndex++) {
        var currentChar = json.charAt(currentCharIndex);        
        //console.log("Nesting level " + currentNestLevel + " at character '" + currentChar + "'");

        if (currentChar == constants.BLOCK_START) {

            // FIXME The following parsing is fairly fragile. It doesn't handle the possibility
            // that a '}' or ',' way occur inside a String and therefore do always close a block or
            // separate sibling JSON properties. To handle this we'd need to write a proper JSON parser.
            if (++currentNestLevel == maxNesting) {             
                // read the content of the current block
                var blockEndIndex = json.indexOf(constants.BLOCK_END, currentCharIndex);
                var currentBlock = json.substring(currentCharIndex + 1, blockEndIndex);

                // Each position in the properties array will contain a property name and it's value
                var properties = currentBlock.split(',');

                for (var i = 0; i < properties.length; i++) {
                    // parse out the property name
                    var property = properties[i];
                    var separatorPosition = properties[i].indexOf(':');
                    var propertyName = property.substring(0, separatorPosition);

                    results.push(propertyName.trim());
                }               
            }           
        } else if (currentChar == constants.BLOCK_END) {            
            --currentNestLevel;
        }                   
    }
    return results;
}

function getMaxNesting(json) {
    var jsonlength = json.length;
    var currentNestLevel = 0;
    var maxNestLevel = 0;

    for (var i = 0; i < jsonlength; i++) {
        var currentChar = json.charAt(i);

        if (currentChar == constants.BLOCK_START) {
            ++currentNestLevel;

        } else if (currentChar == constants.BLOCK_END) {            
            // update maxNestLevel if necessary
            maxNestLevel = Math.max(currentNestLevel, maxNestLevel);
            --currentNestLevel;
        }       
    }   
    return maxNestLevel;
}


Комментарии
2 ответа

Я пишу это как рекурсивный спуск парсер, так как это довольно просто:

http://en.wikipedia.org/wiki/Recursive_descent_parser

На самом деле я уже сделал это пару лет назад, когда я хотел создать нечто, что просто форматы и основные моменты в JSON немного. Если вы можете понять это, тогда вы можете изменить его под свои нужды:

<html>
<head>
<style type="text/css">
.str
{
color: green;
}

.obj
{
font-weight: bold;
}

.num
{
color: red;
}
</style>
<script language="javascript" type="text/javascript">

String.prototype.repeat = function(n) {
result = '';
for (var i = 0; i < n; i++) result += this;
return result;
}

function jsonFormater() {
this.reset = function() {
this.txt = '';
this.pos = 0;
this.result = '';
this.indent = 0;
this.classes = Array();
};

this.undoindent = function() {
this.indent -= 4;
this.nline();
};

this.doindent = function() {
this.indent += 4;
this.nline();
};

this.nline = function() {
this.result += '<br />' + '&nbsp;'.repeat(this.indent);
};

this.chClass = function(neu) {
if (this.classes.length > 0) this.result += '</span>';
this.result += '<span class="' + neu + '">';
this.classes.push(neu);
};

this.endClass = function() {
this.classes.pop();
this.result += '</span>';
if (this.classes.length > 0) this.result += '<span class="' + this.classes[this.classes.length - 1] + '">';
};

this.formatJson = function(txt) {
this.txt = txt;
this.pos = 0;
this.result = '';
while (this.pos < this.txt.length) {
if (this.txt[this.pos] == '{') this.parseObj();
else if (this.txt[this.pos] =='[') this.parseArray();
this.pos++;
}

return this.result;
}

this.parseObj = function(ende) {
if (typeof ende =='undefined') var ende = '}';
this.chClass('obj');

do {
if ((this.txt[this.pos] == '{') || (this.txt[this.pos] == '[')) this.nline();
this.result += this.txt[this.pos];
if (this.txt[this.pos] == ',') this.nline();
if ((this.txt[this.pos] == '{') || (this.txt[this.pos] == '[')) this.doindent();
this.pos++;
if (this.txt[this.pos] == '{') this.parseObj();
if (this.txt[this.pos] == '[') this.parseArray();
if (this.txt[this.pos] == '"') this.parseString();
if (/\d/.test(this.txt[this.pos])) this.parseNum();
if ((this.txt[this.pos] == '}') || (this.txt[this.pos] == ']')) this.undoindent();
} while ((this.pos < this.txt.length) && (this.txt[this.pos] != ende));

this.result += this.txt[this.pos];
this.pos++;
this.endClass();
};

this.parseArray = function() {
this.parseObj(']');
};

this.parseString = function() {
this.chClass('str');
do {
this.result += this.htmlEscape(this.txt[this.pos]);
this.pos++;
} while ((this.pos < this.txt.length) && ((this.txt[this.pos] != '"') || (this.txt[this.pos - 1] == '\\')));

this.result += this.htmlEscape(this.txt[this.pos]);
this.pos++;
this.endClass();
};

this.parseNum = function() {
this.chClass('num');
do {
this.result += this.txt[this.pos];
this.pos++;
} while ((this.pos < this.txt.length) && (/[\d\.]/.test(this.txt[this.pos])));

this.endClass();
};

this.htmlEscape = function(txt) {
return txt.replace(/&/,'&amp;').replace(/</g, '&lt;').replace(/>/g, '&gt;').replace(/"/g, '&quot;');
};

this.reset();
}

var parser = new jsonFormater();

function go(txt) {
document.getElementById('ausgabe').innerHTML = parser.formatJson(txt);
parser.reset();
}

</script>
</head>
<body onLoad="go(document.getElementById('thetextarea').value);">
<textarea id="thetextarea" rows="25" cols="70" onKeyUp="go(this.value);">[{"Dies":"Ist ein Beispiel...","mit":["Arrays","und","so"]},{"alles":"sch&ouml;n verschachtelt..."},"tippt einfach json-zeugs in dem grossen Feld.","Die Anzeige aktualisiert sich sofort...","Die Formatierungen sind als &lt;style&gt; gespeichert. Ihr k&ouml;nnt sie so beliebig &auml;ndern.",{"Zahlen":1,"sind":[1,4,55.67],"auch":"sch&ouml;n"}]</textarea>
<div id="ausgabe"></div>
</body>
</html>

3
ответ дан 26 июня 2011 в 08:06 Источник Поделиться

Я бы сделал это в два шага:


  1. Парсить JSON с

  2. Найти самый глубокий узел этого объекта.

Когда вы отделяете ваш код вроде этого, ветер с два универсальных функций вместо одной-использовать функцию, которая всегда хорошая вещь.

Я писал парсер JSON в качестве самостоятельного выполнения анонимная функция, которая возвращает объект. Это нужно инкапсулировать все вспомогательные функции, поэтому они не подвергаются за пределами функции и результаты в объект только один способ: декодировать.

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];
}
};
})();

Теперь у нас есть способ для разбора JSON, нам нужен способ, чтобы найти самый глубокий ребенок. Так я ходил и делал это рекурсивную функцию, которая возвращает глубину его детей, и 0, если оно не имеет объекта, как ребенок. Это увеличивает эту глубину для его ребенка и возвращает ребенка с максимальной глубины.

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

Я использую вспомогательную функцию этого объекта.тотип. Это замечательная функция, которую придумал Ангус Кролл на JavaScript в блоге.

Object.toType = function(obj) {
return ({}).toString.call(obj).match(/\s([a-z|A-Z]+)/)[1].toLowerCase();
}

Функция deepestObject не возвращать несколько детей, если они имеют одинаковую глубину, хотя, это может быть изменено с помощью следующей:

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];
//console.log(child)
child.depth++;
ar.push(child);
}
}
}
}

var max = [{depth: 0, children: ob}];
for (var i=0; i<ar.length;i++) {
if (ar[i].depth > max[0].depth)
max = [ar[i]];
else if (ar[i].depth == max[0].depth)
max.push(ar[i]);
}

return max;
}

Вы можете увидеть, как здесь работают: одного ребенка и нескольких детей.

2
ответ дан 26 августа 2011 в 02:08 Источник Поделиться