Comment l'algorithme Shunting Yard peut-il simplifier l'évaluation des expressions mathématiques en PHP ?

Créer une calculatrice en PHP

Simplifier les expressions mathématiques saisies dans un la balise en PHP peut être difficile, surtout lorsqu'il s'agit de préserver la notation originale. Bien qu'une approche par force brute consistant à remplacer les chaînes par des valeurs calculées semble viable au départ, elle devient inefficace.

Utilisation de l'algorithme Shunting Yard

Une solution plus efficace est l'algorithme Shunting Algorithme de cour. Il convertit les expressions d'entrée en notation polonaise inversée (RPN). RPN simplifie les calculs car les opérandes sont immédiatement suivis par leurs opérateurs.

Exemple d'implémentation

Le code suivant fournit une implémentation de l'algorithme Shunting Yard en PHP :

class Expression {

    protected $tokens;
    protected $output;

    // Shunting Yard Algorithm
    public function shuntingYard($input) {
        $stack = [];
        $tokens = $this->tokenize($input);
        foreach ($tokens as $token) {
            if (is_numeric($token)) {
                $this->output[] = $token;
            } else {
                switch ($token) {
                    case '(':
                        $stack[] = $token;
                        break;
                    case ')':
                        while ($stack && end($stack) != '(') {
                            $this->output[] = array_pop($stack);
                        }
                        if (!empty($stack)) {
                            array_pop($stack);
                        }
                        break;
                    default:
                        while ($stack && $this->precedence($token) <= $this->precedence(end($stack))) {
                            $this->output[] = array_pop($stack);
                        }
                        $stack[] = $token;
                        break;
                }
            }
        }
        while (!empty($stack)) {
            $this->output[] = array_pop($stack);
        }
    }

    // Tokenize the input
    public function tokenize($input) {
        preg_match_all('~\d+|~|~U', $input, $tokens);
        return $tokens[0];
    }

    // Operator precedence
    public function precedence($operator) {
        switch ($operator) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                return 0;
        }
    }

    // Evaluate the RPN expression
    public function evaluate() {
        $stack = [];
        foreach ($this->output as $token) {
            if (is_numeric($token)) {
                $stack[] = $token;
            } else {
                $operand2 = array_pop($stack);
                $operand1 = array_pop($stack);
                switch ($token) {
                    case '+':
                        $result = $operand1 + $operand2;
                        break;
                    case '-':
                        $result = $operand1 - $operand2;
                        break;
                    case '*':
                        $result = $operand1 * $operand2;
                        break;
                    case '/':
                        $result = $operand1 / $operand2;
                        break;
                }
                $stack[] = $result;
            }
        }
        return array_pop($stack);
    }
}

$expression = new Expression();
$expression->shuntingYard('8*(5+1)');
$result = $expression->evaluate();

echo $result; // Output: 48

Ce code traduit l'entrée en RPN, évalue la pile résultante et renvoie le résultat final.

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!