Newsgroup: it.comp.lang.c
Titolo: da stringa ad espressione

Ciao a tutti!
dovrei passare via file input una funzione, cioč per fare un esempio, dovrei
scrivere "x*x + 2*x +5" su un file di testo e poi far riconoscere al
programma che si tratta di una funzione...
come si fa?
ho provato a cercare su tutorial, manuali, siti... ma non ho trovato nulla..
devo dirgli "il simbolo * č un PER, il simbolo + č un piů.."?
e per funzioni tipo tan, sin, cos, log, e^x...?

 [...]
Se ricordo bene, c'e' un esempio di programma
per una calcolatrice nel librodi Niklaus Wirth
"Algoritmi + Strutture Dati = Programmi"
( mi sembra sia questo il titolo della traduzioni in italiano,
  non ho il libro qui )
Non so se si trovi ancora, sia la traduzione,
sia l'originale in inglese....
Ma te lo consiglio senz'altro, indipendentemente dal
problema del tuo programma.
Ciao
E.

 ha scritto nel messaggio
news:sPNjb.299680$R32.9...@news2.tin.it...

Quello che devi fare un PARSER.
Non č una cosa semplice, e tutto dipende dalle espressioni che devi
riconoscere (se sono tante, diverse, complicate, ramificate, innestate,
etc.)
Comunque la logica e' quella li'.
Innanzi tutto devi decidere la sintassi delle tue espressioni e poi associ
agli elementi della sintassi dei costrutti semantici:
alla stringa "*" associ l'operazione MOLTIPLICAZIONE
alla stringa "+" associ l'ADDIZIONE
alla stringa "tan" associ il calcolo della TANGENTE
...
le stringhe che non riconosci dovrebbero essere IDENTIFICATORI (tipo "x",
"y", "pippo", etc.)
A seconda della semantica degli oggetti che compongono la tua sintassi, poi
dovrai agire di conseguenza. Mi spiego con un esempio:
se hai x * x + 2 * x + 5 non devi eseguire le operazioni, cosi' come le
leggi da sx verso dx, ma rispettando la precedenza degli operatori
aritmetici: (x * x) + (2 * x) + 5 e NON (((x * x) + 2) * x) + 5.
Se ci metti delle funzioni, tipo "tan" poi, devi sapere quanti parametri
prende quella funzione e prima di valutare la tangente, devi valorizzare i
suoi parametri.
Esempio: tan(x + 4 * x)
    vuol dire calcolare prima (x + (4 * x)) e poi calcolare la TANGENTE del
risultato.
Poi, puoi anche voler interpretare espressioni con parentesi. E qui diventa
ancora piu' dura:
Esempio: (x + 4) * ((x + x) * 2)
         in cui, l'ordine di valutazione delle sottoespressioni le decide
chi scrive l'espressione.
In questo caso devi costruirti un albero di valutazione i cui nodi interni
sono gli operatori e le cui foglie sono gli operandi:
Nell'esempio avremmo (copia e incolla in notepad, se non e' leggibile) il
seguente albero:
        *
      /   \
     +     \
   /   \    \
  x     4    *
           /   \
          +     2
        /   \
       x     x
che va valutato a partire dalle foglie (ovvero dal basso)
Insomma, il tutto dipende dal tipo di espressioni che ti serve parserizzare.
Note finali.
In letteratura scientifica, la sintassi e' definita tramite GRAMMATICHE, per
le quali č possibile costruire in modo meccanico dei parser funzionanti. Ma
non č un processo semplice, se non ne sai nulla. A anche chi l'ha studiate
in passato, adesso si rircorda ben poco... :-)
Ciao,
Ema

 etc.)
