Étude de cas : évaluation d'expressions

Les piles peuvent être utilisées pour évaluer des expressions. Les piles et les files d'attente ont de nombreuses applications. Cette section présente une application qui utilise des piles pour évaluer des expressions. Vous pouvez saisir une expression arithmétique de Google pour évaluer l'expression, comme le montre la figure ci-dessous.

Comment Google évalue-t-il une expression ? Cette section présente un programme qui évalue une expression composée avec plusieurs opérateurs et parenthèses (par exemple, (15 + 2) * 34 – 2). Pour plus de simplicité, supposons que les opérandes sont des entiers et que les opérateurs sont de quatre types : +, -, ** et */.

Le problème peut être résolu en utilisant deux piles, nommées operandStack et operatorStack, pour stocker respectivement les opérandes et les opérateurs. Les opérandes et les opérateurs sont placés dans les piles avant d'être traités. Lorsqu'un opérateur est traité, il est extrait de operatorStack et appliqué aux deux premiers opérandes de operandStack (les deux opérandes sont extraits de operandStack). La valeur résultante est repoussée vers operandStack.

L'algorithme se déroule en deux phases :

Phase 1 : analyse de l'expression

Le programme analyse l'expression de gauche à droite pour extraire les opérandes, les opérateurs et les parenthèses.

1. Si l'élément extrait est un opérande, poussez-le vers operandStack.
2. Si l'élément extrait est un opérateur + ou -, traitez tous les opérateurs en haut de operatorStack et poussez l'opérateur extrait vers opérateurStack.
3. Si l'élément extrait est un opérateur ***** ou /, traitez les opérateurs ***** ou / en haut de operatorStack et poussez l'opérateur extrait vers operatorStack.
4. Si l'élément extrait est un symbole (, poussez-le vers operatorStack.
5. Si l'élément extrait est un symbole ), traitez à plusieurs reprises les opérateurs depuis le haut de operatorStack jusqu'à voir le symbole ( sur la pile.

Phase 2 : vider la pile

Traitez à plusieurs reprises les opérateurs depuis le haut de operatorStack jusqu'à ce que operatorStack soit vide.

Le tableau ci-dessous montre comment l'algorithme est appliqué pour évaluer l'expression (1 + 2) * 4 - 3.

Le code ci-dessous donne le programme et la figure ci-dessous montre un exemple de sortie.

package demo;
import java.util.Stack;

public class EvaluateExpression {

    public static void main(String[] args) {
        // Check number of arguments passed
        if(args.length != 1) {
            System.out.println("Usage: java EvaluateExpression \"expression\"");
            System.exit(1);
        }

        try {
            System.out.println(evaluateExpression(args[0]));
        }
        catch(Exception ex) {
            System.out.println("Wrong expression: " + args[0]);
        }
    }

    /** Evaluate an expression */
    public static int evaluateExpression(String expression) {
        // Create operandStack to store operands
        Stack<Integer> operandStack = new Stack<>();

        // Create operatorStack to store operators
        Stack<Character> operatorStack = new Stack<>();

        // Insert blanks around (, ), +, -, /, and *
        expression = insertBlanks(expression);

        // Extract operands and operators
        String[] tokens = expression.split(" ");

        // Phase 1: Scan tokens
        for(String token: tokens) {
            if(token.length() == 0) // Blank space
                continue; // Back to the while loop to extract the next token
            else if(token.charAt(0) == '+' || token.charAt(0) == '-') {
                // Process all +, -, *, / in the top of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '+' || operatorStack.peek() == '-' || operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(operandStack, operatorStack);
                }

                // Push the + or - operator into the operator stack
                operatorStack.push(token.charAt(0));
            }
            else if(token.charAt(0) == '*' || token.charAt(0) == '/') {
                // Process all *, / in the top of the operator stack
                while(!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')) {
                    processAnOperator(operandStack, operatorStack);
                }

                // Push the * or / operator into the operator stack
                operatorStack.push(token.charAt(0));
            }
            else if(token.trim().charAt(0) == '(') {
                operatorStack.push('('); // Push '(' to stack
            }
            else if(token.trim().charAt(0) == ')') {
                // Process all the operators in the stack until seeing '('
                while(operatorStack.peek() != '(') {
                    processAnOperator(operandStack, operatorStack);
                }

                operatorStack.pop(); // Pop the '(' symbol from the stack
            }
            else {
                // Push an operand to the stack
                operandStack.push(Integer.valueOf(token));
            }
        }

        // Phase 2: Process all the remaining operators in the stack
        while(!operatorStack.isEmpty()) {
            processAnOperator(operandStack, operatorStack);
        }

        // Return the result
        return operandStack.pop();
    }

    /** Process one operator: Take an operator from operatorStack and apply it on the operands in the operandStack */
    public static void processAnOperator(Stack<Integer> operandStack, Stack<Character> operatorStack) {
        char op = operatorStack.pop();
        int op1 = operandStack.pop();
        int op2 = operandStack.pop();
        if(op == '+')
            operandStack.push(op2 + op1);
        else if(op == '-')
            operandStack.push(op2 - op1);
        else if(op == '*')
            operandStack.push(op2 * op1);
        else if(op == '/')
            operandStack.push(op2 / op1);
    }

    public static String insertBlanks(String s) {
        String result = "";

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '(' || s.charAt(i) == ')' || s.charAt(i) == '+' || s.charAt(i) == '-' || s.charAt(i) == '*' || s.charAt(i) == '/')
                result += " " + s.charAt(i) + " ";
            else
                result += s.charAt(i);
        }

        return result;
    }

}

