CODEWITHSUNDEEP
c#.netalgorithmdata-structurestree
Colonel Panic
Colonel Panic

Reputation: 137574

How to parse one line string representation of tree?

I'm given a one line string representation of a tree. The keys in the tree are ints. The keys are unique (but sparse). For example the string

2[5],3[6,12[15,16]]

Describes the tree

2
\-- 5
3
|-- 6
`-- 12
    |-- 15
    `-- 16

I'd like to parse the one line string to a ChildLookup class with a method GetChildren so that

How can I do that?

Motivation: I'm trying to unit test an algorithm written for a different class with the same API.

Upvotes: 4

Views: 668

Answers (3)

Arturo Menchaca
Arturo Menchaca

Reputation: 15982

You can write a state-machine parser to build the tree.

Start declaring a Node class like this:

public class Node
{
    public Node Parent;
    public string Value;
    public List<Node> SubNodes;
}

Then formatting the input to start from a root node:

var input = "2[5],3[6,12[15,16]]";
var tree = string.Format("root[{0}]", input);

And the parser would be something like this:

Node root = new Node { Parent = null, Value = string.Empty, SubNodes = new List<Node>() };
Node node = root;

foreach (char c in tree)
{
    switch (c)
    {
        case '[':        // Start a new node, child of the current node 
            node = new Node { Parent = node, Value = string.Empty, SubNodes = new List<Node>() };
            node.Parent.SubNodes.Add(node);
            break;
        case ',':        // Start a new node, but at the same level of the current node
            node = new Node { Parent = node.Parent, Value = string.Empty, SubNodes = new List<Node>() };
            node.Parent.SubNodes.Add(node);
            break;
        case ']':        // Back to parent of the current node
            node = node.Parent;
            break;
        default:         // Add char to current node value
            node.Value += c;
            break;
    }
}

The resulting tree is something like this:

root
 |--2
 |  |--5
 |
 |--3
    |--6
    |--12
       |--15
       |--16

Finally your ChildLookup would be like so:

var lookup = new ChildLookup(root);
...

class ChildLookup
{
    Dictionary<string, Node> nodes;

    public ChildLookup(Node node)
    {
        nodes = new Dictionary<string, Node>();
        AddNodes(node);
    }

    private void AddNodes(Node node)
    {
        nodes[node.Value] = node;
        foreach (var item in node.SubNodes)
            AddNodes(item);
    }

    public IEnumerable<string> GetChildren(string key)
    {
        if (!nodes.ContainsKey(key)) throw new KeyNotFoundException();

        return nodes[key].SubNodes.Select(c => c.Value);
    }
}

Upvotes: 0

David Eisenstat
David Eisenstat

Reputation: 65458

Here's an ersatz LR lexer/parser (in Python, but porting should be easy). Valid input is assumed.

#!/usr/bin/env python3
import re


def parse(s):
    children = {}
    stack = []
    for token in re.findall('[+-]?[0-9]+|.', s):
        if token == '[':
            stack.append(n)
        elif token == ']':
            del stack[-1]
        elif token != ',':
            n = int(token)
            children[n] = []
            if stack:
                children[stack[-1]].append(n)
    return children


>>> print(parse('2[5],3[6,12[15,16]]'))
{16: [], 2: [5], 3: [6, 12], 5: [], 6: [], 12: [15, 16], 15: []}

Upvotes: 0

gilleain
gilleain

Reputation: 641

Something like:

  1. Scan the tree for your parent key. Return null if you don't find it.
  2. From the next open bracket, you are adding to the child output list.
  3. Keep track of open/close brackets from here, as a depth of the tree.
  4. Only add to your return list when you are at the level below the parent.

Of course, you could build the entire tree, but that may be more than you need to do.

Upvotes: 1

Related Questions