Évaluer une expression postfixée

/* Evalue l'expression postfixee s. Renvoie true et range la valeur dans
   *res si l'expression est bien formee, false sinon.
   Precondition : s est une chaine valide ; les operandes sont des chiffres. */
bool evalue(const char* s, int* res) {
    int t[64]; int n = 0;                       /* la pile des operandes */
    for (int i = 0; s[i] != '\0'; i = i + 1) {
        char c = s[i];
        if (c == ' ') { continue; }
        if (c >= '0' && c <= '9') {
            if (n >= 64) { return false; }
            t[n] = c - '0'; n = n + 1;
        } else {
            if (n < 2) { return false; }        /* pas assez d'operandes */
            int b = t[n-1], a = t[n-2]; n = n - 2;
            int v;
            if      (c == '+') { v = a + b; }
            else if (c == '-') { v = a - b; }
            else if (c == '*') { v = a * b; }
            else if (c == '/') { if (b == 0) { return false; } v = a / b; }
            else { return false; }              /* symbole inconnu */
            t[n] = v; n = n + 1;
        }
    }
    if (n != 1) { return false; }               /* trop d'operandes */
    *res = t[0];
    return true;
}

Mesuré :

"3 4 +"              ->  7
"3 4 + 2 *"          -> 14
"5 1 2 + 4 * + 3 -"  -> 14        c'est 5 + (1+2)*4 - 3
"3 +"                -> REFUSEE   pile trop courte
"3 4"                -> REFUSEE   deux valeurs restent a la fin
"8 0 /"              -> REFUSEE   division par zero

L'invariant est la clé de la preuve : après avoir lu un préfixe de l'expression, la pile contient, du fond vers le sommet, les valeurs des sous-expressions complètes déjà rencontrées. Il est vrai au départ (pile vide), il est préservé par un opérande (une sous-expression de plus, réduite à elle-même) et par un opérateur (deux sous-expressions remplacées par une). À la fin, l'expression est bien formée si et seulement s'il reste exactement une valeur.

Les deux refus symétriques sont le cœur de l'exercice. Une pile trop courte au moment d'un opérateur signale un opérateur en trop ; une pile de taille $\ne 1$ à la fin signale des opérandes en trop. Un seul des deux tests ne suffit pas : "3 4" passe le premier et échoue au second, "3 +" l'inverse.

L'ordre des opérandes est le piège d'écriture. Le sommet est le second opérande : on lit b = t[n-1] puis a = t[n-2], et l'on calcule a - b. L'inverser rend l'addition et la multiplication justes, et la soustraction et la division fausses — une faute qui passe donc la moitié des tests, ce qui la rend d'autant plus dangereuse.

Complexité : un seul parcours, $\Theta (|s|)$ en temps ; en espace, la pile atteint la profondeur maximale d'imbrication de l'expression. C'est la même structure que la pile d'exécution du chapitre chap:recursivite, et le chapitre chap:arbres montrera que la notation postfixée est exactement le parcours suffixe de l'arbre de l'expression.