[C++] Albero Binario Che Rappresenta un Espressione

[Skull260287]

Come affrontereste questo esercizio e come arrivereste alla scrittura del codice. Vi pongo questa domanda perchè sono agli inizi nel trattare gli alberi e gradirei sentire la "voce" di qualche esperto:

Sia assegnato un albero binario B nelle cui foglie vi siano i valori numerici e nei restanti nodi vi siano i simboli degli operatori + - * /. Si scriva un programma che elabori il valore dell'espressione ricavata dalla lettura "inorder" dell'albero B.


Sarebbe gradito un esempio (Mamma come sono esigente !!)


Grazie milllle a tutti

[oregon]

Alcuni riferimenti da cui, studiando, puoi prendere spunto ...

http://www.fredosaurus.com/notes-cpp...treeclass.html

http://webcourse.cs.technion.ac.il/2...-in-C++-x4.pdf

[Skull260287]

Originariamente inviato da oregon
Alcuni riferimenti da cui, studiando, puoi prendere spunto ...

http://www.fredosaurus.com/notes-cpp...treeclass.html

http://webcourse.cs.technion.ac.il/2...-in-C++-x4.pdf

Grazie mille, appena posso mi metterò all'opera per capire anche questo.

[Vincenzo1968]

Ciao Skull,

qui:

http://www.guidealgoritmi.it/ShowArticle.aspx?ID=4

ci trovi un articolo che ho scritto sull'argomento. Puoi scaricare i sorgenti(sono in C ma è possibile adattarli facilmente al C++).

L'algoritmo più efficace è conosciuto col nome di Operator Precedence Parsing. Si tratta di un metodo di parsing che ulilizza un automa a stati finiti e una tabella di precedenza degli operatori. L'albero viene costruito in modalità bottom-up (Partendo cioè dalle foglie e arrivando, via via, alla radice).
In realtà esistono altre tecniche di parsing più efficienti; per esempio, si può utilizzare una grammatica del tipo LALR e il relativo automa, ma è molto più difficile da scrivere a mano(soprattutto la parte di costruzione della tabella. Di solito, per questo tipo di parsing, si utilizzano tool appositi come Flex e Bison).

Ciao