View Full Version : alberi binari
qualcuno sa rappresentarmi tale albero binario nei 3 attraversamenti principali ?
anticipato/simmetrico/posticipato
7
/ \
/ \
11 8
/ \ \
/ \ \
20 4 2
/ \
/ \
1 3
Quello non è un albero binario.
Quella struttura dati la ha la particolarità che un figlio sinistro di un nodo deve avere la chiave < o = a quella del padre, mentre il figlio destro la deve avere strettamente maggiore.
O meglio: se quell'albero la lo vogliamo considerare un albero binario di ricerca (cioè una struttura dati) allora non ha senso, altrimenti rimaniamo nel puro ambito algebrico. E visto che stai parlando di visite dei nodi, siamo nell'ambito "strutture dati":
In ogni caso la visita simmetrica (come da nome stesso) significa che scorri i nodi del sottoalbero sinistro, poi la radice e infine i nodi del sottoalbero destro.
Ottieni quindi la seguente visita:
1, 20, 3, 11, 4, 7, 8, 2
Analogamente la visita di un albero binario in ordine anticipato significa che elenchi prima la radice e poi i sottoalberi:
7, 11, 20, 1, 3, 4, 8, 2
Per il differito si elencano prima i sottoalberi e solo alla fine si elenca la radice:
1, 3, 20, 4, 2, 11, 8, 7
Comunque sia, quello non è un albero binario di ricerca.
ok, di ricerca lo hai aggiunto tu; ma quello sotto ora lo è, un "albero di ricerca"
cmq, il mio libro li chiama "alberi binari"
quello che mi interessa capire è se vi è un ordine specifico da seguire
ti hai scritto 1 20 3 ma si poteva anche scrivere 1 3 20 ?
20
/ \
/ \
7 24
/ \ \
/ \ \
2 11 30
/ \
/ \
1 5
No albero binario puro non è una struttura dati bensì una struttura algebrica.
Per illustratre i concetti molte volte si usano semplici "alberi binari". In realtà gli algoritmi vanno applicati su "alberi binari di ricerca" altrimenti quelli basati sulle chiavi di un nodo (per esempio inserzione di un nodo e cancellazione) non funzionano. Nel tuo caso le cose funzionano lo stesso perchè l'algoritmo ricorsivo di visita non usa le chiavi dei nodi.
L'ordine è quello. Non può essere modificato. In una visita di un albero, la sequenza di nodi visitabili è unica. Pertanto se due alberi binari sono uguali, la sequenza di nodi visitata è identica.
1, 3, 20, ..., non è uguale a 1, 20, 3, ...,
Originariamente inviato da misterx
cmq, il mio libro li chiama "alberi binari"
Che libro hai?
Originariamente inviato da mjordan
L'ordine è quello. Non può essere modificato.
Ma nn c'era la possibilità(ho letto ieri sul mio Sedgewick) di swappare i nodi(però li lo diceva se si doveva inserire un dato maggiore del padre di un BST, per nn costruirne uno identico tranne che x il padre)???
/\/\@®¢Ø
12-01-2004, 08:35
Originariamente inviato da mjordan
Quello non è un albero binario.
Quella struttura dati la ha la particolarità che un figlio sinistro di un nodo deve avere la chiave < o = a quella del padre, mentre il figlio destro la deve avere strettamente maggiore.
O meglio: se quell'albero la lo vogliamo considerare un albero binario di ricerca (cioè una struttura dati) allora non ha senso, altrimenti rimaniamo nel puro ambito algebrico. E visto che stai parlando di visite dei nodi, siamo nell'ambito "strutture dati":
Mah, mi sembra che sia un albero binario a tutti gli effetti. Oltretutto non e' neanche detto che non sia nemmeno di ricerca o ordinato perche' in linea generale la funzione (<=) non e' l'unica funzione di confronto utilizzabile.
In ogni caso nell'ambito delle strutture dati gli alberi binari non vengono utilizzati solo per inserimento/ricerca di dati; l'albero di parsing di una espressione (a sole funzioni binarie) ad esempio e' un albero binario ed e' una struttura dati con le contropalle :D.
Un albero binario di ricerca è tale se e solo se la visita in ordine simmetrico restituisce la sequenza delle chiavi in modo ordinato. Altrimenti è un semplice albero binario. Anche gli alberi Red-Black oltre ad avere le loro proprietà, mantengono le proprietà degli alberi binari di ricerca, cioè le chiavi del sottoalbero sinistro sono <= di quelle del sottoalbero destro. Inoltre sebbene nessuno ti vieti di "inventare" nuove operazioni su un albero, bisogna considerare il significato "puro" dei termini. Un albero di parsing è un albero binario ma non un albero binario di ricerca. E' appunto un albero di parsing. Il fatto che la funzione "<=" non sia l'unica è sbagliato. In un nodo puoi inserire quello che vuoi ma devi avere sempre e solo una chiave che ti consenta di utilizzare confronti, altrimenti, ripeto, non è un albero di ricerca puro.
Cioè i confronti non li devi fare su quello che effettivamente vuoi memorizzare nei nodi. Le chiavi sono solo dei mezzi per manipolare le strutture e non come fanno vedere i libri, i dati su cui lavorare.
Ma lui non aveva chiesto un albero binario di ricerca...
"la visita in ordine simmetrico restituisce la sequenza delle chiavi in modo ordinato."
Dipende comunque dalla funzione di ordinamento ;)
Concordo con /\/\@®¢Ø nel dire che un albero binario generico è comunque una struttura dati...
VegetaSSJ5
12-01-2004, 19:28
allora il mio prof distingueva gli alberi binari, cioè gli alberi formati da nodi che possono avere al max 2 figli, dagli ABR ovvero alberi binari di ricerca dove <figlio_sinistro> < <padre(o radice)> < <figlio_destro>.
cmq passando alle visite dovrebbero essere così:
simmetrica:
1-20-3-11-4-7-8-2
anticipata (inorder):
7-11-20-1-3-8-2
postiipata (postorder):
1-3-20-4-11-2-8-7
se ho sbagliato (molto probabile :p) correggetemi.
diamo una definizione più rigorosa di albero binario:
un albero può dirsi binario se è vuoto oppure se la sua radice ha al massimo due nodi i quali sono a loro volta degli alberi binari.
in particolare si parla di albero binario completo se ogni nodo (escluse naturalmente le foglie) ha esattamente due figli e tutte le foglie sono allo stesso livello, quindi raggiungibili dalla radice con cammini di pari lunghezza.
in particolare possiamo notare che in un albero binario il tempo di accesso a ogni elemento è limitato dal logaritmo del numero di nodi, quindi è O(log n).
ciò rende gli alberi vantaggiosi per operazioni di inserimento/ricerca di elementi, non per niente si è parlato di alberi binari di ricerca :)
naturalmente bisogna cercare di bilanciare il più possibile gli elementi all'interno di un albero, poiché in una situazione simile a questa:
o
\
o
\
o
la ricerca di un elemento ha tempo lineare (come si usasse una lista). esistono alberi bilanciati, tra i quali gli alberi red&black e i b-alberi (questi però non sono binari).
per ora mi fermo qui :)
e volendo implementare in java tale albero ?
7
/ \
/ \
11 8
/ \ \
/ \ \
20 4 2
/ \
/ \
1 3
una piccola correzione, nell'ultima visita (quella posticipata) devi invertire 4 e 11
Originariamente inviato da cionci
Dipende comunque dalla funzione di ordinamento ;)
Scusa di che funzione di ordinamento parli?
Concordo con /\/\@®¢Ø nel dire che un albero binario generico è comunque una struttura dati...
Prima di essere una struttura dati è una struttura algebrica. Forse mi sono espresso male. Non intendevo dire che non è una struttura dati. Ho solo detto che gli algoritmi di visita classici se non è un ABR non funzionano correttamente ;)
Originariamente inviato da VegetaSSJ5
allora il mio prof distingueva gli alberi binari, cioè gli alberi formati da nodi che possono avere al max 2 figli, dagli ABR ovvero alberi binari di ricerca dove <figlio_sinistro> < <padre(o radice)> < <figlio_destro>.
Esatto. E' quello che sto facendo capire. Non possono essere scambiati per la stessa cosa.
/\/\@®¢Ø
13-01-2004, 09:58
Originariamente inviato da mjordan
Esatto. E' quello che sto facendo capire. Non possono essere scambiati per la stessa cosa.
Non per sembrare polemico (o si ? :D) ma quello che ha fatto confusione sei stato tu :p, visto che non si parlava di ABR da nessuna parte prima del tuo intervento ;)
e volendo implementare in java tale albero ? :)
7
/ \
/ \
11 8
/ \ \
/ \ \
20 4 2
/ \
/ \
1 3
recoil, hai la mail-box piena :)
Originariamente inviato da misterx
recoil, hai la mail-box piena :)
hai ragione, grazie per avermelo fatto notare :)
riguardo al tuo albero non capisco con che logica sono inseriti gli elementi
7
/ \
/ \
/ \
1 8
/ \ / \
/ \ / \
2 3 / \
11 20
Non ha + senso cosi??? IMHO
Originariamente inviato da recoil
hai ragione, grazie per avermelo fatto notare :)
riguardo al tuo albero non capisco con che logica sono inseriti gli elementi
è rappresentato così sul mio libro, ora a me interessa capire l'eventuale creazione e scansione; magari riordinandoli in ordine crescente
ho visto che con una ricorsione è possibile visitarlo tutto ma mi sfugge il meccanismo
Originariamente inviato da /\/\@®¢Ø
Non per sembrare polemico (o si ? :D) ma quello che ha fatto confusione sei stato tu :p, visto che non si parlava di ABR da nessuna parte prima del tuo intervento ;)
No la questiona l'avete fatta voi perchè se si parla di visita si parla indiscutibilmente in ABR, visto che tali algoritmi ricorsivi funzionano correttamente solo se il valore delle chiavi è giustamente posizionato (proprietà ABR) altrimenti la visita procede senza alcun rigore logico ;)
/\/\@®¢Ø
14-01-2004, 13:55
Originariamente inviato da mjordan
No la questiona l'avete fatta voi perchè se si parla di visita si parla indiscutibilmente in ABR, visto che tali algoritmi ricorsivi funzionano correttamente solo se il valore delle chiavi è giustamente posizionato (proprietà ABR) altrimenti la visita procede senza alcun rigore logico ;)
A questo punto bisogna mettersi cosa si intende per visita.
Ad esempio se ho un albero di parsing di una espressione matematica (che in generale e' un albero binario), si calcola il valore dell'espressione facendo una visita postfissa dello stesso (esempio in "pseudolinguaggio")
parse( tree )=
if tree.type == value
return value
else
// visita postfissa
x = parse( tree.left )
y = parse( tree.right )
op = tree.op
return op( x , y )
Ad esempio con l'espressione "20/4 - 7*2"
ottengo l'albero
"-"
/ \
"/" "*"
/ \ / \
20 4 7 2
in cui la visita postfissa elabora nell'ordine
20 -> 4 -> "/" -> 7 -> 2 -> "*" -> "-"
/\/\@®¢Ø
14-01-2004, 13:58
Originariamente inviato da misterx
è rappresentato così sul mio libro, ora a me interessa capire l'eventuale creazione e scansione; magari riordinandoli in ordine crescente
ho visto che con una ricorsione è possibile visitarlo tutto ma mi sfugge il meccanismo
In generale non si riordina un albero "in loco". Si preferisce tenerlo ordinato man mano che lo si costruisce. Non sono sicuro, ma penso pure che prendere gli elementi del tuo albero e farne uno nuovo ordinato non sia piu' costoso che non cercare di ordinarlo.
Originariamente inviato da /\/\@®¢Ø
A questo punto bisogna mettersi cosa si intende per visita.
Ad esempio se ho un albero di parsing di una espressione matematica (che in generale e' un albero binario), si calcola il valore dell'espressione facendo una visita postfissa dello stesso (esempio in "pseudolinguaggio")
parse( tree )=
if tree.type == value
return value
else
// visita postfissa
x = parse( tree.left )
y = parse( tree.right )
op = tree.op
return op( x , y )
Ad esempio con l'espressione "20/4 - 7*2"
ottengo l'albero
"-"
/ \
"/" "*"
/ \ / \
20 4 7 2
in cui la visita postfissa elabora nell'ordine
20 -> 4 -> "/" -> 7 -> 2 -> "*" -> "-"
Ok. E dove dovrebbe stare l'analogia con una visita in postordine? Scusami ma non la vedo... Cioè nel senso che la differenza è assai sottile. L'output di quella visita è lo stesso di una visita in postordine su un ABR. Tuttavia l'algoritmo è differente.
/\/\@®¢Ø
14-01-2004, 21:32
uff che pignolo ! :D
Il senso e' che una visita (prefissa, infissa o postfissa che si voglia) non e' affatto legata agli ABR, visto che puo' essere fatta con un un generico albero binario. Che io sappia una visita in un albero non ha il solo scopo di stampare il valore, in generale serve a compiere una operazione su ogni elemento in un dato ordine. Se le operazioni che ho utilizzato non vanno bene, sostituisci loro una stampa postfissa del valore ed avrai un programma che dall'albero di parsing "prepara" l'input per una calcolatrice RPN. E' una visita postfissa, ma l'albero non e' un ABR.
ragazzi, stiamo in tema e non perdiamoci in chiecchiere da mercato :D
quello che desideravo conoscere ordine o non ordine, specifiche rispettate o meno, era come si visitano ed eventualmente si creano alberi binari
vogliamo aggiungerci di ricerca per buona pace di mjordan ?
fai finta che io lo abbia scritto e chiedo venia; così la finiamo lì :D
dunque, per entrare nel vivo dell'argomento ed essendo impossibilitato a postare codice non mio scrivo:
"ho" costruito una classe di un bellissimo albero binario con al suo interno un'altra classe che crea nodi e relativi sottoalberi sx e dx
problema
io istanzio un solo oggetto di tipo albero ma creo più volte nodi(oggetti) sx e dx, in funzione ad esempio del numero di stringhe che desidero popolino il mio bell'alberello :)
domanda
ogni volta che uso l'operatore new istanzio un nuovo oggetto (nodo sx/dx) all'interno della classe albero ma; come cavolo fanno a rimanere suddivisi e richiamabili una volta create le stringhe ?
azz, posso capire se avessi implementato all'interno della classe albero un array di stringhe ma istanziando oggetti mica l'ho capito
/\/\@®¢Ø
14-01-2004, 22:30
Originariamente inviato da misterx
ragazzi, stiamo in tema e non perdiamoci in chiecchiere da mercato :D
Chiedo perdono, ho divagato io.
quello che desideravo conoscere ordine o non ordine, specifiche rispettate o meno, era come si visitano ed eventualmente si creano alberi binari
Eh, ma intendi gli ABR o gli alberi binari normali ? :p :D
In generale si possono creare in molti modi, e dipende tipicamente da "dove arrivano" i dati. Considerando gli ABR comunque generalmente si parte dall'albero vuoto e si inseriscono man mano gli elementi.
Ti faro' un esempio con codice Java, ma visto che e' un bel po' che non lo uso, do il permesso a mjordan di cazziarmi a suo piacimento nell'eventualita' di strafalcioni :D.
Questo e' il classico esempio in cui non si puo' fare la distinzione tra chiave e valore, visto che non esiste un modo per associare un numero ad una stringa in modo univoco (cioe', esiste ma la rappresentazione e' la stringa stessa ).
Tra l'altro per questo motivo, non avra' senso "cercare una stringa per chiave", ma semplicemente controllare se l'abbiamo gia' inserita (oltre ovviamente ad inserirla e toglierla)
problema
io istanzio un solo oggetto di tipo albero ma creo più volte nodi(oggetti) sx e dx, in funzione ad esempio del numero di stringhe che desidero popolino il mio bell'alberello :)
Esatto un nodo per ogni elemento
domanda
ogni volta che uso l'operatore new istanzio un nuovo oggetto (nodo sx/dx) all'interno della classe albero ma; come cavolo fanno a rimanere suddivisi e richiamabili una volta create le stringhe ?
All'interno della classe Albero salvi un riferimento alla radice dell'albero. Da qulla radice puoi raggiungere tutti i nodi.
Originariamente inviato da misterx
io istanzio un solo oggetto di tipo albero ma creo più volte nodi(oggetti) sx e dx, in funzione ad esempio del numero di stringhe che desidero popolino il mio bell'alberello :)
domanda
ogni volta che uso l'operatore new istanzio un nuovo oggetto (nodo sx/dx) all'interno della classe albero ma; come cavolo fanno a rimanere suddivisi e richiamabili una volta create le stringhe ?
azz, posso capire se avessi implementato all'interno della classe albero un array di stringhe ma istanziando oggetti mica l'ho capito
non ho ben chiaro qual è il tuo dubbio a riguardo
la classe albero non la utilizzi da sola ma all'interno di un'altra classe nella quale creerai l'elemento radice. a quel punto, richiamando i metodi su quell'oggetto (la radice) potrai inserire elementi e cercarli
tieni conto che il new ti restituisce un nuovo oggetto che in pratica è un puntatore. insomma non sei in un caso molto diverso dalla malloc, solo che l'oggettino ha pure i propri metodi e non è una comune struct (ti faccio sti esempi presumendo che tu abbia familiarità con il c, mi pare di ricordare che ne hai).
/\/\@®¢Ø
14-01-2004, 23:02
Supponendo di avere la seguente classe
dichiarata all'interno della classe Albero
private class Nodo
{
public Nodo( String s )
{
left = null;
right = null;
data = s;
}
public Nodo left;
public Nodo right;
public String data;
}
puoi implementare le funzionalita' di inserimento/ricerca dell'albero nel
modo seguente:
private Nodo root;
public Albero()
{
root = null;
};
public void add( String s )
{
Nodo n = new Nodo(s);
root = insert(root,n);
}
public boolean search( String s )
{
return recSearch( root , s );
}
private boolean recSearch( Nodo t , String s )
{
if ( t == null )
return false;
int n = t.data.compareTo(s);
if ( n == 0 )
return true;
if ( n >= 0 )
return recSearch( t.right , s );
return recSearch( t.left , s );
}
private Nodo insert( Nodo t , Nodo n )
{
if ( t == null )
return n;
if ( t.data.compareTo( n.data ) >= 0 )
t.right = insert( t.right , n );
else
t.left = insert( t.left, n );
return t;
}
Visti i miei ricordi di Java potrei aver scambiato il <= con il >= nel confronto tra stringhe :D ma la sostanza e' quella.
L'implementazione e' tra le piu' semplici (non molto OO ad esempio) ma la piu' chiare possibili.
Originariamente inviato da recoil
non ho ben chiaro qual è il tuo dubbio a riguardo
la classe albero non la utilizzi da sola ma all'interno di un'altra classe nella quale creerai l'elemento radice. a quel punto, richiamando i metodi su quell'oggetto (la radice) potrai inserire elementi e cercarli
tieni conto che il new ti restituisce un nuovo oggetto che in pratica è un puntatore. insomma non sei in un caso molto diverso dalla malloc, solo che l'oggettino ha pure i propri metodi e non è una comune struct (ti faccio sti esempi presumendo che tu abbia familiarità con il c, mi pare di ricordare che ne hai).
stai dicendo che costruisco una sorta di rete di puntatori ?
Guarda che non era richiesta una visita in postordine...ma una visita posticipata...simmetrica ed anticipata...
//Anticipata
void visita(nodo *n)
{
if(!n) return;
elabora(n->info);
visita(n->sx);
visita(n->dx);
}
//Posticipata
void visita(nodo *n)
{
if(!n) return;
visita(n->sx);
visita(n->dx);
elabora(n->info);
}
//Simmetrica
void visita(nodo *n)
{
if(!n) return;
visita(n->sx);
elabora(n->info);
visita(n->dx);
}
Non c'è una sola visita...basta invertire il ramo che si visita per primo e cambia l'ordine di visita...
Quindi ci sono due possibili sequenze diverse per ogni albero...
Originariamente inviato da misterx
stai dicendo che costruisco una sorta di rete di puntatori ?
beh chiamiamola così
il fatto che Java nasconde i puntatori non significa che non ci sono, in effetti tu costruisci una struttura che si basa sui puntatori.
cmq puoi rappresentare un albero anche con una tabella, anche se non è forse il massimo dell'efficenza.
per un albero generico (intento non necessariamente binario) potresti avere una tabella che associa a ogni elemento il proprio padre (la radice avrebbe un valore nullo per quel campo).
per un albero binario potresti costruire una tabella in cui ad ogni elemento sono associati figlio destro e sinistro.
in alternativa ci sono implementazioni che prevedono il concetto di fratelli...
insomma te ne ho enumerate un po' tanto per dirti che non è necessario focalizzarsi su una sola implementazione anche se quella con i puntatori (che fa uso di memoria dinamica) è nella maggior parte dei casi la più efficente per rappresentare gli alberi.
in ogni caso mi pare che sia più semplice capire questo genere di implementazione in un linguaggio che fa uso esplicito di puntatori. in effetti uno dei primi dubbi che hanno i programmatori c quando passano a Java è: "come faccio a utilizzare le strutture dati dinamiche?"
voi che avete studiato gli alberi, perchè non spiegate i vari tipi di albero che esistono e sopratutto per ciascuno di essi il loro uso tipico?
Così anche i "dilettanti" possono capire :)
Molto graditi link a tutorials sul web
Originariamente inviato da verloc
voi che avete studiato gli alberi, perchè non spiegate i vari tipi di albero che esistono e sopratutto per ciascuno di essi il loro uso tipico?
Così anche i "dilettanti" possono capire :)
Molto graditi link a tutorials sul web
ci vorrebbe una bella guida sulle strutture dati, magari divisa in parti teoriche e applicazioni pratiche in modo da coinvolgere più linguaggi.
io al momento non ho molto tempo ma tra un paio di settimane dovrei riuscire a fare qualcosa se siete interessati ;)
si siamo interessati grazie :D
e qual'è la regola per scrivere un'espressione in notazione postfissa ?
cioè in notazione polacca se non dico cavolate :)
3 * 5 + (12 - 9) : 8 * 42 - (3 + 25)
grazie 1000 :);)
prima i 2 operandi e poi l'operatore
2+5:
2 Enter
5 Enter
+ Enter
ps.Sperem che non aggio detto na' str...
/\/\@®¢Ø
03-02-2004, 16:09
Originariamente inviato da misterx
e qual'è la regola per scrivere un'espressione in notazione postfissa ?
cioè in notazione polacca se non dico cavolate :)
3 * 5 + (12 - 9) : 8 * 42 - (3 + 25)
grazie 1000 :);)
Quella di cui parli dovrebbe essere la polacca inverna
(RPN: Reverse Polish Notation), quella diretta dovrebbe avere l'operatore per primo
L'espressione che hai scritto diventa
3 5 * 12 9 - 8 : 42 * + 3 25 + -
Il metodo piu' semplice per trovarla e' scriversi l'albero dalla notazione infissa e poi fare una visita in postordine
Originariamente inviato da /\/\@®¢Ø
Quella di cui parli dovrebbe essere la polacca inverna
(RPN: Reverse Polish Notation), quella diretta dovrebbe avere l'operatore per primo
L'espressione che hai scritto diventa
3 5 * 12 9 - 8 : 42 * + 3 25 + -
Il metodo piu' semplice per trovarla e' scriversi l'albero dalla notazione infissa e poi fare una visita in postordine
infatti è la costruzione dell'albero con una espressione il problema; so che ai nodi vanno gli operatori matematici, meglio aritmetici:) ( + - * : ) e la distribuzione del calcolo tra semialbero destro o sinistro avviene in funzione della priorità di calcolo dell'espressione; ne caso sotto abbiamo ben due priorità
ma è vero che se scrivo 3 * 5 + (12 - 9) : 8 * 42 - (3 + 25) il compilatore la trasforma in notazione postfissa prima di elaborarne il risultato ?
Originariamente inviato da /\/\@®¢Ø
Quella di cui parli dovrebbe essere la polacca inverna
(RPN: Reverse Polish Notation), quella diretta dovrebbe avere l'operatore per primo
L'espressione che hai scritto diventa
3 5 * 12 9 - 8 : 42 * + 3 25 + -
Il metodo piu' semplice per trovarla e' scriversi l'albero dalla notazione infissa e poi fare una visita in postordine
Tra l'altro è l'ordine in cui inserire quella espressione nelle mitiche calcolatrici scientifiche HP48 !!!
/\/\@®¢Ø
04-02-2004, 01:48
Originariamente inviato da misterx
infatti è la costruzione dell'albero con una espressione il problema; so che ai nodi vanno gli operatori matematici, meglio aritmetici:) ( + - * : ) e la distribuzione del calcolo tra semialbero destro o sinistro avviene in funzione della priorità di calcolo dell'espressione; ne caso sotto abbiamo ben due priorità
ma è vero che se scrivo 3 * 5 + (12 - 9) : 8 * 42 - (3 + 25) il compilatore la trasforma in notazione postfissa prima di elaborarne il risultato ?
Non e' necessario. Una volta costruito l'albero avere la notazione postfissa e' immediato (attraversamento in postordine dell'albero), ma quello e' un passo successivo. Elaborare le espressioni con operatori infissi e' decisamente piu' complicato che non per la RPN (per la quale basta una pila), sostanzialmente le tecniche sono le stesse che i compilatori usano per 'leggere' il codice sorgente e capire quello che vuole il programmatore. Domani magari faccio un paio di esempi semplici.
'notte :D
vai ...../\/\@®¢Ø ..... che ti leggo volentieri :)
esci gli esempi :D:D
/\/\@®¢Ø
04-02-2004, 23:38
ehm... attenzione: volevo scrivere una piccola introduzione per spiegare il codice ma mi e' venuto fuori un papiro ...
vabbe' se proprio non vuoi passa al post del codice :D
Quel che si fa in questi casi e' partire da una descrizione di come e' strutturata una espressione aritmetica o, piu' tecnicamente, la "grammatica del linguaggio" (delle esp. ar.).
Come e' fatta una delle nostre espressioni ?
Se ci accontentiamo di poco (:D), possiamo considerare espressioni che contengano solo numeri, in tal caso possiamo descriverle nel seguente modo
<exp> = <num>
Ovvero 'una espressione si puo' scrivere come un numero', e con <num> intendiamo una sequenza di cifre.
(Sorvoliamo per ora su alcuni aspetti come numeri negativi, o sul come si legga un numero).
Se aggiungiamo le quattro operazioni otteniamo invece:
<exp> = <num> | <num> + <num> | <num> - <num> | <num> / <num> | <num> * <num>
Dove la | non e' un simbolo terminale ma indica alternative tra regole (produzioni) diverse.Va letta "una expressione si puo' scrivere come un numero oppure come un numero seguito dal simbolo + seguito da un altro numero etc."
I nomi tra < e > sono detti simboli non-terminali, i singoli caratteri fuori invese sono i terminali.
Ma quale va scelta tra le cinque ? Informalmente, diciamo che va scelta quella "che va bene". Idealmente dovremmo scegliere delle regole tali che la scelta sia univoca.
In questo modo non possiamo pero' usare piu' di un operatore, mentre noi vogliamo usarne un numero indeterminato, e dobbiamo quindi introdurre una qualche forma di ricorsione nelle nostre definizioni:
<exp> = <num> | <exp> + <num> | <exp> - <num> | <exp> / <num> | <exp> * <num>
Per vedere se una espressione e' descritta da questa grammatica si parte da un simbolo non-terminale particolare, e si procede a sostituire un simbolo non-terminale con uno o piu' simboli (terminali e non-terminali) finche' non ci restano solo terminali.
Le regola qui sopra ad esempio dice che possiamo sostituire un <exp> con una qualsiasi delle 5 sequenze a destra dell'uguale. Ad esempio partendo da <exp> possiamo passare a <exp>'+'<num>. Sostituendo nuovamente <exp> possiamo ottenere <exp>'/'<num>+<num> e cosi' via.
Se introduciamo delle produzione per descrivere gli interi possiamo fare un esempio concreto:
<num> = <digit> | <num><digit>
<digit> = '0' | '1' | '2' | ... | '9'
L'espressione "3+4" si puo ricavare quindi con i seguenti passaggi <exp> -> <exp>+<num> -> (sostituiamo la <exp>) -> <num>+<num> -> (sostituiamo la prima <num>) -> <digit>+<num> -> 3+<num> -> 3+<digit> -> 3+4
Va notato che generalmente il riconoscimento dei numeri viene fatto a priori, e si considerano quindi non singole cifre ma i numeri nel loro complesso. Questo permette delle semplificazioni che vedremo successivamente.
Il prossimo passo e' vedere cosa centra tutto questo con gli alberi, e come fare a calcolare l'espressione, oltre che a valutarne la correttezza (chi ha detto "era ora" ? :D)
Notiamo innanzi tutto che le produzioni che abbiamo utilizzato sono strutturare in modo ben preciso: un non-terminale a sinistra dell'uguale, e un terminale a destra, eventualmente 'accompagnato' da altri non-terminali. Questo ci fornisce un modo per rappresentare le produzioni tramite nodi di un albero:
Per rappresentare la produzione <exp> -> <exp>+<num> possiamo infatti usare un nodo che abbia come chiave il simbolo '+' e come figli gli alberi che rappresentano a loro volta una <exp> e un <num>.
L'esempio 3+4 visto sopra si tradure quindi come l'albero
<exp:'+'>
/ \
<exp> <num>
| |
<num> <digit:4>
|
<digit:3>
Se ci fermiamo al livello dei <num> come detto sopra, e procedendo intuitivamente, si puo' semplificare il tutto fino a
<exp:'+'>
/ \
<num:3> <num:4>
Valutare l'espressione a questo punto e' semplice: si parte dalla radice e si valutano prima i sottorami e poi con i risultati si valuta il nodo corrente. Nell'esempio prima si valuta il valore di 3 e di 4, e poi si ritorna il valore della loro somma.
Va notato che la grammatica finora adottata, seppure perfetta per trovare gli errori, non e' precisa nel trovare l'albero. Con un paio di esempi si puo' vedere che non rispetta le precedenze tra gli operatori (ma rispetta l'associativita' a sinistra... perche' ? ;) ):
3+4*5 :
<exp> -> <exp>*<num> -> <exp>+<num>*<num> -> ...
ci porta a
<exp:*>
/ \
<exp:+> <num:5>
/ \
....
E' un errore perche se andiamo a valutare l'espressione, viene eseguita prima la somma e poi la moltiplicazione.
Si puo' introdurre la precedenza nella nostra grammatica imponendo semplicemente di "dover scegliere prima" tra + e - che tra * e / in modo che appaiano "piu' in alto" nell'albero:
<exp> = <exp> + <fact> | <exp> - <fact> | <fact>
<fact> = <fact> * <num> | <fact> / <num> | <num>
Infine una aggiunta per poter gestire le parentesi:
<exp> = <exp> + <fact> | <exp> - <fact> | <fact>
<fact> = <fact> * <term> | <fact> / <term> | <term>
<term> = ( <exp> ) | <num>
Col prossimo post faro' un esempio di come scrivere il codice per fare tutti questi passaggi.
dammi il tempo di leggerlo e capirlo; preparati alle mie domande :D
/\/\@®¢Ø
06-02-2004, 22:43
Finalmente arriva l'esempio :D
Come dicevo nel messaggio precedente, di solito si fa per prima la cosiddetta "analisi lessicale" cioe' si cercano di individuare da subito le 'parole' del linguaggio; nel nostro caso si tratta solo di ignorare la spaziatura inutile e di aggregare le cifre consecutive. Questo in linea di massima agevola il lavoro successivo e non e' neanche difficile ad implementare (non e' pero' la regola: linguaggi come il C e il C++ non la adottano). Il prodotto di questa analisi saranno quelli che vengono comunquemente chiamati tokens (gettoni) e saranno gli elementi base su cui lavorera' il parser vero e proprio. Noi dobbiamo distinguere due tipi di gettoni, ovvero le cifre e gli operatori.
In C++ possiamo tradurre questo con
enum token_type { INTEGER , OP };
struct token
{
token(char c):ttype(OP),symbol(c){}
token(int n):ttype(INTEGER),value(n){}
token_type ttype;
union
{
int value;
char symbol;
};
};
La nostra funzione 'lexer' fara' prendera in input una sequenza di caratteri e ritornera' una sequenza di tokens: (versione da bocciatura all'esame, ma comunque scrivibile in due secondi :D)
struct lexical_error
{
lexical_error(int n):pos(n){};
int pos;
};
vector<token> lexer( const string& s )
{
vector<token> result;
for ( unsigned int i=0 ; i<s.size() ; ++i )
{
static const string valid_ops = "+-*/()";
if ( isspace( s[i] ) )
{
// Spazio, ignoriamolo
continue;
}
else if ( isdigit( s[i] ) )
{
// Cifra, leggiamo un numero
int n=s[i++] -'0';
while( isdigit(s[i]) )
n = n*10 + s[i++] - '0';
--i;
result.push_back( token(n) );
}
// Quattro operazioni e parentesi
else if ( valid_ops.find( s[i] ) != string::npos )
{
result.push_back( token( s[i] ));
}
// Simbolo sconosciuto, lanciamo un'eccezione
else
throw lexical_error(i);
}
return result;
}
E l'analisi vera e propria ? Vista la struttura ricorsiva delle definizioni ad ogni non-terminale possiamo associare una funzione che prova a vedere quale delle produzioni si applica, e quando ne trova una che va bene costruisce l'albero opportuno consumando man mano i gettoni di ingresso. Ad esempio se in un dato momento ci troviamo a dover considerare una <term>
<term> = ( <exp> ) | <num>
Non faremo che controllare se il primo gettone e un token operatore ( oppre un numero. Nel primo caso chiameremo "consumeremo" il gettone, chiameremo la funzione associata ad exp e al suo ritorno verificheremo di avere una ')' e cosi' via. Nel caso il token non rientri nelle due categorie lanceremo un'eccezione.
Per semplificare il parser adottero' pero' un imbroglio e una astuzia (per ora). L'imbroglio sta nella definizione di <exp> (e <term>):
<exp> = <exp> + <fact>
Adottando la tecnica sopra esposta infatti entreremmo in un ciclo infinito, non possiamo sapere in anticipo infatti quante 'exp innestate' abbiamo. Una soluzione e' quella di "spiare in avanti" per vedere quando (se!) troviamo una +. Un'altra (sbagliata ma piu' semplice :D) e' quella di invertire l'associativita' delle operazioni e riscrivere la precedente come:
<exp> = <fact>+<exp>
Pur se cambia il significato delle espressioni adottero' quest'ultima idea per accorciare il codice.
L'astuzia sta nel notare che non occorre affatto costruirsi l'albero: se si guarda l'ordine in cui l'algoritmo costruisce l'albero e quello in cui poi viene attraversato per trovare il risultato si scopre che e' lo stesso; possiamo quindi accorpare i due e ritornare direttamente i valori. Il risultato e' il seguente:
// <exp> = <fact>+<exp> | <fact>-<exp> | <fact>
template <class It>
int exp( It& first, It last )
{
int n1 = fact( first , last );
// Potremmo avere + o - e un <exp>
if ( first->ttype == OP && first->symbol == '+' )
{
++first;
return n1 + exp(first,last);
}
else if ( first->ttype == OP && first->symbol == '-' )
{
++first;
return n1 - exp(first,last);
}
return n1;
}
// <fact> = <term>*<fact> | <term>/<fact> | <term>
template <class It>
int fact( It& first ,It last )
{
int n1 = term(first,last);
// c'e' rimasto qualcosa ... dovrebbe essere * o / e un <fact>
if ( first->ttype == OP && first->symbol == '*' )
{
++first;
return n1*fact(first,last);
}
else if ( first->ttype == OP && first->symbol == '/' )
{
++first;
int n2 = exp(first,last);
if ( n2 == 0 )
throw div_by_zero();
return n1/n2;
}
return n1;
}
// <term> = (<exp>) | <num>
template <class It>
int term( It& first , It last )
{
if ( first->ttype == OP && first->symbol == '(' )
{
++first;
int n = exp(first,last);
if ( first->ttype == OP && first->symbol == ')' )
{
++first;
return n;
}
throw err_not_closed();
}
if ( first->ttype == INTEGER )
// e' semplicemente un numero
{
It old = first++;
return old->value;
}
throw err_unexpected("<term>: expecting a ( or a number");
}
int parse( const vector<token>& v )
{
typedef vector<token>::const_iterator It;
It first=v.begin();
It last=v.end();
int n = exp( first,last );
if ( first != last )
throw err_not_empty();
return n;
}
A meno di eventuali errori ovviamente :D (sembra comunque funzionare).
Il funzionamento e' veramente semplice: si parte dal non-terminale iniziale (exp) e gli si da in pasto la lista di gettoni (tramite iteratori). Questo cerca di trovare il risultato ed aggiorna gli iteratori. Le condizioni di errore capitano quando viene gettata un'eccezione oppure viene ritornato un risultato ma non siamo arrivati alla fine dei gettoni.
lexer e parser vengono messe infine assieme nel main:
int main()
{
string s;
while(true)
{
try
{
cout << "Inserisci l'espressione" << endl;
getline( cin , s);
vector<token> v = lexer(s);
cout << "Il risultato e'" << parse(v)<<endl;
}
catch( lexical_error )
{
cout << "lexical error" << endl;
}
catch( err_unexpected e )
{
cout << "syntax error:" << e.what() << endl;
}
catch( div_by_zero )
{
cout << "divide by zero error" << endl;
}
catch( err_not_closed )
{
cout << "parenthesis error" << endl;
}
catch( err_not_empty )
{
cout << "too much data" << endl;
}
}
}
Per esempi piu' evoluti e' consigliabile utilizzare un qualche generatore di parser, se la grammatica e' un po' complessa comincia diventare un'impresa scriverselo a mano.
E' comunque un campo molto studiato, e c'e' si puo' trovare tanta teoria (su cui io ho decisamente sorvolato :D) quanta 'pratica'.
ci scommetto che sei un ometto con tutti 30+ :)
eheh, se scrivevi il codice in java :D ;)
xybercom
08-02-2004, 15:58
x /\/\@®¢Ø
quello che hai scritto è interessante, grazie; potresti però aggiungere qualche riferimento a libri/articoli o librerie ?
buemuschiato
11-02-2004, 16:06
x /\/\@®¢Ø anche io... :D
Davvero interessante quello che hai scritto...
Anche io, come xybercom, sarei interessato a un pò di bibliografia.
ciao
Originariamente inviato da xybercom
x /\/\@®¢Ø
quello che hai scritto è interessante, grazie; potresti però aggiungere qualche riferimento a libri/articoli o librerie ?
lo avrà studiato all'uni :)
fate domande così anche gli altri leggendovi possono imparare ;)
xybercom
11-02-2004, 20:10
Originariamente inviato da misterx
lo avrà studiato all'uni :)
fate domande così anche gli altri leggendovi possono imparare ;)
Che vuoi dire ? ?
/\/\@®¢Ø
13-02-2004, 23:23
Originariamente inviato da xybercom
x /\/\@®¢Ø
quello che hai scritto è interessante, grazie; potresti però aggiungere qualche riferimento a libri/articoli o librerie ?
Faccio riferimeno ai testi che ho in possesso, prendete quindi le mie indicazioni con le pinze.
Vi interessa piu' la parte teorica o pratica ?
Per la parte teorica ho trovato il libro "Theory of computing - A gentle introduction" (Kinber - Smith), molto chiaro. Fa una panoramica dei vari tipi di linguaggi (come complessita') e delle macchine astratte per implementarli. Unico neo, il prezzo tutt'altro che "gentile" (40-50 euro! :( ).
Se valutate il valore del libro in base al peso troverete piu' utile "Introduction to Automata Theory, Languages and Computation", di Hopcroft, Motwani e Ullman, che a parita di prezzo offre quasi il triplo di pagine :D. Battute a parte, e' decisamente piu' completo ma a mio giudizio anche meno chiaro nell'esposizione.
Per l'aspetto piu' pratico potete rivolgervi verso un testo che tratta di compilatori. Se volete, da qualche parte in internet dovrebbe trovarsi un PDF liberamente scaricabile dal titolo "Compilers and compiler generators"(spiacente, al momento non ricordo autore o indirizzo). A differenza degli altri due testi (di stampo universitario) non richied conoscenze teoriche particolari e fornisce inoltre diverso codice di esempio in C++ e Modula-3.
buemuschiato
14-02-2004, 00:26
/\/\@®¢Ø, grazie per i riferimenti!
xybercom
14-02-2004, 16:45
Originariamente inviato da /\/\@®¢Ø
Faccio riferimeno ai testi che ho in possesso, prendete quindi le mie indicazioni con le pinze.
...
Vi interessa piu' la parte teorica o pratica ?
Grazie.
A me interessa scrivere programmi, il che richiede ovviamente anche delle basi di teoria (purchè non sia fine a sè stessa).
Mi domandavo però se non ci siano librerie standard (non mi sembra il caso di reinventare la ruota) per ricavare l'albero rappresentante un'espressione matematica. Cercavo qualcosa di più agile rispetto al sorgente di un compilatore.
Andando un po' off-topic so che Mathematica fa questo automaticamente.
Il link al pdf penso sia questo http://www.scifac.ru.ac.za/compilers/
Originariamente inviato da xybercom
Grazie.
A me interessa scrivere programmi, il che richiede ovviamente anche delle basi di teoria (purchè non sia fine a sè stessa).
Mi domandavo però se non ci siano librerie standard (non mi sembra il caso di reinventare la ruota) per ricavare l'albero rappresentante un'espressione matematica. Cercavo qualcosa di più agile rispetto al sorgente di un compilatore.
Andando un po' off-topic so che Mathematica fa questo automaticamente.
Guarda caso interessa anche a me questa ramo :D
io non ho capito se cercate un qualcosa tipo: scrivo un'espressione e mi viene disegnato un albero binario:confused:
xybercom
14-02-2004, 18:45
Originariamente inviato da misterx
io non ho capito se cercate un qualcosa tipo: scrivo un'espressione e mi viene disegnato un albero binario:confused:
no, il problema è :
data l'espressione matematica creare l'albero (rappresentazione matematica dell'espressione)
rappresentarlo/manipolarlo poi è facile.
Un esempio con Mathematica (che non uso da un po') :
x + 2 * y <=> Plus [ x , Times[2,y] ]
Cioè il programma riconosce che si tratta di una somma con il primo addendo dato da x e il secondo dato dal prodotto di 2 per y.
Questo è il primo passo per poter valutare una funzione definita da un utente.
Es. l'utente inserisce una funzione "sin(x^2)" e il programma genera l'albero e la valuta per i valori di x desiderati.
xybercom
14-02-2004, 18:52
Io comunque ho trovato a livello di librerie:
1) fparser http://www.students.tut.fi/~warp/FunctionParser/
che è una libreria C++ che ho provato e sembra funzionare ma non mi sembra "standard"
2) libmatheval che è una libreria GNU http://www.gnu.org/software/libmatheval/
però è in C e non ho ancora avuto tempo di provarla
/\/\@®¢Ø
14-02-2004, 19:38
Originariamente inviato da xybercom
Io comunque ho trovato a livello di librerie:
1) fparser http://www.students.tut.fi/~warp/FunctionParser/
che è una libreria C++ che ho provato e sembra funzionare ma non mi sembra "standard"
2) libmatheval che è una libreria GNU http://www.gnu.org/software/libmatheval/
però è in C e non ho ancora avuto tempo di provarla
Che io sappia non esistono librerie standard per quel che serve a te. Tra l'altro mi sembra che la prima libreria calcoli direttamente il risultato... a te e' sufficiente o ti interessa anche l'albero intermedio ?
Nel secondo caso puoi comunque utilizzare un generatore di parser che ti crei l'albero... non e' molto difficile.
xybercom
14-02-2004, 21:18
Beh, a me serve essenzialmente il risultato anche se può essere utile avere anche l'albero.
x chiarire quando parlavo di librerie "standard" mi riferivo a librerie molto diffuse, con un ampia base di utilizzatori non a librerie come la STL.
Per generare un parser ci sono strumenti esterni (come accennavi) ? Quali ?
/\/\@®¢Ø
16-02-2004, 00:16
Se la libreria che hai trovato fa quel che ti serve usala senza remore, non penso che ne siano di molto utilizzate in questo ambito. In alternativa puoi usare un tool come Bison per fartene una da te. Tra l'altro la calcolatrice e' l'esempio classico per questi programmi e quindi trovi quanto materiale vuoi. Ad esempio all'indirizzo http://www.cs.ucr.edu/~lgao/bison.html ho trovato un esempio di calcolatrice per Bison. Fa solo le quattro operazioni ma se ti leggi un po' il manuale di bison capirai in fretta come aggiungerci funzioni come seno e coseno, cosi' come ritornare la struttura dati invece che il valore direttamente (utile se vuoi aggiungerci variabili).
E YACC ? http://dinosaur.compilertools.net/yacc/
/\/\@®¢Ø
16-02-2004, 00:37
Dovrebbero essere piu' o meno la stessa cosa. Yacc se non sbaglio e' l'"originale" BSD, mentre Bison l'implementazione della GNU (con aggiunte)
Originariamente inviato da recoil
diamo una definizione più rigorosa di albero binario:
un albero può dirsi binario se è vuoto oppure se la sua radice ha al massimo due nodi i quali sono a loro volta degli alberi binari.
in particolare si parla di albero binario completo se ogni nodo (escluse naturalmente le foglie) ha esattamente due figli e tutte le foglie sono allo stesso livello, quindi raggiungibili dalla radice con cammini di pari lunghezza.
in particolare possiamo notare che in un albero binario il tempo di accesso a ogni elemento è limitato dal logaritmo del numero di nodi, quindi è O(log n).
ciò rende gli alberi vantaggiosi per operazioni di inserimento/ricerca di elementi, non per niente si è parlato di alberi binari di ricerca :)
naturalmente bisogna cercare di bilanciare il più possibile gli elementi all'interno di un albero, poiché in una situazione simile a questa:
o
\
o
\
o
la ricerca di un elemento ha tempo lineare (come si usasse una lista). esistono alberi bilanciati, tra i quali gli alberi red&black e i b-alberi (questi però non sono binari).
per ora mi fermo qui :)
è arrivato il momento di aggiungere alla tua definizione, il codice in JAVA che crea un bell'albero binario di ricerca :)
Originariamente inviato da misterx
è arrivato il momento di aggiungere alla tua definizione, il codice in JAVA che crea un bell'albero binario di ricerca :)
Perchè non ci provi te ?!?!? ;) Potrebbe essere un buon modo per imparare... La definizione ce l'hai ;)
Originariamente inviato da cionci
Perchè non ci provi te ?!?!? ;) Potrebbe essere un buon modo per imparare... La definizione ce l'hai ;)
perchè io ho già il codice bello e fatto e mi spiace in quanto non l'ho scritto io :)
cmq, le chiamate ricorsive mi fanno venire il mal di testa ma ancor di più, classi definite all'interno di altre classi che.....:muro:
Originariamente inviato da misterx
cmq, le chiamate ricorsive mi fanno venire il mal di testa ma ancor di più, classi definite all'interno di altre classi che.....:muro:
Non le usare...non è fondamentale usarle ;)
Le chiamate ricorsive sicurametne ti semplificano la vita...
Originariamente inviato da cionci
Non le usare...non è fondamentale usarle ;)
Le chiamate ricorsive sicurametne ti semplificano la vita...
ma è fondamentale impararle, altrimenti gli esami non li passi :D
Originariamente inviato da misterx
ma è fondamentale impararle, altrimenti gli esami non li passi :D
Mi riferivo alle classi annidate...
Scrivile separte e poi mettile insieme ;)
Originariamente inviato da cionci
Mi riferivo alle classi annidate...
Scrivile separte e poi mettile insieme ;)
ok, ma io mi riferivo alle "connesioni interne" che si creano sino a formare un albero di ricerca.
Mi viene in mente la "struct" del "C" una cosa simile a:
struct {
.....
struct {
...........
...........
...........
} Nodo;
} Albero;
creo Albero la prima volta, poi all'interno della struttura albero, un Nodo al quale associo ad esempio un valore numerico distibuendolo a sx o dx in conformità alle specifiche degli alberi di ricerca.
Quando desidero inserire un altro dato, alloco un'altra struttura Nodo e due strutture Albero, (sx e dx) ma questa volta all'interno di un Nodo e così via.....
non è banale....
In teoria basterebbe solo una struttura nodo ;)
Originariamente inviato da cionci
In teoria basterebbe solo una struttura nodo ;)
grazie, dire così e non dire nulla non è lo stesso ???? :D
Nel senso che la struttura Albero è superflua...
struct nodo {
int dato;
nodo *sx;
nodo *dx;
};
Originariamente inviato da cionci
Nel senso che la struttura Albero è superflua...
struct nodo {
int dato;
nodo *sx;
nodo *dx;
};
purtroppo il codice che ho io prende vita da un albero
albero+nodo+alberi(sx/dx)+nodo+alberi(sx/dx) etc......
Ma te non guardare il codice che hai...
Fai una struttura simile alla mia e lavora come ha detto /\/\@®¢Ø...
Originariamente inviato da cionci
Ma te non guardare il codice che hai...
Fai una struttura simile alla mia e lavora come ha detto /\/\@®¢Ø...
cacchiarola, all'esame devo esporre con tale codice
se ognuno parla la sua lingua non ci intendiamo più :)
/\/\@®¢Ø
16-02-2004, 14:32
Originariamente inviato da misterx
purtroppo il codice che ho io prende vita da un albero
albero+nodo+alberi(sx/dx)+nodo+alberi(sx/dx) etc......
:mbe:
Puoi scriverci la definizione di nodo e alberi (mi sembra di capire che le hai gia') ? Non occorrono i metodi, solo i campi.
xybercom
16-02-2004, 20:13
Originariamente inviato da /\/\@®¢Ø
Se la libreria che hai trovato fa quel che ti serve usala senza remore, non penso che ne siano di molto utilizzate in questo ambito. In alternativa puoi usare un tool come Bison per fartene una da te. Tra l'altro la calcolatrice e' l'esempio classico per questi programmi e quindi trovi quanto materiale vuoi. Ad esempio all'indirizzo http://www.cs.ucr.edu/~lgao/bison.html ho trovato un esempio di calcolatrice per Bison. Fa solo le quattro operazioni ma se ti leggi un po' il manuale di bison capirai in fretta come aggiungerci funzioni come seno e coseno, cosi' come ritornare la struttura dati invece che il valore direttamente (utile se vuoi aggiungerci variabili).
Ok, grazie. Avevo una vaga idea che Bison (o Yacc) potesse servire allo scopo, vedrò di capire come funzionano; scusate poi se ho portato la discussione un po' off-topic.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.