Vous pouvez utiliser la classe GenericStack fournie par le livre ou la classe java.util.Stack définie dans l'API Java pour créer des piles. Cet exemple utilise la classe java.util.Stack. Le programme fonctionnera s'il est remplacé par GenericStack.

Le programme prend une expression comme argument de ligne de commande dans une seule chaîne.

La méthode evaluateExpression crée deux piles, operandStack et operatorStack (lignes 24, 27), et extrait les opérandes, les opérateurs et les parenthèses délimités par des espaces ( lignes 30 à 33). La méthode insertBlanks est utilisée pour garantir que les opérandes, les opérateurs et les parenthèses sont séparés par au moins un espace (ligne 30).

Le programme analyse chaque jeton dans la boucle for (lignes 36 à 72). Si un jeton est vide, sautez-le (ligne 38). Si un jeton est un opérande, poussez-le vers operandStack (ligne 70). Si un jeton est un opérateur + ou – (ligne 39), traitez tous les opérateurs du haut de operatorStack, le cas échéant (lignes 41 à 43) , et poussez l'opérateur nouvellement numérisé dans la pile (ligne 46). Si un jeton est un opérateur ***** ou / (ligne 48), traitez tous les opérateurs ***** et / du haut de operatorStack, le cas échéant (lignes 50 à 51), et poussez l'opérateur nouvellement numérisé vers la pile (ligne 55). Si un jeton est un symbole ( (ligne 57), poussez-le dans operatorStack. Si un jeton est un symbole ) (ligne 60), traitez tous les opérateurs du haut de operatorStack jusqu'à voir le symbole ) (lignes 62 à 64) et faites apparaître le symbole ) de la pile.

Une fois tous les jetons pris en compte, le programme traite les opérateurs restants dans operatorStack (lignes 75 à 77).

La méthode processAnOperator (lignes 84 à 96) traite un opérateur. La méthode extrait l'opérateur de operatorStack (ligne 85) et extrait deux opérandes de operandStack (lignes 86 à 87). En fonction de l'opérateur, la méthode effectue une opération et repousse le résultat de l'opération vers operandStack (lignes 89, 91, 93, 95).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!