[C++] Utilizzo di alberi per determinare priorità espressioni di un calcolo

[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.

[UltraBeginner]

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/guid...eri_binari.php
http://softzone.it/articoli/showarti...p?articleID=10

saluti!

[giuseppe500]

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]

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]

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]

Questo è 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

[puntino]

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/P...05/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