How to parse a single-line string representation of a tree?

Question

I have been given a single line string representation of a tree. The keys in the tree are ints. The keys are unique (but sparse). For example, the line

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

Describes a tree

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

I would like to parse a single row of a row of the ChildLookup class using the GetChildren method so that

• GetChildren (2) returns [5]
• GetChildren (5) returns []
• GetChildren (3) returns [6,12]
• GetChildren (10) throws a KeyNotFoundException

How can i do this?

Motivation: I'm trying to use the unit test algorithm written for another class with the same API.

Answer 1

Sort of:

• . null, .
• .
• / , .
• , .

, , , .

Answer 2

ersatz LR lexer/parser ( Python, ). .

#!/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: []}

Answer 3

- .

Node :

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

node:

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

:

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

:

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

, ChildLookup :

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