Convertire la rappresentazione da stringa ad albero con le regole

Question

Devo fare un semplice parsing di testo RTF, ho bisogno di correggere un iss. Data la seguente stringa:

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

Dove:

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

In qualsiasi punto nella stringa di stato potrebbe essere influenzata da alcun carattere precedente tranne che per i caratteri nei tag chiusi. per esempio {gggg} non influenzerà ffff ma aaaaaaa} aaa .. interesserà bbbb, ccc, eee, ggg, fff e così via.

Da ciò si può dividere la sopra per solo i blocchi significativi

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

snervamento:

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

Per descrivere la dipendenza ho usato X> Y significa Y dipende X (come in X può cambiare il significato di 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 

quindi, se abbiamo poi un nodo che può avere un valore e un ordinato elenco di valori secondari. Tale che l'albero valore sarebbe simile a questa:

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

Quindi per ottenere i caratteri che influenzano qualsiasi nodo, posso solo intensificare attraverso ogni genitore in modo ricorsivo.

quello che continuo a rimanere bloccati sulla sta cercando di analizzare la stringa nella mia classe del nodo:

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

ho letto il personaggio stringhe per carattere, quando incontro un \ ho aumenta di due. Quando incontro uno {, salvi la sezione di testo precedente come valore del nodo e passo nel bambino, e quando incontro uno } faccio un passo indietro.

Ma continuo a incasinare la logica, in particolare per G e A2. È semplice da fare su carta ma quando poi provo a dover fare la logica per il down down continuo a rovinare tutto.

C'è un modo più semplice per realizzare questa struttura? (o c'è una struttura migliore che dovrei usare). Penserei che ci dovrebbe essere una libreria che permetta la conversione di stringhe sugli alberi, ma non riesco a trovarne alcuna.

Answer 1

utilizzano un approccio "macchina statale", in cui lo Stato è il nodo corrente, e una bandiera di fuga:

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

La classe Node (appena rinominato un po '):

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

Per 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 + " "); 
    } 
} 

uscita:

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

Si noti che il nodo G non è un figlio del nodo E, ma un figlio di un nodo con un valore vuoto.

Quindi ovviamente è necessario aggiungere anche la gestione degli errori.