Newsgroup: it.comp.lang.c++
Titolo: Parsing di espressioni matematiche

Mi servirebbe qualche consiglio su come realizzare una funzione per il
parsing di funzioni matematiche. Cioe' ad esempio di un programma che
richiede in input una stringa, l'utente digita "sen(x+2)+cos(x)" e
questo mi fa il grafico su schermo.
Non so come cominciare. Che cosa fare. Aiutatemi.
alex...@italway.it

AlexMarv wrote:

 
alex...@italway.it
 Prova ad usare un generatore di parser, come Bison, Yacc (da unire
comunque ad un analizzatore lessicale, come il Flex). Questi programmi,
che puoi reperire in siti che contengano anche l'FTP (mi viene in mente
in questo momento 
ftp://x2ftp.oulu.fi/pub/msdos/programming/djgpp
),
aiutano la costruzione di parser facendo il lavoro "sporco" (ovvero la
creazione delle procedure in C che sarebbero noiosissime da
implementare, soprattutto se fatte in modo degno), necessitando all'uopo
solo di una "grammatica" che descriva la sintassi e la semantica del
parser da generare.
Trovi comunque tutta la documentazione con i programmi stessi.
Se ti servono altre informazioni (attento però, io non li ho mai usati
seriamente) mandami un e-mail.
--
 Andrea Glorioso Pelliccioni
 
sa...@intercity.shiny.it
 
glor...@intercity.shiny.it

 
alex...@italway.it
1) Definisci le funzioni previste
2) Crea un parser che trasformi le equazioni in una forma interna che ti
permetta di risolverle velocemente
3) Valuta la funzione (quella tradotta) per ogni punto dell'asse x e fai
un line tra 2 punti successivi
oppure
Crea una funzione che traduca direttamente in numeri ciò che legge
---------------------
Io una cosa simile l'ho già realizzata, quindi se ti serve più aiuto
chiedi senza problemi!
-- 
-------------------
Giulio Argiolas
-------------------

Il tuo e' un classico problema di parsing che puo' essere facilmente
risolto usando strumenti come
yacc, bison, lex.  Nel libro "Unix" di Brian Kernighan (Zanichelli per
l'edizione italiana) puoi anche trovare un esempio di come viene
relaizzato un parser per espressioni matematiche usando yacc.
Se deciderai di usare questi strumenti, ti consiglio di usare bison, che
e' un'evoluzione di yacc.
C'e' pero' un problema, il g++ (compilatore c++ della GNU) non compila
il codice generato da bison perche' non vengono generati i prototipi di
funzione e perche' bison difinsce le funzioni con lo stile C K&R. Questo
problema e' facilmente superabile, infatti basta modificare il modello
che usa bison per generare il codice C e renderelo conforme allo standar
ANSI.
Ho gia' lavorato con bison usando un compilarore C++, se vuoi posso
tentare di darti una mano.
Ciao Gerardo

 
alex...@italway.it
Vi e' un'ottimo testo che spiega come usare lex e yacc (le utility unix
per scrivere parser), e' edito da O'Reilly and associates.
http://www.ora.com


alex...@italway.it
Ciao Alex.
Per risolvere il tuo problema dovresti saper gestire le strutture dati
ad albero binario. Sai cosa sono? Se la risposta e' no, studiale,
altrimenti non puoi realizzare un programma che calcoli funzioni che
inserisci da input. Se la risposta e' si invece devi trasformare la
stringa in una sequenza di simboli (token) di diverso genere (numeri,
operatori binari, operatori unari, parentesi). Per fare cio' devi
costruire un analizzatore lessicale, cioe' dovresti scivere una
procedura che legge un carattere per volta fino a che non trova un
token, segnalando eventualmente gli errori presenti. Poi, una volta
costruita la lista dei simboli presenti nell'espressione, devi
trasformarla nell'"albero" dell'espressione stessa, che e' un albero
binario, essendo gli operatori al piu' binari. Nella radice poni
l'operatore e nelle foglie gli operandi. Ovviamente se l'operatore e'
unario, una delle due foglie verra' a mancare. La procedura che ti
consente di fare cio' e' di tipo ricorsivo e puoi realizzarla
implementando i seguenti passi:
1. Trova l'operatore a precedenza piu' bassa;
2. Poni nella radice l'operatore trovato;
3. Prendi tutta la parte che sta a sinistra di tale operatore(se e' un
operatore binario) e per tale parte vai al punto 1, creando con tale
sotto-espressione il sotto-albero sinistro.
4.Prendi tutta la parte che sta a destra di tale operatore e per tale
parte vai al punto 1, creando con tale sotto-espressione il
sotto-albero destro.
A questo punto puoi calcolare l'espressione con un'altra procedura
ricorsiva del tipo:
1.Se nella radice dell'epressione c'e' un numero il valore
dell'espressione e' il numero stesso;
2.Se nella radice dell'espressione c'e' una variabile il valore
dell'espressione e' il valore della variabile stessa;
3.Se nella radice dell'epressione c'e' un operatore unario il valore
dell'espr. e' l'operatore applicato al valore della soto-espressione
destra.
4.Se nella radice dell'epressione c'e' un operatore binario il valore
dell'espr. e' l'operatore applicato al valore della soto-espressione
sinistra e destra.
Se hai ben presente gli alberi binari, e la ricorsione, ti bastera'
una minima conoscenza di qualunque linguaggio per poter implementare
gli algoritmi che ti ho vagamente descritto. Altrimenti avro' solo
perso cinque minuti a ripetermi come si risolve il problema che tu hai
posto......che tra l'altro non e' banale. 
Buon lavoro.