[C++]Espressioni algebriche

[Luc@s]

Come posso far parserare e risolvere expressioni alebriche come:

5 * (3a + 4a) + 4a * (x+1)(x-1)

Tnk

[cionci]

Esistono strumenti di parsing già pronti...anche se ora non mi ricordo il nome...

Il parsing è abbastanza semplice...
Solitamente si scorre la stringa e si costruisce un albero di derivazione....in base a questo albero valuteremo poi l'espressione...
La scansione della stringa si fa semplicemente carattere per carattere...
In una situazione come quella sono determinanti per le suddivisoni degli operatori gli spazi, le parentesi e le operazioni aritmetiche...
Quindi la prima cosa da fare è cercare un termine fra quelli riconosciuti...
Leggo un carattere: 5
Leggo un altro carattere fino a quando trovo qualsiasi carattere diverso da un numero o dal "."...

Trovo " "
L'albero è composto esclusivamente dal 5...
Cerco un operatore...

"*" è un operatore...

L'albero è composto da:

*
|-- 5
|-- parametro da trovare

Cerco un parametro...

"(" indica che l'intero albero che troverò fino alla corrispondente ")" va messo come figlio dell'operatore precedente...

Trovo 3...
Trovo a...allora a non è un numero, ma non è un operatore...sottointendo 3a come 3 * a...
Creo il sottoalbero:

*
|-- 3
|-- a

Trovo + e l'albero diventa:

+
|-- *
|   |-- 3
|   |-- a
|-- parametro da trovare

Trovo 4a e l'albero diventa:

+
|-- *
|   |-- 3
|   |-- a
|-- *
    |-- 4
    |-- a

Il tutto diventa:

*
|-- 5
|-- +
     |-- *
     |   |-- 3
     |   |-- a
     |-- *
         |-- 4
         |-- a

Capisci come a questo punto sia facile calcolare il risultato...

L'operazione di parsing si fa solitamente con una fuzione ricorsiva che costruisce i vari sottoalberi...

[Luc@s]

era + o - la soluzione che pensavo
Quindi poi alla fine mi ciappo tutto faccio le operazioni e ricompongo la string con il risultato, giusto???

Direi che è un buon esercizio per vedere se il Sedgewick(x alberi) è servito a qualcosa

Tnk cionci

[ri]

ma perchè quando studi qualcosa di nuovo non ti preoccupi di fare qualche test per vedere se hai capito?

[cionci]

L'unica cosa su cui devi stare attento è la precedenza fra gli operatori...

[Luc@s]

Originariamente inviato da ri
ma perchè quando studi qualcosa di nuovo non ti preoccupi di fare qualche test per vedere se hai capito?