[JAVA]Calcolatrice con gli stack
Ragazzi sto letteralmente impazzendo con questo programma che dovrebbe creare una calcolatrice(ancora non è evoluto infatti non ho scritto codice per assegnare le priorità degli operatori semplicemente perchè prima vorrei farlo funzionare per risolvere una semplice espressione e poi lo vado a complicare!)il codice commentato è il seguente:
Se volete spiegato passo dopo passo quello che voglio fare(perchè magari dai commenti non si capisce) chiedete pure.Grazie a tutti
* @(#)Calcolatrice.java
*Questo programma si pone come scopo
*quello di implementare una calcolatrice
*in grado di eseguire tutti i calcoli
*seguendo il corretto ordine delle parentesi.
*
*Risoluzione grafica: dopo aver implementato 3stack nel sugente ordine:
*1)Stack numeri;
*2)Stack operatori;
*3)Stack parentesi;
*si procederà come segue: con una push si inseriscono i vari
*caratteri(numeri operatori e parentesi)nei vari stack di apparteneza
*dopodichè tramite la pop verranno estratti uno alla volta e in ordine
*i caratteri e verranno immessi in uno stack temporaneo.Con una successiva
*pop verranno estratti e di volta in volta si procederà al calcolo del
*risultato finale.
*
* @author soeca
* @version 1.00 2010/7/6
*/
public class Calcolatrice
{
public static void main(String args[])
{
String string="(5+3+2)";
Stacc sNumeri=new Stacc(string.length());
Stacc sOperatori=new Stacc(string.length());
Stacc sParentesi=new Stacc(string.length());
Stacc sTemp=new Stacc(string.length());
for (int i = 0; i<string.length(); i++)
{
sNumeri.Push('N'); //in ogni livello mettera' N a meno che non e' presente
sParentesi.Push('N'); //o un operatore o un numero oppure una parentesi in tal caso verra'
sOperatori.Push('N'); //posizionata nello stack di appartenenza
if(string.charAt(i)=='(' || string.charAt(i)==')')
sParentesi.Push(string.charAt(i));
else
{
if(string.charAt(i)=='+' || string.charAt(i)=='-' || string.charAt(i)=='*' || string.charAt(i)=='/')
sOperatori.Push(string.charAt(i));
else
sNumeri.Push(string.charAt(i));
}
}
for (int j = 0; j<string.length(); j++)
{
if(string.charAt(j)=='(' || string.charAt(j)==')') //tutti gli elementi dello stack devono essere presi
sTemp.Push(sParentesi.Pop( )); //e inseriti in uno stack temporaneo
if(string.charAt(j)=='N')
{
if(string.charAt(j)=='+' || string.charAt(j)=='-' || string.charAt(j)=='*' || string.charAt(j)=='/')
sTemp.Push(sOperatori.Pop( ));
else
sTemp.Push(sNumeri.Pop( ));
}
}
String str="";
System.out.println("comincio a fare i calcoli delle parentesi");
int cont=0;//contatore di parentesi
int mem=0;/*memorizza la posizione dell'array dove
è presente una parentesi così da poterla richiamare
successivamente per assegnare la priorità ai vari blocchi
di operazioni dentro le parentesi.*/
int mem1=0;//memorizza la posizione della parentesi chiusa
for (int i = 0; i<string.length(); i++)
//con questo for entro dentro lo stack temp e memorizzo in una stringa tutti gli elementi, se
//trovo una parentesi aperta memorizzo la sua posizione e partendo da li comincio a svolgere le operazioni
//fino alla parentesi chiusa
{
str+=sTemp.Pop();
if(str.charAt(i)=='(')
{
System.out.println("sono dentro l'if delle parentesi");
cont++;
mem=i;
System.out.println("cont vale"+cont+" mem vale:"+mem);
}
if(str.charAt(i)==')')
mem1=i;
System.out.println("cont vale"+cont+" mem vale:"+mem+" mentre mem1 vale:"+mem1);
}
cont=0;
Calc c =new Calc();
String risultato="";
//Comincio a fare i calcoli
System.out.println("fuori dal for mem vale:"+mem+" mentre mem1 vale:"+mem1);
for (int i = mem; i<mem1; i++)
{
System.out.println("sto entrando nel for per fare i calcoli!");
if(str.charAt(i+2)=='+')
{
System.out.println("sono dentro l'operazione somma e gli sto passando i seguenti valori:"+str.charAt(i+1)+ "e "+str.charAt(i+3));
risultato+=c.Somma(str.charAt(i+1),str.charAt(i+3));
}
if(str.charAt(i+2)=='*')
risultato+=c.Prodotto(str.charAt(i+1),str.charAt(i+3));
if(str.charAt(i+2)=='-')
risultato+=c.Differenza(str.charAt(i+1),str.charAt(i+3));
if(str.charAt(i+2)=='/')
risultato+=c.Quoziente(str.charAt(i+1),str.charAt(i+3));
System.out.println("esco dal for dei calcoli e il risultato fino ad ora e':"+risultato);
}
//Stampiamo il risultato finale
System.out.println("Il risultato e':"+risultato);
}
}
Se volete spiegato passo dopo passo quello che voglio fare(perchè magari dai commenti non si capisce) chiedete pure.Grazie a tutti
Risposte
Che cosa non funziona esattamente? Dove hai letto l'algoritmo che stai seguendo?
Se esegui il codice postato ti accorgi della presenza di vari problemi come per esempio: il risultato non viene calcolato, le variabili cont,mem e mem1 hanno sempre valore 0 e questo perchè nell'ultimo for non ci entra proprio!inoltre nei vari stack non viene memorizzato il valore(per esempio non viene memorizzato il 5 o il + o la N) ma viene memorizzato il codice ascii corrispondente!!e non capisco il perchè!!!
Noto subito alcuni errori:
1. string.charAt(int i) restituisce un char che contiene il valore ASCII del carattere corrispondente. '5' non è insomma uguale a 5, ma 54.
2. Non è chiaro il significato della riga (o meglio lo è ma non è chiaro il tuo intento)
Qui stai verificando che la stringa contenga una lettera N maiuscola ad un certo punto della stringa. Non credo fosse la tua intenzione siccome all'interno del corpo dell'if verifichi se alla stessa posizione ci sono dei numeri o degli operatori.
Con uno studio del programma più approfondito (per ora l'ho solo letto da questo post e quindi non ho provato ad eseguirlo o fare un debug). Mi rimangono comunque molto oscure le tue esatte intenzioni. Cercheresti di spiegarmi a parole cosa dovrebbe fare ogni ciclo? Il codice Java è infatti evidentemente sbagliato e quindi sarebbe meglio tornare alle intenzioni per capire cosa stavi cercando in effetti di fare.[/code]
1. string.charAt(int i) restituisce un char che contiene il valore ASCII del carattere corrispondente. '5' non è insomma uguale a 5, ma 54.
2. Non è chiaro il significato della riga (o meglio lo è ma non è chiaro il tuo intento)
if(string.charAt(j)=='N')
Qui stai verificando che la stringa contenga una lettera N maiuscola ad un certo punto della stringa. Non credo fosse la tua intenzione siccome all'interno del corpo dell'if verifichi se alla stessa posizione ci sono dei numeri o degli operatori.
Con uno studio del programma più approfondito (per ora l'ho solo letto da questo post e quindi non ho provato ad eseguirlo o fare un debug). Mi rimangono comunque molto oscure le tue esatte intenzioni. Cercheresti di spiegarmi a parole cosa dovrebbe fare ogni ciclo? Il codice Java è infatti evidentemente sbagliato e quindi sarebbe meglio tornare alle intenzioni per capire cosa stavi cercando in effetti di fare.[/code]
Intanto ne approfitto per ringraziarti visto che comunque su 5forum dove ho postato fino ad ora sei l'unico che mi sta dando una mano!!Ho risolto un pò di problemi e questa è la versione quasi corretta del codice.....stavolta i vari stack vengono riempiti in modo corretto ma ancora il secondo for non funziona come dovrebbe perchè lo stack sTemp non viene riempito correttamente.Ora vedo un pò di sistemarlo!!
se hai qualsiasi dubbio sul mio codice posta pure....così capisci il mio modo di interpretare il programma e magari mi dai qualche consiglio!!Grazie ancora.
/**
* @(#)Calcolatrice.java
*Questo programma si pone come scopo
*quello di implementare una calcolatrice
*in grado di eseguire tutti i calcoli
*seguendo il corretto ordine delle parentesi.
*
*Risoluzione grafica: dopo aver implementato 3stack nel sugente ordine:
*1)Stack numeri;
*2)Stack operatori;
*3)Stack parentesi;
*si procederà come segue: con una push si inseriscono i vari
*caratteri(numeri operatori e parentesi)nei vari stack di apparteneza
*dopodichè tramite la pop verranno estratti uno alla volta e in ordine
*i caratteri e verranno immessi in uno stack temporaneo.Con una successiva
*pop verranno estratti e di volta in volta si procederà al calcolo del
*risultato finale.
*
* @author soeca
* @version 1.00 2010/7/6
*/
public class Calcolatrice
{
public static void main(String args[])
{
String string="(5+3+2)";
Stacc sNumeri=new Stacc(string.length());
Stacc1 sOperatori=new Stacc1(string.length());
Stacc1 sParentesi=new Stacc1(string.length());
Stacc sTemp=new Stacc(string.length());
for (int i = 0; i<string.length(); i++)
{
//in ogni livello mettera' N a meno che non e' presente
//o un operatore o un numero oppure una parentesi in tal caso verra'
//posizionata nello stack di appartenenza
if(string.charAt(i)=='(' || string.charAt(i)==')')
{
sParentesi.Push(string.charAt(i));
sOperatori.Push('N');
sNumeri.Push('N');
}
else
{
if(string.charAt(i)=='+' || string.charAt(i)=='-' || string.charAt(i)=='*' || string.charAt(i)=='/')
{
sOperatori.Push(string.charAt(i));
sParentesi.Push('N');
sNumeri.Push('N');
}
else
{
sNumeri.Push(string.charAt(i));
sOperatori.Push('N');
sParentesi.Push('N');
}
}
/*System.out.println("snumeri:"+sNumeri.toString());
System.out.println("soperatori:"+sOperatori.toString());
System.out.println("sparentesi:"+sParentesi.toString());*/
}
char car=sOperatori.Pop();
for (int j = 0; j<string.length(); j++)
{
if(string.charAt(j)=='(' || string.charAt(j)==')') //tutti gli elementi dello stack devono essere presi
sTemp.Push(sParentesi.Pop( )); //e inseriti in uno stack temporaneo
if(sOperatori.Pop()=='+' || sOperatori.Pop()=='-' || sOperatori.Pop()=='*' || sOperatori.Pop()=='/')
sTemp.Push(car);
else
sTemp.Push(sNumeri.Pop( ));
}
String str="";
System.out.println("comincio a fare i calcoli delle parentesi");
int cont=0;//contatore di parentesi
int mem=0;/*memorizza la posizione dell'array dove
è presente una parentesi così da poterla richiamare
successivamente per assegnare la priorità ai vari blocchi
di operazioni dentro le parentesi.*/
int mem1=0;//memorizza la posizione della parentesi chiusa
for (int i = 0; i<string.length(); i++)
//con questo for entro dentro lo stack temp e memorizzo in una stringa tutti gli elementi, se
//trovo una parentesi aperta memorizzo la sua posizione e partendo da li comincio a svolgere le operazioni
//fino alla parentesi chiusa
{
str+=sTemp.Pop();
if(str.charAt(i)=='(')
{
System.out.println("sono dentro l'if delle parentesi");
cont++;
mem=i;
System.out.println("cont vale"+cont+" mem vale:"+mem);
}
if(str.charAt(i)==')')
mem1=i;
System.out.println("cont vale"+cont+" mem vale:"+mem+" mentre mem1 vale:"+mem1);
}
cont=0;
Calc c =new Calc();
String risultato="";
//Comincio a fare i calcoli
System.out.println("fuori dal for mem vale:"+mem+" mentre mem1 vale:"+mem1);
for (int i = mem; i<mem1; i++)
{
System.out.println("sto entrando nel for per fare i calcoli!");
if(str.charAt(i+2)=='+')
{
System.out.println("sono dentro l'operazione somma e gli sto passando i seguenti valori:"+str.charAt(i+1)+ "e "+str.charAt(i+3));
risultato+=c.Somma(str.charAt(i+1),str.charAt(i+3));
}
if(str.charAt(i+2)=='*')
risultato+=c.Prodotto(str.charAt(i+1),str.charAt(i+3));
if(str.charAt(i+2)=='-')
risultato+=c.Differenza(str.charAt(i+1),str.charAt(i+3));
if(str.charAt(i+2)=='/')
risultato+=c.Quoziente(str.charAt(i+1),str.charAt(i+3));
System.out.println("esco dal for dei calcoli e il risultato fino ad ora e':"+risultato);
}
//Stampiamo il risultato finale
System.out.println("Il risultato e':"+risultato);
}
}se hai qualsiasi dubbio sul mio codice posta pure....così capisci il mio modo di interpretare il programma e magari mi dai qualche consiglio!!Grazie ancora.
Devi stare molto attento ai side effect (non ricordo come si dice in italiano) delle funzioni che usi. Con side effect si intende un cambiamento nello stato interno del tuo programma. Chiamando una funzione di questo tipo una o più volte può avere un grande effetto sul risultato del programma ed è quindi importante prestare particolarmente attenzione quando si usano. È per questo motivo che è meglio cercare di rendere il più possibile del programma side effect free. In particolare la seguente riga è completamente sbagliata:
Ad ogni Pop() l'ultimo elemento dello stack viene eliminato. Ogni chiamata a Pop() restituisce un valore diverso!!! Inoltre alla fine di questa riga di codice 4 elementi sono stati eliminati dallo stack degli operatori!!! Il metodo corretto è quindi:
Inoltre ti faccio notare che ogni volta hai inserito car, che era l'ultimo elemento dello stack prima di entrare del ciclo e non è quindi poi mai cambiato. Incidentalmente quel valore era 'N' nel tuo esempio.
Ma consideriamo i primi due cicli e vediamo che cosa stai facendo. Parti dalla stringa "(5+3+2)". Poi iteri su tutti gli elementi della stringa e inserisci il carattere all'interno dello stack corrispondente e 'N' in quelli non corrispondenti. I tre stack diventano a questo punto:
- sParentesi = (NNNNN)
- sOperatori = NN+N+NN
- sNumeri = N5N3N2N
Nel secondo ciclo iteri nuovamente lungo la stringa e questa volta inserisci tutto in uno stack temporaneo. Ignorando i problemi di cui ho parlato sopra e cercando di interpretare le tue intenzioni a questo punto mi verrebbe:
- sTemp = )NN2NNN
Dubito che questo sia il risultato che volevi. Quello che ho fatto è stato semplicemente iterare sulla stringa e fare un pop in sOperatori, sParentesi o sNumeri a seconda del carattere corrispondente nella stringa. Questo dimostra abbastanza chiaramente che la tua logica è proprio fallata. Vorrei quindi capire se a questo algoritmo ci sei arrivato tu oppure se l'hai letto da qualche parte. In entrambi i casi vorrei me lo descrivessi in modo da capire cosa stai cercando di fare.
if(sOperatori.Pop()=='+' || sOperatori.Pop()=='-' || sOperatori.Pop()=='*' || sOperatori.Pop()=='/')
Ad ogni Pop() l'ultimo elemento dello stack viene eliminato. Ogni chiamata a Pop() restituisce un valore diverso!!! Inoltre alla fine di questa riga di codice 4 elementi sono stati eliminati dallo stack degli operatori!!! Il metodo corretto è quindi:
char value = sOperatori.Pop(); if (value == '+' || ... || value == '/')
Inoltre ti faccio notare che ogni volta hai inserito car, che era l'ultimo elemento dello stack prima di entrare del ciclo e non è quindi poi mai cambiato. Incidentalmente quel valore era 'N' nel tuo esempio.
Ma consideriamo i primi due cicli e vediamo che cosa stai facendo. Parti dalla stringa "(5+3+2)". Poi iteri su tutti gli elementi della stringa e inserisci il carattere all'interno dello stack corrispondente e 'N' in quelli non corrispondenti. I tre stack diventano a questo punto:
- sParentesi = (NNNNN)
- sOperatori = NN+N+NN
- sNumeri = N5N3N2N
Nel secondo ciclo iteri nuovamente lungo la stringa e questa volta inserisci tutto in uno stack temporaneo. Ignorando i problemi di cui ho parlato sopra e cercando di interpretare le tue intenzioni a questo punto mi verrebbe:
- sTemp = )NN2NNN
Dubito che questo sia il risultato che volevi. Quello che ho fatto è stato semplicemente iterare sulla stringa e fare un pop in sOperatori, sParentesi o sNumeri a seconda del carattere corrispondente nella stringa. Questo dimostra abbastanza chiaramente che la tua logica è proprio fallata. Vorrei quindi capire se a questo algoritmo ci sei arrivato tu oppure se l'hai letto da qualche parte. In entrambi i casi vorrei me lo descrivessi in modo da capire cosa stai cercando di fare.
Ho letto su un altro forum quale fosse la tua intenzione. Vuoi cioè creare uno stack con il quale estrarre operatori e parentesi al contrario. Ma questo NON è il modo corretto di valutare una espressione. Considera per esempio l'espressione:
2 * 3 + 4
Usando il tuo metodo leggi prima 4, poi +, poi 3 ed esegui l'operazione di somma, poi trovi il prodotto e infine il 2 ed esegui il prodotto. Questo metodo risolve (4+3)*2 che è uguale a 14 e non il corretto (2*3)+4=10. In questo caso il metodo corretto sarebbe quello di leggere l'espressione partendo dall'inizio, ma anche questo metodo è destinato a fallire in alcuni casi. Come ti è stato detto su quel forum non è inoltre necessario usare 4 stack per fare questo ma è sufficiente leggere la stringa al contrario una volta. Se vuoi posso cercare di correggere il tuo programma, ma se il tuo obiettivo è quello di fare una calcolatrice allora devi cambiare proprio l'algoritmo da usare.
2 * 3 + 4
Usando il tuo metodo leggi prima 4, poi +, poi 3 ed esegui l'operazione di somma, poi trovi il prodotto e infine il 2 ed esegui il prodotto. Questo metodo risolve (4+3)*2 che è uguale a 14 e non il corretto (2*3)+4=10. In questo caso il metodo corretto sarebbe quello di leggere l'espressione partendo dall'inizio, ma anche questo metodo è destinato a fallire in alcuni casi. Come ti è stato detto su quel forum non è inoltre necessario usare 4 stack per fare questo ma è sufficiente leggere la stringa al contrario una volta. Se vuoi posso cercare di correggere il tuo programma, ma se il tuo obiettivo è quello di fare una calcolatrice allora devi cambiare proprio l'algoritmo da usare.
Scusami se rispondo ora!Comunque lo so che posso fare l'esercizio senza usare 4stack ma leggendo la stringa al contrario o ancora in molti altri modi però il testo voleva la realizzazione di una calcolatrice mediante l'uso di stackPer questo, considerando che le pile sono strutture LIFO(ciò vuol dire che se inserisco gli elementi: parentesi,operatori e numeri, dentro i rispettivi stack, quando dovrò effetturare l'operazione di POP avrò tutta la stringa al contrario) mi serviva quindi un qualcosa che non si discostasse molto da ciò che richiede il problema e mi riportasse la stringa nel verso giusto pronta per essere letta. Ora provo la tua correzione e ti faccio sapere.Grazie ancora per l'aiuto!!PS. Per quanto riguarda il cambio dell'algoritmo da usare....io sinceramente(sarà sbagliato)volevo intanto implementare una calcolatrice nel modo + semplice possibile per poi andarla a complicare successivamente...se già sto avendo notevoli difficoltà qui(che dovrebbe essere un esercizio banale secondo il prof) figuriamoci se lo complicassi assegnando per es. le priorità alle operazioni!!Volevo partire prima da un qualcosa di base base e molto semplice e poi successivamente (avendo un programma funzionante) andarlo a complicare!
Ho fatto la correzione però non mi aggiorna le variabili...posto il codice per far capire cosa intendo:
Ho pensato allora che il problema fosse della classe Stacc1 nel metodo Pop() e ho notato di aver commesso un errore infatti il metodo è questo:
così funziona(nel senso che non mi da ArrayIndexOutOfBoundException:7 secondo me però il metodo dovrebbe essere modificato in:
Per far comprendere meglio metto tutto il codice di Stacc1:
char value,value1,value2;
for (int j = 0; j<string.length(); j++)
{
value=sParentesi.Pop();
value1=sOperatori.Pop();
value2=sNumeri.Pop();
if(value=='(' || value==')')
sTemp.Push(value);
else
{
if((value1=='+' || value1=='-' || value1=='*' || value1=='/'))
sTemp.Push(value1);
else //Deve esserci per forza un numero
sTemp.Push(value2);
}
}
Ho pensato allora che il problema fosse della classe Stacc1 nel metodo Pop() e ho notato di aver commesso un errore infatti il metodo è questo:
public char Pop(){
if(isEmpty())
return '0';
char x=el[top-1];
return x;
}così funziona(nel senso che non mi da ArrayIndexOutOfBoundException:7 secondo me però il metodo dovrebbe essere modificato in:
public char Pop(){
if(isEmpty())
return 'f';
char x=el[top--]; //nel vecchio modo prendevo sempre la posizione precedente, cosi' invece prendo la posizione top e poi decremento
return x;
}
Per far comprendere meglio metto tutto il codice di Stacc1:
public class Stacc1{ //implements Pile{
protected int top;
protected int max;
protected char [] el;
public Stacc1(int m)
{
max=m;
el=new char[max];
top=0;
}
public int Top()
{
if(isEmpty())
return -1;
return (el[top-1]);
}
public boolean isFull(){
return (top==max);
}
public boolean isEmpty(){
if(top!=0)
return false;
return true;
}
public boolean Clear(){
top=0;
return true;
}
public char Pop(){
if(isEmpty())
return 'f';
char x=el[top--];
return x;
}
public char Push(char val)
{
if(isFull())
return 'N';
el[top++]=val;
return el[top-1];
}
public String toString()
{
String stampa = "";
for(int i = 0; i<el.length; i++)
stampa += el[i];
return stampa;
}
}
Fatemi sapere per favore!!Grazie.
Quando un esercizio richiede o consiglia l'uso di qualcosa è perché questa cosa è utile per risolvere il tuo problema. Se sei costretto a complicare enormemente il tuo programma solo per usare quello che l'esercizio richiede, probabilmente stai sbagliando qualcosa o stai almeno usando una soluzione diversa da quella che l'autore aveva in mente. Nel tuo caso stai sbagliando tutto dell'esercizio. Il punto principale dell'uso di una stack in questo esercizio è per semplificare la gestione di parentesi e della priorità tra le operazioni, proprio quello che stai evitando di considerare in questo momento insomma. L'uso degli stack non è evidente perché non stai ancora risolvendo il problema che lo richiede. Per comprendere perché lo stack è utile nel caso di parentesi considera il seguente esempio:
(5 + (3 * (2 + 7))) + (2 * 3)
Ho inserito molte parentesi in modo che ci fosse un preciso ordine con cui eseguire le operazioni. Faccio insomma finta che non esiste né l'associatività delle operazioni, né una diversa priorità tra di esse. L'operazione mostrata è equivalente all'albero:
Valutare l'espressione precedente è equivalente a visitare l'albero eseguendo le operazioni nei nodi una volta che entrambi i suoi figli siano stati valutati. In questo caso l'uso di uno stack sarebbe nascosto dalla chiamate ricorsiva. Gli stack sono anche usati quando si passa e poi si valuta una espressione scritta in RPN. Valutando la stessa espressione ma usando le seguenti parentesi (equivalenti al tuo modo di valutare l'espressione):
(5 + (3 * (2 + (7 + (2 * 3)))))
Si otterrebbe l'albero
È ovvio che si potrebbe usare uno stack anche in questo caso ma la sua utilità è meno evidente essendo semplice valutarlo direttamente. Lo stack viene insomma usato per memorizzare lo stato delle espressioni che non hai incontrato ma che non puoi ancora valutare completamente e per definire insomma una specie di ordine con il quale eseguirle.
Se vuoi risolvere un problema più semplice della valutazione completa di una espressione e vuoi usare gli stack risolvi almeno questo: scrivi un programma che valuti una espressione da sinistra a destra come fanno molte calcolatrici portatili. Esiste insomma un subtotale che viene continuamente aggiornato man mano che vengono inseriti i numeri e le operazioni e ogni operazione agisce su questo subtotale e su un numero eventualmente inserito successivamente. Il programma deve inoltre supportare le parentesi. L'introduzione di una parentesi blocca la valutazione dell'espressione attuale e inizia la valutazione di una nuova espressione il cui valore viene poi usato nell'espressione iniziale quando si incontra la parentesi chiusa equivalente. Per una maggiore flessibilità se non viene incontrata una parentesi prima della fine dell'espressione si considera come se la parentesi fosse inserita subito dopo la fine. Usa una stack per memorizzare lo stato di una espressione quando si passa ad un livello di parentesi successivo.
Se viene inserita per esempio l'espressione:
2 + 5 * 7 + (2 * 5
Si calcola il numero (usando le normali regole di calcolo):
((2 + 5) * 7) + (2 * 5)
Spero sia chiaro.
Ma perché stai usando una classe da te scritta per uno stack quando Java contiene già una classe che implementa uno stack (java.util.Stack)? La tua classe Stack è in effetti sbagliata. Come hai giustamente notato pop deve modificare top, ma hai sbagliato operatore: devi usare --top. Il valore è infatti contenuto in top-1 e quindi il valore restituito dall'espressione dentro le parentesi quadre deve essere top-1. Questo non succede nel caso di top--, in cui il decremento è fatto dopo aver restituito al resto dell'espressione il valore corrente di top. Un altra nota riguarda il metodo isEmpty. Non ha senso scrivere espressioni come:
o l'equivalente con true e false scambiati perché cond è già un boolean e quindi puoi restituire semplicemente lui o il suo negato. Non c'è alcun motivo per cui return debba ricevere una espressione costante.
(5 + (3 * (2 + 7))) + (2 * 3)
Ho inserito molte parentesi in modo che ci fosse un preciso ordine con cui eseguire le operazioni. Faccio insomma finta che non esiste né l'associatività delle operazioni, né una diversa priorità tra di esse. L'operazione mostrata è equivalente all'albero:
+
+ *
5 * 2 3
3 +
2 7
Valutare l'espressione precedente è equivalente a visitare l'albero eseguendo le operazioni nei nodi una volta che entrambi i suoi figli siano stati valutati. In questo caso l'uso di uno stack sarebbe nascosto dalla chiamate ricorsiva. Gli stack sono anche usati quando si passa e poi si valuta una espressione scritta in RPN. Valutando la stessa espressione ma usando le seguenti parentesi (equivalenti al tuo modo di valutare l'espressione):
(5 + (3 * (2 + (7 + (2 * 3)))))
Si otterrebbe l'albero
+
* 5
+ 3
+ 2
* 7
2 3
È ovvio che si potrebbe usare uno stack anche in questo caso ma la sua utilità è meno evidente essendo semplice valutarlo direttamente. Lo stack viene insomma usato per memorizzare lo stato delle espressioni che non hai incontrato ma che non puoi ancora valutare completamente e per definire insomma una specie di ordine con il quale eseguirle.
Se vuoi risolvere un problema più semplice della valutazione completa di una espressione e vuoi usare gli stack risolvi almeno questo: scrivi un programma che valuti una espressione da sinistra a destra come fanno molte calcolatrici portatili. Esiste insomma un subtotale che viene continuamente aggiornato man mano che vengono inseriti i numeri e le operazioni e ogni operazione agisce su questo subtotale e su un numero eventualmente inserito successivamente. Il programma deve inoltre supportare le parentesi. L'introduzione di una parentesi blocca la valutazione dell'espressione attuale e inizia la valutazione di una nuova espressione il cui valore viene poi usato nell'espressione iniziale quando si incontra la parentesi chiusa equivalente. Per una maggiore flessibilità se non viene incontrata una parentesi prima della fine dell'espressione si considera come se la parentesi fosse inserita subito dopo la fine. Usa una stack per memorizzare lo stato di una espressione quando si passa ad un livello di parentesi successivo.
Se viene inserita per esempio l'espressione:
2 + 5 * 7 + (2 * 5
Si calcola il numero (usando le normali regole di calcolo):
((2 + 5) * 7) + (2 * 5)
Spero sia chiaro.
Ma perché stai usando una classe da te scritta per uno stack quando Java contiene già una classe che implementa uno stack (java.util.Stack)? La tua classe Stack è in effetti sbagliata. Come hai giustamente notato pop deve modificare top, ma hai sbagliato operatore: devi usare --top. Il valore è infatti contenuto in top-1 e quindi il valore restituito dall'espressione dentro le parentesi quadre deve essere top-1. Questo non succede nel caso di top--, in cui il decremento è fatto dopo aver restituito al resto dell'espressione il valore corrente di top. Un altra nota riguarda il metodo isEmpty. Non ha senso scrivere espressioni come:
if (cond)
return true;
else
return false;
o l'equivalente con true e false scambiati perché cond è già un boolean e quindi puoi restituire semplicemente lui o il suo negato. Non c'è alcun motivo per cui return debba ricevere una espressione costante.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo