PDA

Visualizza la versione completa : [C++] Utilizzo di alberi per determinare prioritÓ espressioni di un calcolo


giuseppe500
06-04-2007, 13:20
CIao,
Devo creare una rutine di calcolo di funzioni con prioritÓ di operatori e parentesi.
Ho pensato di usare un albero e mettere in ogni foglia una sottofunzione(Ad es il contenuto dellla parentesi) e il livello della foglia Ŕ la priorita' della sottofunzione.
Ora non essendo un conoscitore di alberi e grafi in c++ vi chiedo
1)come si costruisce un albero in c++
2)come popolarlo con sottofunzioni di livello successivo
3)come posso partire dalla funzioni di priorita' piu alta , eseguire il calcolo,e passare i valori eseguiti alla sottofunzione di livello subito precedente in modo da completare anche questa , passare i valori alla sottofunzione di livello subito precedente e cosi via fino alla root.
grazzie in anticipo , vi sembra un buon sistema?
grazie.

UltraBeginner
06-04-2007, 14:14
Originariamente inviato da giuseppe500
CIao,
Devo creare una rutine di calcolo di funzioni con prioritÓ di operatori e parentesi.
Ho pensato di usare un albero e mettere in ogni foglia una sottofunzione(Ad es il contenuto dellla parentesi) e il livello della foglia Ŕ la priorita' della sottofunzione.
Ora non essendo un conoscitore di alberi e grafi in c++ vi chiedo
1)come si costruisce un albero in c++
2)come popolarlo con sottofunzioni di livello successivo
3)come posso partire dalla funzioni di priorita' piu alta , eseguire il calcolo,e passare i valori eseguiti alla sottofunzione di livello subito precedente in modo da completare anche questa , passare i valori alla sottofunzione di livello subito precedente e cosi via fino alla root.
grazzie in anticipo , vi sembra un buon sistema?
grazie.

Ciao giuseppe,

ti invio un link generico che forse ti pu˛ aiutare a chiarire i concetti basilari sugli alberi

http://www.alessioluffarelli.it/guide_tutorial/desktop/alberi_binari.php
http://softzone.it/articoli/showarticle.php?articleID=10

saluti!

:ciauz: :ciauz:

giuseppe500
06-04-2007, 15:11
grazie ultra beginner , ma li avevo gia letti , tra l'atro sono i primi 2 risultati di google.
QUello che cerco Ŕ come gestire in oop spinto il calcolo di funzioni matematiche.
Gli alberi gli ho capiti.
Non so pero come
1)parsare la funzione,in modo che ogni parentesi aperta creo una sottofoglia della foglia precedente che Ŕ un oggetto funzione ad es:
(1+3+(2+4+(2*2)))

trovo la prima parentesi creo un sottonodo che contiene un oggetto funzione dove i parametri sono 1+3 (la funzione termina con la riapertura della parentesi ')'?
continuando c'Ŕ una altra parentesi aperta , quindi devo creare un sottonodo del nodo e ci inserisco una funzione con parametri 2+4.
Il problema insomma sono 1 il parsing delle parentesi e la costruzione dell'albero dove la profondita delle parentesi Ŕ la prfondita della foglia
e 2 il calcolo partendo dall ultima foglia dell albero contenente una funzione e risalire l'albero calcolando.
ciao.

giuseppe500
06-04-2007, 15:50
ho trovato su google questo

Gli operatori hanno priorita` diverse: = + - * / ^
durante il parsing raccogli le sottoespressioni dalla meno prioritaria (=)
alla piu` prioritaria (^), considerando che appena incontri una parentesi
significa che inizia una sotto espressione (sub-stringa che riparserai
in seguito ricorsivamente) che si chiude dove il numero di parentesi
trovate chiuse in seguito equivaglia il numero di quelle trovate aperte.


ma non riesco a capire come gestire le sottoespressioni e come eseguirne il parsing ricorsivamente.
grazie.

UltraBeginner
06-04-2007, 16:08
ciao giuseppe,

premetto che non l ho letto pero forse anke questa puo essere una base...

http://en.wikipedia.org/wiki/Parsing_expression_grammar

king64
06-04-2007, 21:13
Questo (http://www.programmersheaven.com/d/click.aspx?ID=F24213) Ŕ invece un esempio di parser per espressioni matematiche . E' un buon inizio da cui partire per costruire in seguito parser piu completi ed efficaci . Saluti :ciauz:

puntino
06-04-2007, 21:50
Ciao giuseppe500,

Non credo che l'uso di un albero sia l'ideale per le operazioni che tu vuoi eseguire.
A me viene in mente uno stack pi¨ che un albero.
Ti faccio notare che come vorresti eseguire tu le operazioni il tuo albero diventa una lista .
Ad ogni modo ti consiglio:

http://www.grid.unina.it/Didattica/P1/tlc0405/mat_did.htm

vedi le prove di programmazione, dove potrai metterti alla prova con gli alberi giudicare se veramente Ŕ la cosa migliore usare un albero per il tuo problema.
Ciao

Loading