0
$\begingroup$

I have a long string that contains data formatted in the following way:

var str = "parent /n /t child /n /t child /n /t /t grandchild /n parent";

If you print this out you get a tree structure like directories. I am trying to figure out a way/algorithm to individually extract every parent and child and children of the aforementioned and store them in an array for each of them so that I can access them later for other useful purposes. I was thinking of using a regular expression to extract the substrings since there is some sort of pattern but I am not an expert in that field and do not know if it is worth the time. Any other ways to approach this problem or is this the best way?

Notes:

A child is always preceded with \n\t

A child's child "" "" "" \n\t\t (possibly spaces between the literals)

If the string is searched the substrings that have been searched should be stored somehow for compiling the node later.

$\endgroup$
  • 2
    $\begingroup$ I don't really understand what you're looking for. Scan the string until you reach one of the delimiters, then place whatever you just found into the tree in the appropriate place. $\endgroup$ – David Richerby Oct 10 '16 at 23:20
1
$\begingroup$

Don't use regexes. A tree is a recursively defined structure, and regexes don't do recursion (they can't match nested parens for the exact same reason).

You can easily build a tree structure by using a LIFO stack of nodes and maintaining an integer currentDepth, initially 0. For each line, pop nTabsAtStartOfLine - currentDepth - 1 nodes off the stack, create a new node, make it the child of the current top-of-stack, push it on the stack, and set currentDepth = nTabsAtStartOfLine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.