Convert string to tree representation with rules

Question

I'm to do some simple RTF text parsing, I need to correct an iss. Given the following string:

{aaaaaaa\}aaaa\{aaaaa{bbbbbbbb{ccccc\{cccc}bbb{eeeee}{{gggg}ffff}bbbbbb}aaaaa}

Where:

\ means ignore next character
{ means expand
} means collapse up to parent

At any point in the string the state might be affected by any previous character except for characters in closed tags. eg {gggg} won't affect ffff but aaaaaaa}aaa.. will affect bbbb, ccc, eee, ggg, fff and so on.

From this we can split the above to just the meaningful blocks

A1 = aaaaaaa\}aaaa\{aaaaa
B1 = bbbbbbbb
C = ccccc\{cccc
B2 = bbb
E = eeeee
G = gggg
F = ffff
B3 = bbbbbb
A2 = aaaaa

Yielding:

{A1{B1{C}B2{E}{{G}F}B3}A2}

To describe the dependency I used X > Y means Y depends on X (as in X may change the meaning of Y)

A1
A1 > B1
A1 > B1 > C
A1 > B1 > B2
A1 > B1 > B2 > E
A1 > B1 > B2 > G
A1 > B1 > B2 > F
A1 > B1 > B2 > B3
A1 > B1 > B2 > A2
A1 > A2

So if we then have a node that can have a value and a ordered list of sub values. Such that the value tree would look like this:

A1
- B1
- - C
- - B2
- - - E
- - - G
- - - F
- - - B3
- A2

Then to get the characters that affect any node, I can just step up through each parent recursively.

What I keep getting stuck on is trying to parse the string into my node class:

public class myNode
{
    public myNode Parent;
    public string Value;
    public List<myNode> subNodes;
}

I read the string character by character, when I encounter a \ I increment by two. When I encounter a { I save the previous text section as the node value and step into the child, and when I encounter a } I step down.

But I keep messing up the logic, especially for G and A2. It's simple to do on paper but when I then try having to do the actual logic for step down I keep messing it up.

Is there a more straight forward way to make this structure? (or is there a better structure I should be using). I would think that there should be some library that allows conversions of strings to trees but I can't seem to find any.

Answer 1

Use a "state machine" approach, where the state is the current node, and an escape flag:

string rtf = @"{aaaaaaa\}aaaa\{aaaaa{bbbbbbbb{ccccc\{cccc}bbb{eeeee}{{gggg}ffff}bbbbbb}aaaaa}";

Node root = new Node { Parent = null, Value = "root", SubNodes = new List<Node>() };
Node node = root;
bool escape = false;
foreach (char c in rtf) {
  if (escape) {
    node.Value += c;
    escape = false;
  } else {
    switch (c) {
      case '{':
        node = new Node { Parent = node, Value = String.Empty, SubNodes = new List<Node>() };
        node.Parent.SubNodes.Add(node);
        break;
      case '}':
        node = new Node { Parent = node.Parent.Parent, Value = String.Empty, SubNodes = new List<Node>() };
        if (node.Parent != null) node.Parent.SubNodes.Add(node);
        break;
      case '\\':
        escape = true;
        break;
      default:
        node.Value += c;
        break;
    }
  }
}

PrintNode(root, String.Empty);

The Node class (just renamed a little):

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

For display:

private static void PrintNode(Node node, string level) {
  if (node.Value.Length > 0) Console.WriteLine(level + node.Value);
  foreach (Node n in node.SubNodes) {
    PrintNode(n, level + "  ");
  }
}

Output:

root
  aaaaaaa}aaaa{aaaaa
    bbbbbbbb
      ccccc{cccc
    bbb
      eeeee
        gggg
      ffff
    bbbbbb
  aaaaa

Note that the G node is not a child of the E node, but a child of a node with an empty value.

Then of course you also have to add some error handling.