Scrivere un parser funzionante e' un problema non
troppo difficile per un programmatore abbastanza esperto,
mentre puo' diventare un piccolo inferno per il novizio.
Inoltre va anche considerato il formato nel quale
andrai a codificare l'espressione che devi poi anche
eseguire. Siccome tu queste funzioni le dovrai "interpretare"
un sacco di volte durante l'esecuzione del tuo programma
che calcola (mi sembra) minimi di funzioni in piu' variabili,
anche la fase di interpretazione dovra' essere efficiente.
Mi permetto allora di indicarti 2 strade che sono
entrambe alternative al parser "classico" e sono entrambe piu' facili
da implementare e probabilmente piu' veloci.
1) la piu' efficiente. Non scrivi l'espressione
in un file di testo, ma scrivi un vero e proprio programma
in C per la funzione, con un nome prestabilito, per
esempio
double thefunz(double *x) che memorizzerai in un file tipo funz.c
poi scrivi due programmi
Programma A: e' quello che tu invochi direttamente.
Legge alcuni valori di input che gli servono
e poi invoca il compilatore c sul file funz.c, (o su altro file
specificato da input) e lo fa linkare con il programma B che contiene
le istruzione per calcolare tutto quel che vuoi calcolare
facendo riferimento alla generica funzione thefunz().
Dopo aver ottenuto l'eseguibile lo esegue, passandogli gli
opportuni parametri.
Per esempio sotto linux tutto cio' e' facilissimo da realizzare.
Saranno si e no una manciata di linee di codice e il vantaggio
e' che  la funzione e' compilata quindi la sua valutazione e' molto 
veloce. Se e' una funzione un po' lunga da scrivere e viene
invocata un milione di volte puo' fare veramente la differenza.
Gli svantaggi sono a) che deve essere presente il compilatore,
ma per esempio sotto linux il compilatore e' sempre presente...
b) che dovendo effettuare la compilazione perde un po' di tempo,
all'inizio, che pero' viene compensato largamente se il programma
esegue molte valutazioni della funzione.
2) Se invece vuoi proprio usare un parser e quindi di fatto
interpretare una funzione scritta in una stringa allora il mio
consiglio spassionato e' di implementare una parser per la notazione
polacca inversa, che potrebbe farlo ad occhi chiusi anche un
bambino.
La notazione polacca inversa (RPN) cioe' quella delle vecchie
calcolatrici scientifiche HP, e' una notazione postfissa.
In pratica
invece di "(3+x)*(1+y)" scrivi "3 x + 1 y + *
invece di "(x+y)*sin(e^(x+7)+z)" scrivi "z 7 x + exp + sin x y + *"
puoi immaginarti che la RPN lavori su uno stack.
Ogni volta che incontri una variabile o una costante devi inserirla
in cima allo stack. Quando incontri una operazione devi combinare con
quella operazione i valori (o il valore, se e' una funzione) eliminando
gli operandi dallo stack mettendo al loro posto il risultato.
nel caso sopra eseguendo "3 x + 1 y + *"
lo stack conterrebbe nell'ordine: (ogni [] indica un double nello stack)
[]       (stack vuoto)
[3]
[3][x]
[3+x]
[3+x][1]
[3+x][1][y]
[3+x][1+y]
[(3+x)*(1+y)]
(dove ovviamente al posto di x e y ci saranno i valori double
corrispondenti).
Perche' fare un parser per la notazione RPN e' infinatamente piu'
semplice rispetto a farlo per la notazione classica ?
1) perche' non devo incasinarmi con i problemi di precedenza degli
operatori e con le parentesi: nella RPN non c'e' bisogno ne di parentesi
ne esiste il concetto di precedenza degli operatori, visto
che puoi/devi specificare esattamente in che ordine eseguire le operazioni.
2) e' molto semplice controllare se l'espressione e' sintatticamente
corretta: basta controllare che lo stack non diventi mai vuoto e che
alla fine ci rimanga un solo valore (il risultato). Nel caso
di espressioni classiche devi controllare il bilanciamento
delle parentesi, che non ci siano delle cose tipo x++++y etc.etc....
3) per "eseguire" un programma RPN basta scandirlo linearmente.
etc.etc.
Lo svantaggio e' che l'espressione in RPN e' meno leggibile (per un
umano).
Personalmente mi e' capitato un paio di volte (diversi
anni fa) di dover fare una cosa simile alla tua. In un caso ho fatto
come nel primo suggerimento, perche' appunto dovevo eseguire
la funzione un numero enorme di volte e avevo bisogno che
fosse molto veloce. Nel secondo caso ho usato la RPN per poter
fare subito delle prove ed in un secondo tempo ho scritto una
specie di piccolo traduttore che traduceva una espressione da
notazione classica "umana" a notazione RPN).
Ciao e scusate la prolissita',
g.

grazie!
ora sorge il problema successivo.. come si fa ad invocare il compilatore
all'interno di un programma c?
con l' exec?
ma con che sintassi? e che librerie incluse?
grazie grazie grazie!


Qui stiamo andando OT, in quanto la modalita' dipende probabilmente
dal sistema in cui stai lavorando e non e' probabilmente standard in C.
Esistono dei gruppi appositi dedicati
alla programmazione sotto linux o sotto windows.
Per esempio, sotto linux, ci sono dei modi piu' sofisticati,
ma uno puo' fare anche una semplice
system("gcc ciccio.c franco.c -lm -o lasagna");
o in generale system(const char *s);
che e' in stdlib.h invoca semplicemente una
shell e gli passa il comando specificato.
ciao,
g.

 in C per la funzione, con un nome prestabilito, per
Complimenti per la pensata :)
Questo lavoretto si faceva ai tempi del mitico Commodore Vic20 (dove non
c'era abbastanza ram per fare alcunchč: 3,5 Kb!!).
Qualche programma, rigorosamente in assembly 6502, modificava se stesso,
alterando il valore delle proprie locazioni di memoria; veramente
divertente...
La tua soluzione (forse non elegantissima ma interessante e soprattutto
funzionale) č la stessa cosa realizzata in C e mi ha fatto tornare indietro
con i ricordi di parecchi anni :))
Ciao,
Paolo


In effetti il Vic20 e' stato il mio primo calcolatore, anche
se da alcuni anni programmavo gia' "sulla carta" in fortran a
algol (per pura passione). Che tristezza... realizzo ora che
ho cominciato a programmare 25 anni fa quando ne avevo 14.
Fate voi i conti di quanti anni ho adesso, a me viene da piangere....
Comunque la soluzione di compilare il pezzo di programma
che contiene la funzione e' una pratica piuttosto comune
quando uno usa una libreria scientifica per il calcolo
per esempio della quadratura automatica (integrazione),
calcolo di minimi e massimi, radici etc.etc.
Di solito quello che succede e' che la libreria e'
gia' compilata e predisposta per chiamare una generica
funzione dell'utente che andra' compilata a parte e linkata.
Questi passi di solito si fanno a mano.
Quello che io suggerivo era di automatizzare anche la compilazione.
ciao,  (e grazie per avermi fatto ripensare ai pixelloni del Vic20 :-)
g.