3

I'm trying to 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!

Improve this question

2 Answers 2

Reset to default
2

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);
   }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks. Because of the use of the object property, which allows a kind of pseudo-pass-by-reference, this works for me!
1

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.

Improve this answer

6 Comments

Good ideas - thanks. I'll have a play around and let you know how it goes :)
The JSON idea seems quite easy to achieve. I do have a question about idea #2 though - how are you proposing to access a specific array index in a tree of indeterminate (possibly infinite) nesting depth? Accessing an item three levels deep would require notation like tree[0]["children"][7]["children"][2]["children"]. Short of eval-ing (ugh) or iterating (which lack of pass-by-reference makes very hard) I'm not sure how you'd achieve this.
I think my favorite is #2 which I added a little pseudo code for and exploits a useful feature in Javascript that some other languages don't offer.
Don't get me wrong - I like #2 and want to use it - I'm just not sure how ;)
I see what you're asking now. You can get to any parent node in your tree with just a series of array indexes. In the example you asked about in your previous comment it's 0,7,2. The reference to the "children" attribute is implied and always the same. So, you can save a "reference" to any spot in your data structure with an array of indexes. So, when you create a new level, you add a new index onto the end of that array (push). When you add a new item at the current level, you increment the last value in the array. When you finish a level, you pop the last value off the array.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.