análisis de texto para crear una estructura de datos de árbol

Question

Digamos que estoy leyendo una línea de un archivo:

{Parent{{ChildA}{ChildB}}} 

Un ejemplo más complejo:

{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}} 

¿Qué es la gramática utilizada para construir un árbol .

Cualquier nombre dentro de {} paréntesis es un nodo, y si dentro de ese paréntesis hay otros nodos (paréntesis), esos nodos son hijos.

Puedo analizar el primer ejemplo específico usando un contador, pero solo para encontrar los nombres de texto de los nodos. ¿Cómo puedo analizar esto para poder determinar qué nodos son hijos el uno del otro? Parece que no puedo concentrarme en el código que usaría. Tengo la sensación de que usaría la recursión.

Cualquier ayuda o consejo sería apreciado.

Se prefiere C++.

Muchas gracias.

Answer 1

estropear la diversión con una respuesta que no se puede utilizar de todos modos si se trata de la tarea:

Una implementación mínima con Boost Espíritu Qi:

#include <boost/spirit/include/qi.hpp> 
namespace qi = boost::spirit::qi; 

typedef boost::make_recursive_variant< 
    std::vector<boost::recursive_variant_>, 
    std::string>::type ast_t; 

void dump(const ast_t&); 

// adhoc parser rule: 
static const qi::rule<std::string::iterator, ast_t()> node = 
    '{' >> *node >> '}' | +~qi::char_("{}"); 

int main() 
{ 
    std::string input = "{Parent{{ChildA{ChildC}{ChildD}}{ChildB{ChildE}{ChildF}}}}"; 
    std::string::iterator f(input.begin()), l(input.end()); 

    ast_t tree; 
    if (qi::parse(f, l, node, tree)) 
     dump(tree); 
    else 
     std::cerr << "Unparsed: " << std::string(f, l) << std::endl; 
} 

La implementación de dump es, lamentablemente, casi la cantidad equivalente de código :)

---

se imprimirá:

{ 
    Parent 
    { 
     { 
      ChildA 
      { 
       ChildC 
      } 
      { 
       ChildD 
      } 
     } 
     { 
      ChildB 
      { 
       ChildE 
      } 
      { 
       ChildF 
      } 
     } 
    } 
} 

_{Aquí es la definición de dump(const ast_t&):}

struct dump_visitor : boost::static_visitor<> 
{ 
    dump_visitor(int indent=0) : _indent(indent) {} 

    void operator()(const std::string& s) const { print(s); } 

    template <class V> 
     void operator()(const V& vec) const 
    { 
     print("{"); 
     for(typename V::const_iterator it=vec.begin(); it!=vec.end(); it++) 
      boost::apply_visitor(dump_visitor(_indent+1), *it); 
     print("}"); 
    } 

    private: 
    template <typename T> void print(const T& v) const 
     { std::cout << std::string(_indent*4, ' ') << v << std::endl; } 
    int _indent; 
}; 

void dump(const ast_t& tree) 
{ 
    boost::apply_visitor(dump_visitor(), tree); 
} 

Answer 2

Como es una tarea, supongo que tiene que implementar la solución a mano, por lo que probablemente quiera usar una Pila para guardar los datos mientras analiza la entrada.

Cada vez que veas un { creas un nuevo nodo con los datos que lo siguen, y lo presionas en la pila.

Cada vez que vea un }, saca el último nodo de la pila y lo agrega a la forma de árbol.

La otra cosa que necesitaría para este enfoque es un puntero de nodo, lo llamaremos currentNode, para que podamos hacer que la jerarquía real suceda. Para empezar, currentNode será nulo; la primera vez que se saca un nodo de la pila, coloca ese nodo en currentNode. De lo contrario, cuando muestre un valor, sabemos que tenemos ambos hijos del siguiente nodo en la pila.

Te dejaré correr con él desde allí, pero si necesitas más, estaré esperando.

Answer 3

Tendrá que hacer un seguimiento de la anidación actual. Para esto puedes usar una pila.

Cada vez que encuentre un { (seguido del nombre del nodo), sabrá que este es el comienzo de un nuevo nodo. Este nuevo nodo es un elemento secundario del nodo actual.

Cada vez que te encuentras con }, sabes que el nodo actual está terminado ahora, lo que significa que tienes que decirle a tu programa que el nodo actual ahora se cambia al padre del nodo actual.

