Les piles (ou stacks) sont des structures de données fondamentales en informatique, suivant le prnicipe LIFO (Last-In, First-Out), c'est-à-dire que le dernier élément ajouté est le premier à être retiré. Elles sont couramment utilisées pour gérer la mémoire des appels de fonctions, l'analyse syntaxique de code, et bien sûr, l'évaluation d'expressions arithmétiques. Cet article détaille l'application des piles pour évaluer deux formes distinctes d'expressions : les expressions infixées (avec gestion des parenthèses et des priorités) et les expressions postfixées (Notation Polonaise Inverse).

Évaluation d'Expressions Infixées (avec gestion des parenthèses et priorités)

L'évaluation d'une expression infixée, telle que (3 + 5) * 2 - 1, est complexe en raison de la nécessité de respecter les règles de priorité des opérateurs (multiplication et division avant addition et soustraction) et de gérer les parenthèses qui modifient cet ordre. Une méthode efficace pour résoudre ce problème implique l'utilisation de deux piles : une pour stocker les opérandes (nombres) et une autre pour les opérateurs.

L'algorithme de base se déroule comme suit :

1. Parcourez l'expression caractère par caractère de gauche à droite.
2. Si le caractère est un chiffre, construisez le nombre entier (qui peut être multi-chiffres) et empilez-le sur la pile des opérandes.
3. Si le caractère est une parenthèse ouvrante (, empilez-la sur la pile des opérateurs.
4. Si le caractère est une parenthèse fermante ) : Tant que le sommet de la pile des opérateurs n'est pas une parenthèse ouvrante, exécutez l'opération au sommet. Une fois la parenthèse ouvrante atteinte, dépilez-la (sans l'exécuter).
5. Si le caractère est un opérateur (+, -, *, /) : Tant que la pile des opérateurs n'est pas vide, que son sommet n'est pas une parenthèse ouvrante et que l'opérateur au sommet a une priorité supérieure ou égale à celle de l'opérateur courant, exécutez l'opération au sommet. Ensuite, empilez l'opérateur courant.
6. Après avoir traversé toute l'expression, continuez à exécuter les opérations restantes dans la pile des opérateurs jusqu'à ce qu'elle soit vide.

Le résultat final sera le seul élément restant dans la pile des opérandes.

#include <iostream>
#include <string>
#include <stack>
#include <map>
#include <cctype> // Pour la fonction isdigit

// Définit les niveaux de priorité pour chaque opérateur
std::map<char, int> niveauxPriorite = {
    {'+', 1}, {'-', 1},
    {'*', 2}, {'/', 2}
};

std::stack<int> pileOperandes;      // Pile destinée aux valeurs numériques
std::stack<char> pileOperateurs;    // Pile destinée aux symboles d'opérateurs

// Effectue une opération en utilisant les éléments au sommet des piles
void effectuerCalcul() {
    // Les opérandes sont dépilés dans l'ordre inverse de leur apparition
    int operandeDroit = pileOperandes.top(); pileOperandes.pop();
    int operandeGauche = pileOperandes.top(); pileOperandes.pop();
    char operateurCourant = pileOperateurs.top(); pileOperateurs.pop();
    
    int resultatOperation;
    switch (operateurCourant) {
        case '+': resultatOperation = operandeGauche + operandeDroit; break;
        case '-': resultatOperation = operandeGauche - operandeDroit; break;
        case '*': resultatOperation = operandeGauche * operandeDroit; break;
        case '/': resultatOperation = operandeGauche / operandeDroit; break; // Division entière
        default: return; // Cas inattendu pour un opérateur
    }
    pileOperandes.push(resultatOperation);
}

int main() {
    std::string expressionFournie;
    std::cin >> expressionFournie; // Lit l'expression infixée depuis l'entrée standard
    
    for (int i = 0; i < expressionFournie.length(); ++i) {
        char elementActuel = expressionFournie[i];
        
        if (isdigit(elementActuel)) {
            // Reconstruit un nombre entier qui peut avoir plusieurs chiffres
            int valeurNum = 0;
            int j = i;
            while (j < expressionFournie.length() && isdigit(expressionFournie[j])) {
                valeurNum = valeurNum * 10 + (expressionFournie[j] - '0');
                j++;
            }
            pileOperandes.push(valeurNum);
            i = j - 1; // Ajuste l'index de la boucle principale
        } else if (elementActuel == '(') {
            pileOperateurs.push(elementActuel);
        } else if (elementActuel == ')') {
            // Évalue les opérations jusqu'à atteindre la parenthèse ouvrante correspondante
            while (!pileOperateurs.empty() && pileOperateurs.top() != '(') {
                effectuerCalcul();
            }
            pileOperateurs.pop(); // Retire la parenthèse ouvrante de la pile
        } else { // L'élément est un opérateur
            // Exécute les opérations si l'opérateur au sommet de la pile est de priorité supérieure ou égale
            while (!pileOperateurs.empty() && pileOperateurs.top() != '(' &&
                   niveauxPriorite[pileOperateurs.top()] >= niveauxPriorite[elementActuel]) {
                effectuerCalcul();
            }
            pileOperateurs.push(elementActuel); // Ajoute l'opérateur actuel à sa pile
        }
    }
    
    // Une fois toute l'expression parcourue, exécute toutes les opérations restantes
    while (!pileOperateurs.empty()) {
        effectuerCalcul();
    }
    
    // Le résultat final de l'expression est le dernier élément de la pile des opérandes
    std::cout << pileOperandes.top() << std::endl;
    
    return 0;
}

Évaluation d'Expressions Postfixées (Notation Polonaise Inverse - NPI)

Les expressions postfixées, aussi appelées Notation Polonaise Inverse (NPI), représentent les opérations de manière plus simple que les expressions infixées. L'avantage principal est qu'elles ne nécessitent ni parenthèses ni règles de priorité d'opérateurs, ce qui simplifie grandement leur évaluation par un ordinateur. Par exemple, l'expression infixée (3 + 5) * 2 - 1 se traduit en NPI par 3 5 + 2 * 1 -.

L'évlauation d'une expression NPI est directe et utilise une seule pile pour les opérandes :

1. Parcourez l'expression de gauche à droite.
2. Si vous rencontrez un nombre, empilez-le sur la pile.
3. Si vous rencontrez un opérateur, dépilez les deux derniers nombres de la pile, effectuez l'opération avec ces deux nombres (le premier dépilé est l'opérande droit, le second est l'opérande gauche), puis empilez le résultat de cette opération sur la pile.
4. Lorsque l'expression est entièrement parcourue, le seul nombre restant dans la pile est le résultat final.

Le fragment de code C++ suivant illustre cette logique pour une expression NPI où les nombres sont séparés par un point . et l'expression se termine par le symbole @.

#include <iostream>
#include <stack>
#include <cctype> // Pour la fonction isdigit

int main() {
    std::stack<int> pileValeurs;
    int accumulateurNumerique = 0; // Sert à construire les nombres multi-chiffres
    char symboleCourant;

    // Lit les symboles un par un jusqu'à ce que le marqueur de fin '@' soit rencontré
    while (std::cin >> symboleCourant && symboleCourant != '@') {
        if (isdigit(symboleCourant)) {
            // Accumule les chiffres pour former un nombre complet
            accumulateurNumerique = accumulateurNumerique * 10 + (symboleCourant - '0');
        } else if (symboleCourant == '.') {
            // Le point '.' indique la fin d'un nombre, qui est alors poussé sur la pile
            pileValeurs.push(accumulateurNumerique);
            accumulateurNumerique = 0; // Réinitialise l'accumulateur pour le prochain nombre
        } else { // Le symbole est un opérateur (+, -, *, /)
            // Récupère les deux opérandes nécessaires à l'opération (ordre LIFO)
            int operandeDeux = pileValeurs.top(); pileValeurs.pop();
            int operandeUn = pileValeurs.top(); pileValeurs.pop();
            
            int resultatTemporaire;
            switch (symboleCourant) {
                case '+': resultatTemporaire = operandeUn + operandeDeux; break;
                case '-': resultatTemporaire = operandeUn - operandeDeux; break;
                case '*': resultatTemporaire = operandeUn * operandeDeux; break;
                case '/': resultatTemporaire = operandeUn / operandeDeux; break;
                default:
                    // En compétition, on suppose souvent que l'entrée est toujours valide
                    break; 
            }
            pileValeurs.push(resultatTemporaire); // Empile le résultat de l'opération
        }
    }
    
    // Le résultat final de l'expression se trouve au sommet de la pile
    std::cout << pileValeurs.top() << std::endl;
    
    return 0;
}