Newsgroup: it.comp.java
Titolo: Da stringa a struttura ad albero

Ciao a tutti, volevo sapere se c'é da qualche parte una libreria già pronta 
che trasforma una stringa in una struttura ad albero con etichette. E' una 
cosa abbastanza semplice, ma un po' noiosa (perché bisogna gestire tutta una 
serie di casi particolari nel parsing della stringa).
L'input potrebbe essere una stringa di questo tipo:
"A(B C)"
che rappresenta un albero con radice A e due figli B e C
Un caso più complesso:
"A(B C D E(F G(H(I))) J K(L M))"
Le etichette possono essere lettere dell'alfabeto (non necessariamente 
singole lettere) oppure numeri (una o più cifre, eventualmente decimali...)
L'output che vorrei è una struttura a puntatori tipo:
class Nodo {
    public Object Etichetta;
    public Nodo[] figlio;
    .....
    public Object getEtichetta() {
       return Etichetta;
    }
    public Nodo getFiglio(int i) {
       return figlio[i];
    }
}
Mi sapete indicare se c'é già qualcosa o se devo mettermi a scrivere tutto?
Grazie :-)


Se usassi xml come stringa esistono parecchi framework di
unmarshalling.

 Grazie :-)
Puoi scrivere tranquillamente tutto da te, non è troppo difficile, e
potresti imparare qualcosa di "affascinante": le macchine a stati
finiti, o anche macchine di Turing (la base dell'informatica)
Certo, nessuno ti impedisce di seguire il consiglio di pioneer, ma
secondo me se ti serve qualcosa di leggero e non troppo complesso, puoi
scriverti da solo il parser della stringa.
Prima di tutto devi definire quali sono i caratteri ammessi come
etichette e quali caratteri saranno riservati. Da quanto ho capito,
come caratteri riservati dovrai tenere le parentesi e gli spazi, tutto
il resto può essere considerato "etichetta" (se vuoi puoi inserire
un'ulteriore regola che distingue i caratteri ammessi nelle etichette,
rigettando tutti gli altri).
Ora immagina che la tua stringa sia su un nastro, e che il parser sia
una testina di lettura. La testina possiede uno "stato corrente", un
elenco di regole da seguire, e legge la tua stringa da sinistra a
destra.
Le regole potrebbero essere queste (non pretendo che lo siano, sta a te
verificarne la correttezza):
- se incontri un carattere ammesso come etichetta, memorizzalo in un
buffer di utilità interno (ByteArrayOutputStream). Prosegui con il
prossimo carattere.
- se incontri uno spazio, ma il buffer di utilità interno è vuoto, non
fare nulla. Prosegui. (potresti però pensare di lanciare un'eccezione
per errore di sintassi)
- se incontri uno spazio, prendi il contenuto del buffer e memorizzalo
come nodo nella struttura ad albero che stai compilando. Svuota il
buffer interno. Prosegui.
- se incontri una parentesi aperta, inserisci il puntatore all'albero
in uno stack interno di utilità, e prepara una nuova collection in cui
memorizzare i prossimi nodi. Prosegui.
- se incontri una parentesi chiusa, la struttura corrente è terminata.
Preleva l'ultimo elemento dallo stack interno, inserisci la struttura
corrente come ultimo nodo, e impostalo come *struttura corrente* da
compilare. Prosegui
- se incontri una parentesi chiusa, ma lo stack interno è vuoto, c'è un
errore di sintassi. Solleva un'eccezione.
- se la stringa è terminata, ma lo stack interno ha ancora qualche
puntatore, come prima: errore di sintassi, solleva un'eccezione.
Alla fine i dati che dovrai mantenere nel parser sono i seguenti:
1) un buffer in cui memorizzare i caratteri dei nodi
2) uno stack (consiglio una LinkedList) per tenere traccia dei nodi
padre
3) un puntatore a LinkedList che conterrà il "nodo corrente" che stai
compilando, e che alla fine conterrà tutta la struttura descritta dalla
stringa.
Ah, un avvertimento: la stesura finale del codice potrebbe sembrarti
molto "corposa", ma se progettato come si deve, il parser avrà una
velocità che nemmeno ti aspetti (esperienza personale, ho fatto un
parser per strutture molto più complesse senza potermi appoggiare a
XML, visto che dovevo parsificare un flusso binario)
In bocca al lupo ;)
-- 
Scientology: se la conosci la eviti, se la conosci non ti uccide...
http://xenu.com-it.net
 - 
http://xenu.freewinds.cx
 - 
http://www.xenu.net
(per rispondere personalmente leva IlDitoDalCulo)
http://www.webalice.it/ech3l0n/HastaLaVictoria.jpg
   -   Siempre!

 ..............
Ooooh, mi hai riportato indietro di 3-4 anni, esame di informatica teorica, 
macchine a stati finiti, grammatiche... Speravo di essermi liberato di 
quelle cose, che qualcuno avesse provveduto a risolvere tutti i problemi 
possibili ;-)
Farò tesoro dei tuoi suggerimenti, anche perché con buone probabilità dovrò 
davvero scrivere io il codice ex novo (la stringa da parserizzare in verità 
potrebbe essere più complessa...). Pensavo ad un'implementazione ricorsiva, 
come ricorsiva è la struttura della stringa, mentre, se ho ben capito, tu 
suggerisci uno schema iterativo (comunque ora mi stampo il messaggio e vedo 
di capirci di più...).
Quello che mi preoccupava, in fin dei conti, era l'uso di funzioni ad alto 
livello di java (ad esempio per trattare le stringhe), potenzialmente 
"pesanti" a livello computazionale (devo elaborare un dataset abbastanza 
grande...). Con C++ forse posso guadagnare un bel po' in termini di 
prestazioni, ma sono molto più familiare con java, e inoltre mi troverei a 
non poter utilizzare altre librerie. Meglio comunque trattare la stringa 
come array di caratteri, anziché come oggetto String, giusto?
Ciao, grazie