[C] Esercizio notazione polacca inversa

Gead1

Nuovo Utente
2
0
Ciao, mi servirebbe una mano con questo programma che sto scrivendo, effettua l'espressione data in input in forma di notazione polacca inversa e restituisce il calcolo in complemento a 2 binario. Siccome devo farlo verificare dal compilatore dell'università ho dei test case, a me escono tutti senza problemi, sul sito dell'uni invece mi da " Execution killed with signal 11 (could be triggered by violating memory limits) " su questo test case:
2147483648 -1 * (Risultato: Overflow!)
2147483648 -1 * 1 - (Risultato: Overflow!)
1024 1024 * 1024 * -2 * (Risultato: -2147483648 in C2: 1000 0000 0000 0000 0000 0000 0000 0000)
1024 1024 * 1024 * 2 * (Risultato: Overflow!)
2147483647 1 + (Risultato: Overflow!)
2147483647 1 - (Risultato: 2147483646 in C2: 0111 1111 1111 1111 1111 1111 1111 1110)
fine

Il codice che ho scritto è il seguente:
C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define LENGHT 35

//Struttura che conterrà i valori delle espressioni
typedef struct n{
    int numero;
    struct n *nextPtr;
}Numeri;
typedef Numeri *numPtr;

//Dichiarazione funzioni
int acquisisci(char *stringa);
void azzera(numPtr *nPtr);
void concatena(numPtr *nPtr, short int val);
void newNum(numPtr *nPtr, short int val);
void calcolo(numPtr *nPtr, unsigned short int temp);
void stampa(numPtr *nPtr);
int controlloOverflow (int primo, int secondo, unsigned short int operazione);
void complemento2(int num);

//Variabili globali per controllare concatenazione e overflow
unsigned short int conc = 0;
unsigned short int ov = 0;

//Inizio main
int main()
{
    short int temp = 0;
    unsigned short int negativo = 0;
    char espressione[LENGHT]; //Variabile che conterrà l'espressione
    Numeri *nPtr = NULL; //Dichiarazione e inizializzazione puntatore

    while(acquisisci(espressione)){//Ripeto fin quando non trovo il valore "fine"
        //Azzero la lista ad ogni reiterazione del ciclo while
        azzera(&nPtr);

        //Analizzo ogni elemento dell'espressione
        for(size_t i = 0; i<strlen(espressione); i++){
            //Trasformo in int l'iesimo elemento dell'espressione
            temp = (int)espressione[i];

            //Se abbiamo un "-" seguito da un valore allora abbiamo un numero negativo
            if(temp == 45 && isdigit(espressione[i+1])){
                negativo = 1;
            }
            //Se abbiamo un valore intero
            else if(temp < 58 && temp > 47){
                temp = temp - '0'; //Convertiamo il valore dal suo codice ascii al suo reale valore
                if(conc == 1){//Concateniamo al numero letto in precedenza
                    concatena(&nPtr, temp);
                }else{ //Oppure creiamo un nuovo elemento in lista
                    if(negativo == 1){
                        temp *= -1;
                        negativo = 0;
                    }
                    newNum(&nPtr, temp);
                }
            }
            //Se il valore è un'operazione (+, - o *) chiamiamo la funzione calcolo
            else if(temp == 45 || temp == 43 || temp == 42){
                calcolo(&nPtr, temp);
            }else{//Altrimenti sarà uno spazio e quindi azzariamo conc
                conc = 0;
            }
        }
        //Stampiamo il risultato dopo aver analizzato l'espressione
        stampa(&nPtr);
    }
    //Azzeriamo definitivamente la lista
    azzera(&nPtr);

}
//Funzione per l'acquisizione della stringa da stdin
int acquisisci(char *stringa){
    fgets(stringa, LENGHT, stdin);
    stringa[strlen(stringa) - 1] = 0;
    if(strcmp(stringa, "fine")){//Se la stringa è "fine" allora restituiamo 1 per interrompere l'esecuzione
        return 1;
    }else{
        return 0;
    }
    while(getchar() != '\n');
}

