Valutare espressioni

[Z80Fan]

• 

Per il mio computer Z80 stavo cominciando a scrivere un interprete BASIC; sono sulla buona strada, ma ho capito che non potevo andare molto avanti senza avere un valutatore di espressioni, mi spiego meglio: io gli do 2+2 e lui mi ritorna 4

Son venuto fuori con questo algoritmo, che fa uso di due stack (uno per i valori e uno per gli operatori), e ho pure una versione funzionante in C++:

Codice: [Seleziona]

1  pusha 0 in stackNum
10 legge numero n
11 se non è stato letto un numero ma un operatore (incluse le parentesi), assegna x=n e vai a 40
15 push n su stack num
20 legge operatore x (se è finita la stringa, goto 60)
30 se la precedenza di x è minore o uguale a quella dell'operatore precedente (top dello stack) (nessun operatore precedente = precedenza minima)
allora esegui operazioni precedenti finchè la priorità dell'operatore sullo stack è maggiore di x o finchè non si
incontra una parentesi aperta, in tal caso la si toglie
40 push x su stack op (tranne nel caso in cui fosse stata una parentesi chiusa)
50 se non è finita la stringa, goto 10
60 esegui le operazioni mancanti nello stack op
70 il top dello stack num è il risultato

parentesi = precedenza minima
(NOTA: il codice C++ lo ho scritto con l'idea di doverlo tradurre in Assembly successivamente)

Codice: [Seleziona]

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

#define PushNum(x) stackNum[++spNum]=(x)
#define PopNum (stackNum[spNum--])
#define PushOp(x) stackOp[++spOp]=(x)
#define PopOp (stackOp[spOp--])
#define TopOp (stackOp[spOp])
#define PrintStack(stack, sp)
cout << #stack << ": ";
for(int c=1; c<=sp; c++)
cout << stack[c] << " ";
cout << endl

// 2 + 3*5 - 1*4 +5 -7. = 11

int stackNum[100] = {0}, spNum = 0, spOp = 0;
char stackOp[100] = {0};

char input[50];
int ptrIn=0; // puntatore input

int getOpPriority(char op) {
switch(op) {
case '(':
case ')':
return 10;
case '+':
case '-':
return 20;
case '*':
case '/':
return 30;
default:
return 0;
}
}

// esegue l'operazione più in alto nello stack op con i 2 numeri più in alto nello stack Op
void doOp() {
cout << " - doOp" << endl;
int a, b, r;
char o = PopOp;
a = PopNum;
b = PopNum;
switch(o) {
case '+': r = b+a; break;
case '-': r = b-a; break;
case '*': r = b*a; break;
case '/':
if(a==0) {
cout << "Divisione per zero" << endl;
exit(0);
}
r = b/a;
break;
case '.': cout << "tentata elaborazione di "."" << endl; exit(0); break;
}
cout << "    a=" << a << ", b=" << b << ", r=" << r << ", op=" << o << endl;
PushNum(r);
}

// true se op è un operatore valido
bool isOp(char op) {
switch(op) {
case '(':
case ')':
case '+':
case '-':
case '*':
case '/':
case '.': // operatore fittizio con priorità minima
return true;
default:
return false;
}
}

// true se x è una cifra numerica
bool isNum(char x) {
if(x>='0' && x<='9')
return true;
else
return false;
}

void skipSpaces() {
while(ptrIn<50 && input[ptrIn] == ' ')
++ptrIn;
}

int main()
{
int n;
char x = 0, opPrec; // opPrec = operatore precedente
int numPar=0; // numero parentesi (incrementato quando aperta, decrementato quando chiusa)

cout << "Inserisci espressione:" << endl;

cin.getline(input, 50);

PushOp('.');
//PushNum(0);

do {
cout << "nCiclo" << endl;

skipSpaces();

opPrec = x;

//x = cin.peek();
x = input[ptrIn];

if(ptrIn>=50 || x=='') // fine stringa
goto fuori;

if( isNum(x) )
{
//cin >> n;
char *invPtr;
n = strtol(&input[ptrIn], &invPtr, 10);
ptrIn = invPtr-input;
PushNum(n);
cout << "Letto Num: " << n << endl;
}
else
{
++ptrIn;
if(x=='+' || x=='-') // se al posto di un numero ci sono + o -
{
cout << "Letto Op "" << x << "" invece di num" << endl;
// se dopo non c'è un numero o una parentesi aperta, allora sono simboli errati

skipSpaces();
char y = input[ptrIn];
cout << "  y = ""<<y<<""" << endl;

if( !isNum(y) && (y!='(') ) {
cout << "  ma dopo non c'è un numero o una parentesi aperta! Errore!" << endl;
cout << "nErrore: trovato simbolo quando ci si aspettava numero" << endl;
goto uscitaErrore;
}
// se dopo c'è un numero o una parentesi aperta, allora sono simboli di segno.
PushNum(0); // inserisco uno 0 così l'operatore ha un secondo numero su cui lavorare
// ( 0-x = -x;  0+x = +x; )
input[--ptrIn] = x; // ritorno a mettere x al suo posto (circa)
}
else if( x == ')' ) { // se trovo una parentesi chiusa, la tolgo dallo stream e vado a elaborare lo stack
goto elabora;
}
else if( (opPrec==')' && isOp(x)) || x=='(' ) // se al posto di un numero c'è un operatore, e prima avevamo una parentesi chiusa, oppure al posto del numero c'è una parentesi aperta
{
cout << "Letto Op "" << x << "" invece di num" << endl;
goto L45;
}
else
{
cout << "Carattere non valido ""<< x <<"" al posto di un numero" << endl;
goto uscitaErrore;
}
}

//cin >> x;
skipSpaces();
x = input[ptrIn++];

if( x!='' && !isOp(x) ) {
cout << """ << x << "" non è un operatore" << endl;
goto uscitaErrore;
}

cout << "Letto Op: " << x << endl;
//cout << " (Peek: "" << (char)cin.peek() << "")" << endl;

if(x=='') {
cout << " - vado fuori" << endl;
goto fuori;
}

PrintStack(stackNum, spNum);
PrintStack(stackOp, spOp);

cout << "Testo " << x << "(" << getOpPriority(x) << ") e " << TopOp << "(" << getOpPriority(TopOp) << ")" << endl;

elabora:

while( (TopOp != '(') && (getOpPriority(x) <= getOpPriority(TopOp)) )
doOp();

if((x==')') && (TopOp == '('))
PopOp;

L45:
if(x != ')')
PushOp(x);

} while(x!='');

PopOp;

fuori:

cout << "son fuori" << endl;



PrintStack(stackNum, spNum);
PrintStack(stackOp, spOp);

while(TopOp != '.'/*spOp > 1*/)
doOp();

cout << "Ris: " << PopNum << endl;
uscitaErrore:
return 0;
}
In futuro gli darò una pulitina, magari diventa utile per qualcuno

Qualche commento?

[TheKaneB]

• 

Con il tuo metodo non puoi gestire le variabili...

ad esempio 3  * x + 5 banalmente farebbe saltare in aria il tutto :-)

io avevo scritto una versione ad albero, dove ogni nodo può avere zero, uno o due figli.

i terminali, costanti e variabili, hanno zero figli
gli operatori unari (segno meno, espressione) hanno un figlio
gli operatori binari (+, -, *, /, ^) hanno 2 figli

La priorità degli operatori è definita a livello di grammatica. Prima faccio il parsing di * e /, creando i cosiddetti "fattori", i quali a loro volta sono considerati alla stregua di operatori unari, successivamente faccio il parsing di + e - e mi aspetto due "fattori" come operandi, dando in output una "espressione". Una espressione circondata da parentesi diventa a sua volta un fattore.

durante il parsing costruisco l'albero, poi valuto l'espressione ricorsivamente. L'avevo scritto tempo fa per un compilatore minimale. Il vantaggio di questo metodo è che puoi valutare le espressioni costanti durante il parsing e prima della generazione del codice.

Se trovo (e se ti serve) il libro (un pdf gratuito di qualche università americana) da cui ho studiato questa tecnica, te lo passo :-)

[Z80Fan]

• 

Si le variabili ancora non ci sono, ne sono consapevole.

Informazioni sul parsing ad albero e ricorsivo ne ho trovate parecchie in rete, ma questa mia versione ha il vantaggio di essere lineare, passa la stringa di input una volta sola, e non ha bisogno della ricorsione. Mi è utile visto anche che la devo mettere sullo Z80, e che devo fare un interprete.

Cmq grazie per l'aiuto

[cdimauro]

• 

Ne avevo realizzato uno una ventina d'anni fa in assembly 68000 per Amiga, e utilizzava un solo stack. Più o meno funzionava come il tuo.

Con un albero, come suggeriva Antonio, te ne esci molto prima (tra l'altro è un esercizio che si fa alle superiori, all'ITIS, quando si studiano gli alberi, appunto).

Soltanto un suggerimento: quello non + C++, ma C. Se vuoi usare il C++, cerca di sfruttare le caratteristiche del linguaggio, e non fermarti al classico cout.

[Z80Fan]

• 

Si ma sullo Z80 non ho la memoria dinamica per fare gli alberi!  :lol:

Soltanto un suggerimento: quello non + C++, ma C. Se vuoi usare il C++, cerca di sfruttare le caratteristiche del linguaggio, e non fermarti al classico cout.

Già usare cout lo rende C++; cmq, se avessi dovuto scriverlo per usarlo in C++, sarebbe stato diverso, ma lo ho fatto solo per testare l'idea prima di tradurlo in asm.

[cdimauro]

• 

Si ma sullo Z80 non ho la memoria dinamica per fare gli alberi!  :lol:

Ahi ahi ahi: lei mi cade sugli alberi!

Si possono utilizzare anche sullo z80 definendo un'area di memoria allo scopo. Esattamente come sul mio valutatore di espressioni per il 68000, dove avevo allocato uno stack di una precisa dimensione.

Semplicemente metti un tetto al massimo numero di nodi utilizzabili.

[Z80Fan]

• 

Si possono utilizzare anche sullo z80 definendo un'area di memoria allo scopo. Esattamente come sul mio valutatore di espressioni per il 68000, dove avevo allocato uno stack di una precisa dimensione.

Semplicemente metti un tetto al massimo numero di nodi utilizzabili.

Bene, ho capito cosa intendi.

Cmq ho già questo algoritmo che funziona bene, non mi serve manco la ricorsione...

Implemento questo intanto, giusto per mostrare qualcosa all'esame, al massimo non lo presenterò come "Interprete Basic" ma come "calcolatrice"  :lol:

Oppure posso montare il mio famoso mergesort

[TheKaneB]

• 

finchè non metti le variabili, non puoi fare nemmeno un algoritmo, ne sei consapevole giusto? :-D

per la memoria dinamica, implementati una banale "malloc"... ci sono decine di algoritmi già pronti che richiedono solo un buffer di memoria, quindi un puntatore e un size, da utilizzare come arena per le allocazioni. Se proprio non vuoi sbatterti a fartelo da zero ci sono già centinaia di implementazioni precotte in giro :-)

PS: Se lo scopo è semplicemente quello di allocare spazio per i nodi dell'albero, dal momento che hanno una dimensione nota a priori, puoi usare un banalissimo algoritmo di allocazione di tipo bitmap. Se vuoi degli algoritmi già pronti cerca "bitmap allocation object caching" in qualche sito di game programming :-)

[Z80Fan]

• 

finchè non metti le variabili, non puoi fare nemmeno un algoritmo, ne sei consapevole giusto? :-D

Ho detto che non ci sono, non che non ci saranno mai.
Ho già pensato una piccola modifica che mi permette di usare le funzioni...

per la memoria dinamica, implementati una banale "malloc"... ci sono decine di algoritmi già pronti che richiedono solo un buffer di memoria, quindi un puntatore e un size, da utilizzare come arena per le allocazioni. Se proprio non vuoi sbatterti a fartelo da zero ci sono già centinaia di implementazioni precotte in giro :-)

L'algoritmo non è un problema: lo ho già implementato nell'OS

[clros]

• 

@TheKaneB:

Il tuo valutatore parsa correttamente anche funzioni a cui puoi passare parametri?


Ad esempio: pow(4,2) oppure sqrt(4) vengono valutate?

Io ne avevo scritto uno (molto) tempo fa e in effetti il mio non supportava le variabili, ma avevo previsto un metodo per valutare le funzioni in quella maniera, solo che lo facevo in maniera un po' "originale": all'inizio scorrevo tutta l'espressione e sostituivo alle funzioni un operatore (ad esempio pow(4,2) diventava 4^2) e poi valutavo il tutto con lo stack...

[TheKaneB]

• 

certo, le funzioni (built-in) possono essere tokenizzate come qualsiasi altro operatore, al pari dei simboli * - + ecc...

Quindi sarebbero valide le espressioni Sin x + 50 che è diversa da Sin(x + 50) ad esempio :-)

In tal caso l'operatore Sin è un operatore unario, al pari del segno - (da non confondersi con l'operatore binario "differenza" sempre associato al simbolo - ).

Se, invece, si vuole fare un linguaggio più complesso, che permetta la definizione di funzioni custom con numero e tipo di parametri variabile, bisogna implementare un parser più completo tipo LL(1), ma a quel punto diventa fondamentale capire i concetti di linguaggio formale, grammatica, state machine, ecc... :-)

[clros]

• 

Cosa che io nn ho mai studiato seriamente.. :-(

[clros]

• 

[...]

durante il parsing costruisco l'albero, poi valuto l'espressione ricorsivamente. L'avevo scritto tempo fa per un compilatore minimale. Il vantaggio di questo metodo è che puoi valutare le espressioni costanti durante il parsing e prima della generazione del codice.

Se trovo (e se ti serve) il libro (un pdf gratuito di qualche università americana) da cui ho studiato questa tecnica, te lo passo :-)

Adesso mi serve un valutatore di espressioni con variabili ...potresti dirmi dove posso trovare il libro di cui parli?
(anche se sn sicuro che in qualche libro di algoritmi dell'uni che ho a casa ci deve essere qualcosa...)

[Z80Fan]

• 

Adesso mi serve un valutatore di espressioni con variabili ...potresti dirmi dove posso trovare il libro di cui parli?
(anche se sn sicuro che in qualche libro di algoritmi dell'uni che ho a casa ci deve essere qualcosa...)

Quando ancora stavo cercando di fare quel valutatore, avevo trovato dei bei siti che spiegavano la tecnica, vedo se riesco a ritrovarli.

EDIT: Ecco principalmente erano questi 3:
http://www.arstdesign.com/articles/expr ... ation.html
http://www.strchr.com/expression_evaluator
http://compilers.iecc.com/crenshaw/tutor2.txt

Cmq le variabili le tratti come i numeri: dove ti aspetti un numero, ma trovi un simbolo, cerchi nella tabella delle variabili e prendi il valore (o l'indirizzo se stai facendo un compilatore) da li.

[clros]

• 

Cmq le variabili le tratti come i numeri: dove ti aspetti un numero, ma trovi un simbolo, cerchi nella tabella delle variabili e prendi il valore (o l'indirizzo se stai facendo un compilatore) da li.

Pensavo infatti di fare proprio così! Solo che avevo capito che il metodo di TheKaneB (quello basato su albero invece di stack) poteva valutare diversamente/meglio espessioni con variabili (anche il mio valutatore è basato su stack!)