analisi del testo per fare una struttura ad albero dei dati

Question

Diciamo che sto leggendo una riga da un file:

{Parent{{ChildA}{ChildB}}} 

esempio più complesso:

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

Qual è la grammatica usata per costruire un albero .

Qualsiasi nome all'interno delle parentesi {} è un nodo e se all'interno di tale parentesi ci sono altri nodi (parentesi), tali nodi sono figli.

Sono in grado di analizzare il primo esempio specifico utilizzando un contatore, ma solo per trovare i nomi di testo dei nodi. Come posso analizzare questo in modo che possa determinare quali nodi sono figli l'uno dell'altro? Non riesco a spiegarmi il codice che userò. Ho la sensazione che userò la ricorsione.

Qualsiasi aiuto o consiglio sarebbe apprezzato.

C++ è preferito.

Grazie mille.

Answer 1

rovinare il divertimento con una risposta non si può usare in ogni caso se si tratta di compiti a casa:

Un'implementazione minimo con Boost Spirito 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; 
} 

L'attuazione di dump è purtroppo quasi la quantità equivalente di codice :)

---

Si stamperà:

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

_{Ecco la definizione di 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

Dato che si tratta di compiti a casa, suppongo che si debba implementare la soluzione a mano, quindi probabilmente si vorrà utilizzare uno Stack per contenere i dati mentre si analizza l'input.

Ogni volta che si visualizza un {, si crea un nuovo nodo con i dati che lo seguono e lo si inserisce nello stack.

Ogni volta che si visualizza un }, si inserisce l'ultimo nodo fuori dallo stack e lo si aggiunge alla forma dell'albero.

L'altra cosa necessaria per questo approccio è un puntatore del nodo, lo chiameremo currentNode, in modo che possiamo fare in modo che la gerarchia attuale si verifichi. Per cominciare, currentNode sarà nullo; la prima volta che un nodo viene estratto dallo stack, lo si inserisce in currentNode. Altrimenti, quando si inserisce un valore, sappiamo che abbiamo entrambi i figli del nodo successivo nello stack.

Ti lascio correre con esso da lì, ma se hai bisogno di più sarò in attesa.

Answer 3

Dovrai tenere traccia dell'attuale annidamento. Per questo puoi usare una pila.

Ogni volta che si incontra un { (seguito dal nome del nodo), si sa che questo è l'inizio di un nuovo nodo. Questo nuovo nodo è figlio del nodo corrente.

Ogni volta che si incontra }, si sa che il nodo corrente è terminato ora, il che significa che devi dire al tuo programma che il nodo corrente è ora cambiato in genitore del nodo corrente.

Esempio:

{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

Immaginate che questo sia qualcosa di simile (anche se è lineare dal file che si sta leggendo da, basta provare a visualizzare in questo modo)

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

Così ora è più visibile che ogni volta che ottieni il tuo '{' hai un figlio.Quindi diventa cieco e ogni volta che ottieni un '{' genera un bambino (in modo ricorsivo ma se la linea da cui stai leggendo è troppo lunga allora ti suggerirei di andare per iterazione) e ogni volta che incontri un '}' muovi di un livello su (al genitore).

Suppongo che avresti avuto una funzione per aggiungere un nodo all'albero e spostando il tuo albero di un livello. Se questo è tutto ciò che hai allora tutto ciò che devi fare è mettere insieme i pezzi.

Spero che abbia senso.

Answer 5

La grammatica che possiedi è relativamente semplice.

Sulla base delle vostre esempi i nodi possono essere dichiarati in uno dei due modi diversi:

{nodename} 

che è la semplice e

{nodename{childnodes}} 

che è la complessa

Ora per trasformare questo in una grammatica più formale scriviamo prima delle parti costitutive:

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

Poi possiamo definire la grammatica (i non terminali sono capitalizzati)

Node :: = "{" Nodename "}" | "{" Nodename "{" childNodes "}" Nodename :: = almeno una lettera childNodes :: = uno o più nodi

Il metodo standard per trasformare rispetto in un parser (supponendo che hai di scrivere a mano, che come vorresti perché è così piccolo) è scrivere un metodo in grado di analizzare ciascuno dei non terminali (quello che vedi a sinistra del segno: ==).

L'unico problema spinoso è che devi scrivere la funzione Nodename per verificare se c'è un "{" (nel qual caso il nodo ha un figlio) o un "}" (nel qual caso non ha un figlio) dopo la fine del nome del nodo.

Inoltre mi sono preso la libertà di non scrivere tutte le stringhe ascii possibili come Nodename.

Answer 6

Ogni volta che vi trovate "{" quindi aggiungere bambino al genitore ogni volta che si trova "}" impostare la corrente albero da essere albero genitore.