//Funzione per azzerare la lista prima di una nuova conversione o alla fine del programma
void azzera(numPtr *nPtr){
    //Inizializziamo i puntatori necessari
    numPtr corrPtr = *nPtr;
    numPtr tempPtr = NULL;
    //Libero la memoria allocata per ogni puntatore fino all'ultimo
    while(corrPtr != NULL){
        tempPtr = corrPtr;
        corrPtr = corrPtr->nextPtr;
        free(tempPtr);
    }
    *nPtr = NULL;
}

//Funzione per inzializzare e inserire un nuovo elemento in lista
void newNum(numPtr *nPtr, short int val){
    //Inizializziamo i puntatori necessari
    numPtr corrPtr = *nPtr;
    numPtr precPtr = NULL;

    //Allochianmo la memoria per il nuovo nodo e il nuovo nodo
    numPtr nuovoPtr = malloc(sizeof(Numeri));
    if(nuovoPtr == NULL){
        puts("Memoria insufficiente!");
        exit(0);
    }
    nuovoPtr->numero = val;
    nuovoPtr->nextPtr = NULL;

    //Portiamoci all'ultimo elemento della lista
    while(corrPtr != NULL){
        precPtr = corrPtr;
        corrPtr = corrPtr->nextPtr;
    }
    //Se la lista è vuota la inizializziamo
    if(precPtr == NULL){
        nuovoPtr->nextPtr = *nPtr;
        *nPtr = nuovoPtr;
    }else{ //Altrimenti lo aggiungiamo in
        precPtr->nextPtr = nuovoPtr;
        nuovoPtr->nextPtr = corrPtr;
    }
    //Aggiunto un nuovo nodo, avvertiamo che i successivi valori saranno da concatenare
    conc = 1;
    return;
}
//Funzione per la concatenazione
void concatena(numPtr *nPtr, short int val){
    //Inizializziamo i puntatori e le variabili necessarie
    numPtr corrPtr = *nPtr;
    numPtr precPtr = NULL;
    int temp = 0;
    //Arrivo all'ultimo elemento in lista
    while(corrPtr != NULL){
        precPtr = corrPtr;
        corrPtr = corrPtr->nextPtr;
    }
    //Concateno il numero e controllo se faccia overflow il concatenamento
    if(precPtr->numero<0){
        temp = precPtr->numero;
        if(temp == -214748364 && val == 9){
            ov = 1;
        }else{
            precPtr->numero = (precPtr->numero * 10) - val;
        }
        if(temp<precPtr->numero){
            ov = 1;
        }
    }else{
        temp = precPtr->numero;
        if(temp == 214748364 && val>7){
            ov = 1;
        }else{
            precPtr->numero = (precPtr->numero * 10) + val;
            if(temp>precPtr->numero){
                ov = 1;
            }
        }

    }
    return;
}

//Funzione per il calcolo che svolge l'operazione con gli ultimi 2 numeri in lista
void calcolo(numPtr *nPtr, unsigned short int temp){
    numPtr corrPtr = *nPtr;
    numPtr precPtr = NULL;

    while(corrPtr->nextPtr != NULL){
        precPtr = corrPtr;
        corrPtr = corrPtr->nextPtr;
    }

    //Chiamo la funzione che controlla l'overflow e effettua l'operazione
    precPtr->numero = controlloOverflow(precPtr->numero, corrPtr->numero, temp);
    precPtr->nextPtr = NULL;
    free(corrPtr);//Liberiamo in nodo che non ci serve più
    return;
}

//Funzione per la stampa del valore finale e conversione in c2
void stampa(numPtr *nPtr){
    //Se abbiamo un overflow stampiamo l'errore
    if(ov == 1){
        puts("Overflow!");
        ov = 0;
        return;
    }
    numPtr corrPtr = *nPtr;
    //Stampiamo il valore e chiamiamo la funzione per il complemento a 2
    printf("%d in C2:  ", corrPtr->numero);
    complemento2(corrPtr->numero);
}