Ejemplo:

{A{B{C}{D}{E}}{F{G}{H}}} Stack: 
^ 

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A // A is root 
^ 

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B // B is child of A 
^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, C // C is child of B 
    ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, // C has no child, C done 
    ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, D // D is child of B 
     ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, 
     ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, E // E child of B 
     ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, B, 
      ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, // B has no more children, B done 
      ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F // F child of A 
      ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, G // G child of F 
       ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, 
       ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, H 
        ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, F, 
        ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: A, 
        ^

{A{B{C}{D}{E}}{F{G}{H}}} Stack: 
        ^

DONE. 

Answer 4

Imagínese que esto es algo como esto (A pesar de que es lineal del archivo que está leyendo a partir, sólo trata de visualizar de esta manera)

{ 
Parent 
    { 
    { 
    ChildA 
     { 
     ChildC 
     } 
     { 
     ChildD 
     } 
    } 
    { 
     ChildB 
     { 
     ChildE 
     } 
     { 
     ChildF 
     } 
    } 
    } 
} 

Así ahora es más visible que cada vez que obtienes tu '{' tienes un hijo.Así que ve a ciegas y siempre que obtengas un '{' engendrar un hijo (recursivamente, pero si la línea de la que estás leyendo es demasiado larga, te sugiero que vayas por iteración) y cada vez que encuentres un '}' muevas un nivel hacia arriba (al padre).

Supongo que tendrías una función para agregar un nodo al árbol y mover tu árbol un nivel. Si eso es todo lo que tienes, entonces todo lo que tienes que hacer es juntar las piezas.

Espero que esto tenga algún sentido.

Answer 5

La gramática que tiene es relativamente simple.

Con base en sus ejemplos los nodos pueden ser declarados en una de dos maneras diferentes:

{nodename} 

que es la simple y

{nodename{childnodes}} 

que es el complejo uno

Ahora para convertir esto en una gramática más formal, primero escribimos sobre las partes que lo componen:

"{" nodename "}" 
"{" nodename "{" childnodes "}" "}" 

Entonces podemos definir la gramática (los no terminales se capitalizan)

Nodo :: = "{" Nombre de nodo "}" | "{" Nombre de nodo "{" Subelementos "}" Nombre de nodo :: = al menos una letra Subelementos :: = uno o más Nodos

La forma estándar de hacerlo girar que en un analizador (suponiendo que haya que escribir a mano, que lo hará correctamente porque es muy pequeño) es escribir un método que pueda analizar cada uno de los no terminales (lo que ve a la izquierda del signo: ==).

El único problema espinoso es que tiene que escribir la función NombreNombre para verificar si hay un "{" (en cuyo caso el nodo tiene un hijo) o un "}" (en cuyo caso no tiene un niño) después del final del nombre del nodo.

También me tomé la libertad de no anotar todas las cadenas ascii posibles como el nombre de nodo.

Answer 6

Cada vez que se encuentre "{" y luego añadir niño al padre entonces cada vez que se encuentre "}" establecer la corriente árbol para ser árbol padre.

public class Tree 
    { 
     public Tree Parent { get; set; } 
     public string Value { get; set; } 
     public List<Tree> Children { get; set; } 
    } 

    public Tree Parsing() 
    { 
     string rawString = this._rawData; 
     Tree parent = new Tree { Parent = null,Value = "",Children = new List<Tree>()}; 
     Tree child = parent; 

     foreach (char c in rawString) 
      { 
      if (c == '{') 
      { 
       child = new Tree { Parent = child, Value = string.Empty, Children = new List<Tree>() }; 
       child.Parent.Children.Add(child); 
      } 
      else if (c == '}') 
      { 
       child = new Tree { Parent = child.Parent.Parent, Value = string.Empty, Children = new List<Tree>() }; 
       if (child.Parent != null) 
       { 
        child.Parent.Children.Add(child); 
       } 
       } 
      else 
      { 
        child.Value += c; 
      } 
     } 

      return parent; 
} 

public void RenderTree(Tree tree, string level) 
{ 
    if (tree.Value.Length > 0) 
     Console.WriteLine(level + tree.Value); 

    foreach (Tree t in tree.Children) 
    { 
     RenderTree(t, level + " "); 
    } 
}