Generating Tree Structure from Flat Array in JavaScript (without using object references)

I'm trying t开发者_高级运维o generate a tree structure in JavaScript from a flat array. This would usually be a fairly straightforward proposition - simply retain a 'stack' array with references to ancestor objects of the current working scope ordered by nesting depth - push a new element onto the stack when entering another nested level, and pop it off when leaving one, replacing the current working element with the object referenced by the (new) last array item.

Unfortunately this requires the capability to pass-by-reference, which JavaScript doesn't have (well, doesn't have in any meaningful way that I know how I could use for this problem.)

To give a bit of background, I'm trying to turn an arbitrarily long/complicated string containing nested XML-style (but not XML, so an XML parser can't be used instead) tokens into a structure similar to the one below:

Expected Input:

[
    "<token>",
    "<my non compliant token>",
    "some text at this level",
    "<some other token>",
    "some more text",
    "<yet another token>",
    "more text",
    "</yet another token>",
    "blah!",
    "</some other token>",
    "</token>",
    "more text"
]

Expected Output

[
    {
        "token": "<token>",
        "children": [
            {
                "token": "<my non compliant token>",
                "children": [
                    "some text at this level",
                    {
                        "token": "<some other token>",
                        "children": [
                            "some more text",
                            {
                                "token": "<yet another token>",
                                "children": [ "more text" ]
                            },
                            "blah!"
                        ]
                    }
                ]
            }
        ]
    },
    "more text"
]

To clarify - I'm not after an entire algorithm (but I'd be interested if you want to provide your implementation) - just a good method for maintaining current position in the outputted tree (or an entirely different/better way of generating tree objects!) Don't get too caught up on how the tokens work - they're not XML and for the purpose of the exercise could be formatted entirely differently.

Any input would be greatly appreciated!

Your strings look easy to parse. I think I would do something like this:

var stack = [];
var array = [];
for (var i in strings) {
   var s = strings[i];
   if (s.indexOf("</") == 0) {
      array = stack.pop();
   } else if (s.indexOf("<") == 0) {
      var obj = {token: s, children: []};
      array.push(obj);
      stack.push(array);
      array = obj.children;
   } else {
      array.push(s);
   }
}

Idea #1

Here's an answer you probably weren't anticipating.

Looking at your expect output, I was wondering if it's easiest to just generate JSON and then eval it when you're done. No references at all.

When going through your flat array, you basically have three operations:

1. You add more data to the current object
2. You close off the current object
3. You create a new child object

You can do all three of those fairly easily by just appending the appropriate text onto a JSON string you're building as you iterate through your source array to literally just generate the text you show in your expected output. When done, run that JSON string through eval. You may need a few safety checks to verify that each array and object is closed properly if there are errors in the input, but it should work fine.

Idea #2

You can still use your stack array. I'm not sure exactly why you need to pass by reference, but you can just pass an index into the array around and have everyone modify the master copy of the array that way via index. Using local functions, the master array can be a common data value that is local to your main function, but essentially global to all your sub-functions so they can all shared access to it.

This would look something like this:

function ParseRawData(rawData)
{
    var parentScopeArray = [];   // main parent scope of objects

    function processTag(x)
    {
        // you can access parentScopeArray directly here and
        // and be accessing it by reference
    }

    // other code or local functions here

}

Idea #3

If you want to pass the array into a function and have the master copy modified (perhaps the reason you're thinking of pass by reference), the javascript design pattern is to pass the array in and return a modified array, replacing the entire original array with the modified one that is returned.