//Funzione per il controllo dell'overflow
int controlloOverflow (int primo, int secondo, unsigned short int operazione){
    int temp = 0;
    //Controllo overflow moltiplicazione
    if(operazione == 42){
        if(primo == 0 || secondo == 0){//Se abbiamo uno "0" allora la moltiplicazione farà 0
            return 0;
        }
        if(primo>0){
            if(secondo>0){
                if(primo > (temp = primo*secondo) ){//Se i 2 numeri sono > 0 e temp < primo allora abbiamo overflow
                    ov = 1;
                }
            }else{//Primo > 0 e secondo < 0
                if(primo < (temp = primo*secondo)){//Se primo è minore della molt. allora abbiamo overflow
                    ov = 1;
                }
            }
        }else{
            if(secondo > 0){ //Primo min 0 e sec magg 0
                if(primo < (temp = primo*secondo)){//Se primo < operazione allora abbiamo overflow
                    ov = 1;
                }
            }else{//Anche secondo minore di 0
                if(primo > (temp = primo*secondo) ){//Se primo > operazione allora overflow
                    ov = 1;
                }
            }
        }
    }
    //Controllo overflow somma
    else if(operazione == 43){
        //Se l'operazione è una somma e uno dei due valori è 0 allora restituiamo l'altro valore
        if(primo == 0){
            return secondo;
        }else if(secondo == 0){
            return primo;
        }
        if(primo>0){
            if(secondo>0){//Primo e secondo > 0
                if(primo > (temp = primo + secondo)){//Se primo > somma allora overflow
                    ov = 1;
                }
            }
        }else{
            if(secondo > 0){//Eseguiamo l'operazione perchè non può esserci overflow
                temp = primo + secondo;
            }else{
                if(primo < (temp = primo + secondo)){//Se sec < 0 e primo < somma allora overflow
                    ov = 1;
                }
            }
        }
    }
    //Controllo overflow sottrazione
    else if(operazione == 45){
        //Nella sottrazione, se il secondo valore è 0 possiamo ritornare direttamente il primo
        if(secondo == 0){
            return primo;
        }
        if(primo >= 0){
            if(secondo>0){//Primo e secondo > 0 eseguiamo sottrazione
                temp = primo - secondo;
            }else{//Secondo minore 0 controlliamo overflow
                if(primo >= (temp = primo - secondo)){
                    ov = 1;
                }
            }
        }else{
            if(secondo >= 0){//Primo >= 0, secondo < 0 controlliamo overflow
                if(primo < (temp = primo - secondo)){
                    ov = 1;
                }
            }else{//Secondo < 0 eseguiamo sottrazione perchè non può essere overflow
                temp = primo - secondo;
            }
        }
    }
    return temp;
}
//Funzione per effettuare il complemento a 2
void complemento2(int num){

    unsigned short int numconv[32];
    unsigned short int cont=31;
    unsigned short int spazi=0;
    size_t neg=0;
    size_t riporto=0;

    if(num==1){
        printf("0000 0000 0000 0000 0000 0000 0000 0001");
        return;
    }
    if(num==0){
        printf("0000 0000 0000 0000 0000 0000 0000 0000");
        return;
    }
    if(num<0){
        neg=1;
        num *= -1;
    }
    for(int i=0; i<=cont; i++){
            numconv[i]=0;
    }
    while(num>0){
        numconv[cont]=num%2;
        cont--;
        num=num/2;
    }
    if(neg==1){
        for(int i=0; i<32; i++){
            if(numconv[i]==0){
                numconv[i]=1;
            }
            else if(numconv[i]==1){
                numconv[i]=0;
            }
        }
        for(int k=31; k>=0; k--){
            if(k==31){
                numconv[k] += 1;
                if(numconv[k]==2){
                    riporto=1;
                    numconv[k]=0;
                }
            }else{
                if(riporto==1 && numconv[k]==0){
                    numconv[k]=1;
                    riporto=0;
                }else if(riporto==1 && numconv[k]==1){
                    numconv[k]=0;
                    riporto=1;
                }
            }
        }
        numconv[0]=1;
    }
    for(size_t i=0; i<32; i++){
        printf("%d", numconv[i]);
        spazi++;
        if(spazi==4){
            printf(" ");
            spazi=0;
        }

    }
    printf("\n");
}
 

