Trovare l'errore! [risolutore espressioni aritmetiche]

[Mitch96]

Salve ragazzi, ho un quesito da porvi, ma prima vi spiego un pò.
Allora la traccia a cui corrisponde il mio problema è questa:
"...Gli operatori ammessi sono +,-,*,^ (elevamento a potenza) e valgono le usuali priorità della matematica, cioè: Π(^)>Π(*,/,)>Π(+,-).
A parità di priorità, si assume l’associatività a sinistra.
Algoritmo di valutazione
Si usano due stack: il primo è uno stack di operandi, il secondo è uno stack di caratteri operatori. Quando arriva un operando, lo si inserisce in cima allo stack di operandi. Quando arriva un operatore, sia esso opc (operatore corrente), si procede come segue:
A) se opc è più prioritario dell’operatore in cima allo stack di operatori o tale stack è vuoto, si inserisce opc in cima allo stack degli operatori.
B) Se opc non è più prioritario rispetto alla cima dello stack operatori, si preleva l’operatore op in cima allo stack operatori, quindi si prelevano due operandi o2 (top) e o1 (top-1) dallo stack operandi (in caso di eccezioni, l’espressione è malformata). Si esegue o1 op o2. Il risultato è inserito in cima allo stack operandi.
Si continua ad eseguire il passo B) se opc risulta ancora non più prioritario dell’operatore affiorante la cima dello stack operatori. Dopo questo, o perché opc è più prioritario dell’operatore in cima allo stack operatori o perché lo stack è vuoto, si applica il caso A.
Quando l’espressione termina, se lo stack operatori non è vuoto, si estraggono uno alla volta gli operatori presenti e si applicano ai rispettivi due operandi prelevati dallo stack operandi, come spiegato al punto B), inserendo ogni volta il risultato in cima allo stack operandi.
Quando lo stack operatori è vuoto, allora lo stack operandi dovrebbe contenere un solo elemento che è il risultato dell’espressione. Ogni altra situazione (stack operandi vuoto o con più di un elemento) denota una situazione di espressione malformata. ...."

Ora, io ho fatto ciò:

import java.util.Stack;
import java.util.StringTokenizer;


public class RisolutoreEspressione {
        
        private static int operazione(int o1, String op, int o2){
            //if(op!="+" && op!="-" && op!="*" && op!="/" && op!="^") throw new IllegalArgumentException("Operatore non valido."); 
/*l'ho messo come commento perchè mi parte un errore, ma non è questo il problema, 
supponiamo che queste condizioni le abbia già verificate*/
            int ris=0;
            switch(op){
            case "^": ris=((int)Math.pow(o1, o2)); break;
            case "*": ris=(o1*o2); break;
            case "/": ris=(o1/o2); break;
            case "+": ris=(o1+o2); break;
            case "-": ris=(o1-o2); break;
            }
            return ris;
        }
        
        private static boolean prioritario(String opc, String op){
            switch(opc){
            case "^": if(op!="^") return true; 
            case "*": if(op=="+"||op=="-") return true; 
            case "/": if(op=="+"||op=="-") return true; 
            case "+": return false;
            case "-": return false;
            }
            return false;
        }
        
        private static void nonPrioritario(Stack<Integer> operandi, Stack<String> operatori){
            String op=operatori.pop();
            int o2=operandi.pop();
            int o1=operandi.pop();
            operandi.push(operazione(o1,op,o2));
        }
        
        public static int espressione(String s){
            Stack<Integer> operandi= new Stack<Integer>();
            Stack<String> operatori= new Stack<String>();
            StringTokenizer st= new StringTokenizer(s,"^*/+-",true);
            int o1= Integer.parseInt(st.nextToken());
            String opc;
            operandi.push(o1);
            boolean nxtIsInt=false;
            while(st.hasMoreTokens()){
                if(!nxtIsInt){
                    opc=st.nextToken();
                    boolean giàStatoPrioritario=false;
                    if( operatori.empty() ){operatori.push(opc); giàStatoPrioritario=true;}
                    else if(prioritario(opc,operatori.peek()) ){ 
                        operatori.push(opc); giàStatoPrioritario=true;}
                    else //penso che il problema sia quì sotto!
                        while (!prioritario(opc,operatori.peek()) || !operatori.empty()) {
                            nonPrioritario(operandi,operatori); 
                            if(operatori.empty()) break;
                        }
                    if(!giàStatoPrioritario) operatori.push(opc);
                    nxtIsInt=true;
                }
                else if(nxtIsInt){ 
                    operandi.push(Integer.parseInt(st.nextToken())); nxtIsInt=false;}
            }
            while (!operatori.empty()) nonPrioritario(operandi,operatori);
            return operandi.peek();
        }
        
