[C] Trasformazione espressione in notazione infissa a postfissa (RPN)

[Krahos]

Da qualche giorno sbatto la testa sull'algoritmo che permette di ottenere un'espressione in notazione postfissa (o reverse polish notation) partendo da una stringa in notazione prefissa per creare una calcolatrice. In particolare vorrei che lavorasse anche e soprattutto con numeri in virgola mobile. Nonostante la teoria mi è abbastanza chiara faccio degli errori nell'implementazione (non mi da nemmeno errori di compilazione).

Riporto il codice:

void rpNotation (char *iString, char *oString) {
    int in = 0, out = 0;
    char tmpCh;
    stack lStack = stackInit (); /*la funzione si appoggia a uno stack creato da me a parte*/

    while ((tmpCh = iString [in]) != '\0') { /*salvo in tmpCh un carattere proveniente dalla stringa iString (in è un semplice indice)*/
    switch (tmpCh) {
    case '(':
        stackPush (lStack, tmpCh);
        break;

    case ')':
        tmpCh = stackPop (lStack);
        while (tmpCh != '(') {
        oString [out++] = tmpCh;
        tmpCh = stackPop (lStack);
        }
        break;

    case '+':
        while (showTop (lStack) != '(' || !stackEmpty (lStack)) {
        if (showTop (lStack) == '-' || '*' || '/') {
            oString [out] = ' ';
            out++;
            oString [out] = stackPop (lStack);
            out++;
        } else {
            stackPush (lStack, tmpCh);
            break;
        }
        }
        break;

    case '-':
        while (showTop (lStack) != '(' || stackEmpty (lStack)) {
            if (showTop (lStack) == '+' || '*' || '/') {
            oString [out] = ' ';
            out++;
            oString [out] = stackPop (lStack);
            out++;
        } else {
            stackPush (lStack, tmpCh);
            break;
        }
        }
        break;

    case '*':
        while (showTop (lStack) != '(' || stackEmpty (lStack)) {
        if (showTop (lStack) == '/') {
            oString [out] = ' ';
            out++;
            oString [out] = stackPop (lStack);
            out++;
        } else {
            stackPush (lStack, tmpCh);
            break;
        }
        }
        break;

    case '/':
        while (showTop (lStack) != '(' || stackEmpty (lStack)) {
        if (showTop (lStack) == '*') {
            oString [out] = ' ';
            out++;
            oString [out] = stackPop (lStack);
            out++;
        } else {
            stackPush (lStack, tmpCh);
            break;
        }
        }
        break;

    default:
        if (isdigit (tmpCh) || tmpCh == '.') {
        oString [out] = tmpCh;
        out++;
        }
    }

    in++;
    }
}

[Krahos]

partendo da una stringa in notazione prefissa

Naturalmente qui intendevo infissa.

[Vincenzo1968]

Puoi usare l'algoritmo operator precedence parsing per calcolare direttamente il risultato di un'espressione infissa senza doverla prima convertire in forma postfissa. Basta usare due stack: uno per gli operatori e uno per gli operandi:

https://github.com/Vincenzo1968/OperatorPrecedenceParsing

[Krahos]

Grazie, non conoscevo questo algoritmo, lo userò come alternativa nel caso in cui non riesca ad aggiustare il mio codice.

[Vincenzo1968]

Eventualmente puoi usare lo stesso algoritmo per trasformare l'espressione in notazione postfissa.
Usi un solo stack, per gli operatori. I numeri vanno direttamente nella stringa di output:

[Vincenzo1968]

Ho aggiunto la funzione calcolate che prende in input l'espressione postfissa e ne calcola il risultato:

[Rising1]

Mi inserisco un attimo nella discussione. Ho dato un'occhiata all'algoritmo proposto, ma mi sembra che potrebbe dare un po' di problemi nel caso ci siano numeri negativi. Esempio : 3+2*(-4+2) questa espressione genererebbe un errore. Meglio adottare un diverso algoritmo (un po' di tempo fa ne avevo usato uno un po' più lungo, che teneva conto di questo e altri casi) o fare qualche modifica a questo?

[Vincenzo1968]

No, i numeri negativi vengono gestiti correttamente:

[Krahos]

Grazie mille, mi è stato davvero utile. Invece a scopo didattico c'è qualcuno che abbia la pazienza di farmi capire cosa c'è di sbagliato nel mio codice?