Andretti60

Utente Èlite
6,440
5,091
Beh, l’errore è chiaro, stai usando una locazione di memoria che non è inizializzata.

Una prima occhiata al tuo codice mostra subito un grosso problema, ossia l’uso di variabili globali, che se non sono assegnate correttamente causano errori catastrofici, nel tuo caso la variabile “conc” che è inutile in quanto il test sulla lista va fatto sul suo primo elemento (se è NULL la lista è vuota). Il tuo programma non azzera “conc” all’inizio di ogni iterazione.

Come regola generale, variabili globali vanno usate (nei linguaggi che le accettano) solo per dati che sono costanti, MAI usarle per memorizzare lo stato del programma.
 
U

Utente cancellato 371741

Ospite
Non ho il tempo di trovare il problema preciso, compilato stesso test case qui
non da problemi. Per trovare il problema facilmente sulla macchina dove lo da,

Codice:
gcc -ggdb -o binario main.c

gdb ./binario
run


Come regola generale, variabili globali vanno usate (nei linguaggi che le accettano) solo per dati che sono costanti, MAI usarle per memorizzare lo stato del programma.
variabili globali sono perfettamente lecite in C ,
e usate spesso anche per tenere conto di stati. Vedi molti esempi nel
kernel linux. I'importante e' sapere sempre quello che si fa e impostare
bene le cose.

Alcuni suggerimenti:

1) variabili globali non serve inizializzarle a 0, lo saranno comunque.
2) stringa[strlen(stringa) - 1] = 0; non serve, input gia zero terminato
3) in stampa corrPtr potrebbe essere nullo, va protetto (digita inizialmente una seplice striga e dai invio)

adesso ora di andare a nanna
Saluti
 
  • Mi piace
Reazioni: Andretti60

Andretti60

Utente Èlite
6,440
5,091
variabili globali sono perfettamente lecite in C ,
essere lecito non significa che bisogna farlo. Puoi usare una variabile globale perfino come contatore di un ciclo, è perfettamente lecito, ma lo faresti?
ed è per questo che il C ormai è usato solo da sviluppatori con esperienza, troppe cose sono lecite (non per nulla il C è evoluto nella versione ANSI dove perlomeno si può dichiarare i prototipi delle funzione, tra le altre restrizioni) e si finisce con lo scrivere “spaghetti code”. Non c’è poi da stupirsi se molti che imparano a programmare in C poi si trovano in difficoltà con i linguaggi evoluti dove le variabili globali non sono nemmeno ammesse.
Post unito automaticamente:

2) stringa[strlen(stringa) - 1] = 0; non serve, input gia zero terminato
Vero, ma fgets (se non ci sono errori) lascia il carattere newline nel vettore, se dá problemi con il parsing della stringa è meglio eliminarlo fin dal principio.
 
Ultima modifica:
U

Utente cancellato 371741

Ospite
essere lecito non significa che bisogna farlo. Puoi usare una variabile globale perfino come contatore di un ciclo, è perfettamente lecito, ma lo faresti?
ed è per questo che il C ormai è usato solo da sviluppatori con esperienza, troppe cose sono lecite (non per nulla il C è evoluto nella versione ANSI dove perlomeno si può dichiarare i prototipi delle funzione, tra le altre restrizioni) e si finisce con lo scrivere “spaghetti code”. Non c’è poi da stupirsi se molti che imparano a programmare in C poi si trovano in difficoltà con i linguaggi evoluti dove le variabili globali non sono nemmeno ammesse.

Suvvia dai, fondamentale e' sempre se "si sa quel che si fa".
Come una variabile mostly_read, scritta in pochi punti e letta in molti.

Si, talvolta le uso anche in semplici tool, in genere con uno static davanti,
inutile sprecare tempo a passar variabili alle funzioni se non serve.

Spaghetti code: non so se mi da piu fastitdio lo spaghetti code, che a volte
e' orribile ma funziona perfettamente, dell'offuscamento o cargo-cult,
che piace tanto a certi ingegneri, che vogliono prevalere sui colleghi,
e dimostrare superiorita a scopi carrieristici,
utilizzando tecniche inutilmente complesse in situazioni dove la complessita' non
serve affatto. E dove poi si trovano bug comunque.

