Convertir la representación de cadena a árbol con reglas

Question

Voy a hacer un análisis de texto RTF simple, necesito corregir un iss. Dada la siguiente cadena:

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

Dónde:

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

En cualquier punto de la cadena del estado podría verse afectada por cualquier carácter anterior, excepto para los caracteres en las etiquetas cerradas. por ejemplo, {gggg} no afectará a ffff, pero aaaaaaa} aaa .. afectará a bbbb, ccc, eee, ggg, fff y así sucesivamente.

De esto podemos dividir el anterior sólo los bloques significativos

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

Rendimiento:

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

Para describir la dependencia Solía ​​X> Y significa Y depende de X (como en X puede cambiar el significado de 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 

Así que si tenemos un nodo que puede tener un valor y un orden lista de valores sub. De tal manera que la estructura de valores se vería así:

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

luego a que los caracteres que afectan a cualquier nodo, sólo puede intensificar a través de cada padre de forma recursiva.

lo que sigo quedarse atascado en la que se trata de analizar la cadena en mi clase de nodo:

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

leí el carácter de la cadena de caracteres, cuando me encuentro con un \ que aumentará en dos. Cuando encuentro un { guardo la sección de texto anterior como el valor del nodo y paso al niño, y cuando me encuentro con un } me retiro.

Pero sigo arruinando la lógica, especialmente para G y A2. Es simple de hacer en papel, pero cuando trato de tener que hacer la lógica real para bajar, sigo arruinándolo.

¿Hay una manera más directa de hacer esta estructura? (o hay una estructura mejor que debería estar usando). Pensaría que debería haber alguna biblioteca que permita conversiones de cadenas a los árboles, pero parece que no puedo encontrar ninguna.

Answer 1

utilizan un enfoque de "máquina de estados", donde el Estado es el nodo actual, y una bandera de escape:

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 clase Node (nombre acaba de cambiar un poco):

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

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

salida:

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

Tenga en cuenta que el nodo G no es un elemento secundario del nodo E, sino un elemento secundario de un nodo con un valor vacío.

Luego, por supuesto, también tiene que agregar un poco de manejo de errores.