1 pusha 0 in stackNum10 legge numero n11 se non è stato letto un numero ma un operatore (incluse le parentesi), assegna x=n e vai a 4015 push n su stack num20 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 toglie40 push x su stack op (tranne nel caso in cui fosse stata una parentesi chiusa)50 se non è finita la stringa, goto 1060 esegui le operazioni mancanti nello stack op70 il top dello stack num è il risultatoparentesi = precedenza minima
#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. = 11int stackNum[100] = {0}, spNum = 0, spOp = 0;char stackOp[100] = {0};char input[50];int ptrIn=0; // puntatore inputint 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 Opvoid 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 validobool 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 numericabool 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;}
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.
Si ma sullo Z80 non ho la memoria dinamica per fare gli alberi! :lol:
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.
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 :-)
[...]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...)
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.