Perche alle universita' si ostinano a insegnare il C se ci sono tutti questi
fomidabili scripting di "alto" livello (non esenti da speaghetti code) ?
Perche non esiste solo x86_64. Ma centinaia di architetture, tra von newmann,
harvard e molti ibridi tra le due. Se uno si orienta sul settore embedded
il C e' ovunque, specie nei micro 8 bit, ed e' _fondamentale_. In piu si usa perche'
essendo a basso livello fa capire qualcosa di quello che avviene tra cpu e
memoria, piuttosto che partire di python e non capire nulla di quello che avviene
sotto.


Vero, ma fgets (se non ci sono errori) lascia il carattere newline nel vettore, se dá problemi con il parsing della stringa è meglio eliminarlo fin dal principio.
ok, cmq per come lui ha scritto il loop iniziale, terminare a 0 sopra \n mi pare non cambi nulla rispetto al non farlo. Pr altro il \n viene aggiunto anche in caso di input maggiore di LENGTH quindi si puo anche cercare il '\n' finale.
 
Ultima modifica da un moderatore:

Andretti60

Utente Èlite
6,440
5,091
...
utilizzando tecniche inutilmente complesse in situazioni dove la complessita' non
serve affatto. E dove poi si trovano bug comunque.
Due punti qui.
Primo, l’utente qui non sta scrivendo codice commerciale, lo fa per imparare. Sono cose molto diverse. Quando si studia occorre imparare le “buone” abitudini e le tecniche di programmazione, altrimenti si può benissimo scrivere due programmi in croce a casa senza bisogno di spendere tempo a scuola. Sul lavoro il discorso è diverso e dipende dal progetto su cui si sta lavorando.
Secondo, Vero che i bug si trovano ovunque, ma sono molto più facili da trovare in un codice ben strutturato. Infatti una domanda classica che si fa durante i colloqui di assunzione è “meglio un codice scritto male che funziona o uno scritto bene che non funziona”.
Post unito automaticamente:

...
Pr altro il \n viene aggiunto anche in caso di input maggiore di LENGTH quindi si puo anche cercare il '\n' finale.
Sono secoli che non uso fgets(), ma che mi ricordi (e il manuale lo conferma) la lettura dello stream termina appena o si raggiunge la fine dello stream, o il carattere di ritorno o la lunghezza della stringa (proprio per evitare overflow, che può succedere invece nella “sorella” gets(), che è deprecata)
 
Ultima modifica:
U

Utente cancellato 371741

Ospite
Sono d'accordo, programmare bene anche per hobby, certo. Ma sconsigloiare l'uso di globali e' profondamente sbagliato. Avvisare dei rischi, ok. Una policy simile potrebbe aver senso in qualche azienda che si vuole proteggere da completi inesperti. Aziende hanno sempre un code review, e a volte, il solito capetto in cravatta che nessuno ha nominato capo istituisce regole inutili, ne ho visti tanti.

I colloqui d'assunzione sono sempre una scommessa, non si sa mai come va finire, a volte uno che sembrava un idiota si rivela svegilo, e viceversa un venditore di vaporware poi risulta imbranato pignolo prolisso e poco redditizio, a volte un giovane inesperto puo esere capace di risolvere rapidamente problemi complessi meglio di uno che ha molti anni di esperienza.
 

Andretti60

Utente Èlite
6,440
5,091
L’uso di variabili globali è “sempre” sconsigliato. Punto. Specie quando è possibile evitarle. Non per nulla non sono ammesse in certi linguaggi di programmazione. Ti potrei elencare dozzine di motivi e non accademici, tutti esempi su cui mi sono scontrato nella mia carriera (che sta volgendo al fine).
Post unito automaticamente:

variabili globali sono perfettamente lecite in C ,
e usate spesso anche per tenere conto di stati. Vedi molti esempi nel
kernel linux.
In seguito Hai postato una pagina di codice del kernel Linux, ma non contiene alcuna variabile globale. Ti spiace trovarne una che ne faccia uso? Grazie, sono curioso.
 