        public static void main(String[]args){
            String s= "4^2-5*8+3+4";//"3^2*5-5" <--con questa espressione quì funziona
            int i=espressione(s);
            System.out.println(i);
        }
        
}

Ora vi chiedo la cortesia di darci un'occhiata e di aiutarmi a capire dove sia l'errore
Grazie mille in anticipo!

[LeleFT]

Ora vi chiedo la cortesia di darci un'occhiata e di aiutarmi a capire dove sia l'errore
Grazie mille in anticipo!

Dovresti almeno dire COSA ti fa pensare che vi sia un errore...
Dà risultati errati? Quali? E con quali input?
Non compila? Che messaggi dà il compilatore?
Compila ma non parte? Controllato lo stackTrace di eventuali eccezioni?

Insomma... almeno sapere COSA cercare, senza costringere a copincollare, compilare, eseguire e fare prove su prove. Aiutaci ad aiutarti.


Ciao.

[Mitch96]

senza costringere a copincollare, compilare, eseguire e fare prove su prove. Aiutaci ad aiutarti.

Non pensavo vi togliesse più di 5 minuti di tempo copiare, incollare e fare delle prove...
Comunque: il programma non da il risultato esatto. O meglio, non sempre da il risultato esatto.
Il programma funziona con input del tipo "3^2*5-5", "1+1+1+1+1+1" e insomma cose così.. (non so che dirvi su quali input funziona, con alcuni si(la maggiorparte sono espressioni banalissime) e con altri input del tipo "4^2-5*8+3+4" già non funziona più, da un risultato errato (95).)
Cosa mi fa pensare che vi sia un errore... mmm vediamo... ho inserito dei System.out.println(operandi); ogni volta che viene modificato lo Stack operandi in modo da cercare di capire il perchè dia un risultato errato. Con "4^2-5*8+3+4" come input ho notato che non venivano applicate le giuste priorità agli operatori, ma in realtà non è proprio così, diciamo che a volte applica delle operazioni non desiderate. Di seguito vi riporto l'output :

[4] //aggiunge il primo numero allo stack operandi
[4, 2] //nel frattempo nello stack operatori viene aggiunto il segno "^" e successivamente viene aggiunto in cima allo stack operandi il secondo numero
[16] //prende il segno - , lo confronta con la cima di operatori (che è ^), capisce che non è prioritario e perciò esegue 4^2, mette il risultato nella cima di operandi e mette il segno - in cima a operatori
[16, 5] //legge il numero 5 e lo mette in cima allo stack operandi
[11] //legge il segno * , lo confronta con la cima di operatori (che è -) e non so per quale motivo, invece di mettere in cima allo stack il segno *, compie l'operazione 16-5 e mette il risultato in cima allo stack operandi! (cioè, non riconosce che * è prioritario rispetto a - , e non capisco il perchè
[11, 8] // da qui in poi riprende a ragionare e le operazioni (che però non dovrebbero essere queste) sono esatte
[88]
[88, 3]
[91]
[91, 4]
[95]
[95]

l'output che dovrebbe uscire è invece: (p.s. forse ho sbagliato qualche passaggio)

[4]
[4, 2]
[16]
[16, 5]
[16, 5, 8]
[16, 40]
[-24]
[-24, 3]
[-21]
[-21, 4]
[-17]

Non so cosa altro dire per farmi aiutare...

[LeleFT]

Non l'avevo visto subito (oltretutto, non uso Java 7 e lo switch su stringhe):

      private static boolean prioritario(String opc, String op){
            switch(opc){
            case "^": if(op!="^") return true; 
            case "*": if(op=="+"||op=="-") return true; 
            case "/": if(op=="+"||op=="-") return true; 
            case "+": return false;
            case "-": return false;
            }
            return false;
        }

Le stringhe (ed in generale gli oggetti) non si confrontano con gli operatore relazionali, ma si deve usare il metodo equals().

String str1 = ...;
String str2 = ...;

if (str1 == str2) {   // SBAGLIATO (quasi sempre false)
   ...
}

if ( str1.equals(str2) ) {   // CORRETTO
   ...
}

if (str1 != str2) {   // SBAGLIATO (quasi sempre true)
   ...
}

if ( !str1.equals(str2) ) {   // CORRETTO
   ...
}

Ciao.

[Mitch96]

Grazie mille! Bella osservazione! Ora sembra che funzioni!! Che stupido a non averci pensato prima
Comunque se magari volete utilizzare il codice, oltre all'errore di non averci messo l'equals, ho fatto quest'altro piccolo errore(quello in rosso, va cancellato)

while (!prioritario(opc,operatori.peek()) || !operatori.empty()) {nonPrioritario(operandi,operatori); if(operatori.empty()) break;}