Ultima modifica:
U

Utente cancellato 371741

Ospite
L’uso di variabili globali è “sempre” sconsigliato. Punto. Specie quando è possibile evitarle. Non per nulla non sono ammesse in certi linguaggi di programmazione. Ti potrei elencare dozzine di motivi e non accademici, tutti esempi su cui mi sono scontrato nella mia carriera (che sta volgendo al fine).
Post unito automaticamente:


In seguito Hai postato una pagina di codice del kernel Linux, ma non contiene alcuna variabile globale. Ti spiace trovarne una che ne faccia uso? Grazie, sono curioso.
Uno che sconsiglia variabili globali non sa' programmare. Instaura contenziosi bambineschi pur di avere ragione, su inutili medaglie.
"Punto" e' anche dimostrazione di cafonaggine.
Il thread aveva un senso piu alto, aiutare una persona, peche hai voluto litigare poi non so.

Link kernel punta a una linea con system_state, forse non le sai riconoscere.

Non ti rispondo piu. Saluti.
 

sp3ctrum

Amministratore
Staff Forum
15,961
7,809
CPU
AMD Ryzen 5 3900X
Dissipatore
Scythe Mugen 5 rev.b Push&Pull
Scheda Madre
ASUS TUF Gaming B550M-Plus WIFI
HDD
Nvme Samsung EVO 1Tb + SSD Samsung evo 850 250gb + Toshiba P300 3Tb
RAM
HyperX FURY 16gb 3200Mhz
GPU
ASUS Dual GeForce RTX 4070 OC White Edition 12GB GDDR6X
Audio
Topping DX3 Pro + Focusrite Scarlett 2i2 + Mackie MR524 + Beyer DT 770 Pro + Presonus SubWoofer
Monitor
LG Ultragear 27gp850
PSU
Corsair RM850x 80 PLUS Gold
Case
Thermaltake V200 RGB
Net
Vodafone 1000Mb
OS
Windows 11 Pro
Uno che sconsiglia variabili globali non sa' programmare. Instaura contenziosi bambineschi pur di avere ragione, su inutili medaglie.
"Punto" e' anche dimostrazione di cafonaggine.
Il thread aveva un senso piu alto, aiutare una persona, peche hai voluto litigare poi non so.

Link kernel punta a una linea con system_state, forse non le sai riconoscere.

Non ti rispondo piu. Saluti.

Si puó benissimo discutere senza andare sul personale e senza offendere nessuno, cerca di evitare offese gratuite.
 

Andretti60

Utente Èlite
6,440
5,091
@Gead1 (great nickname BTW)
Ieri ho avuto tempo di provare il tuo programma, che funziona bene anche a me. Sei sicuro che lo hai trasferito correttamente nel computer scolastico? Sei sicuro di avere immesso i dati correttamente? Quando ti dà errore, al primo passo, in alcuni o in tutti?

Il tuo codice mi pare ben strutturato, se posso dare un consiglio è di implementare la lista di tipo LIFO in quanto è proprio quella che si usa per la notazione polacca inversa (dove il primo operando che si usa è l’ultimo a essere immesso), ti semplifica il codice non poco.
 
U

Utente cancellato 371741

Ospite
Si puó benissimo discutere senza andare sul personale e senza offendere nessuno, cerca di evitare offese gratuite.
Vorrei che mi quotassi dove ho offeso. Offesa e' un insulto diretto alla persona, che non ho espresso. Io e Andretti abbiamo gia chiarito la question in pvt. Se come moderatore ritieni che io abbia "offeso", confermalo, e chiudo l'account.
 

BAT

Moderatore
Staff Forum
Utente Èlite
22,668
11,452
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
Io e Andretti abbiamo gia chiarito la question in pvt.
Avendo chiarito tra di voi va bene così. ?
L'equivoco era nato in quanto un messaggio precedente era stato segnalato con il pulsante "Segnala".
Avendo tutto risolto continuiamo a parlare di programmazione. ?
 
  • Mi piace
Reazioni: Mursey

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili