Comment évaluer une expression en notation préfixe

evaluation expression-trees s-expression

Question

J'essaie d'évaluer une liste qui représente une expression en notation préfixe. Voici un exemple d'une telle liste:

[+, [sin, 3], [- 10 5]]

Quelle est la meilleure façon d'évaluer la valeur de la liste

Réponse acceptée

Ce sera plus simple si vous avez utilisé postfix au lieu de préfixe. Voir Reverse Polish Notation (RPN) . Étant donné une expression dans RPN, il est facile d'évaluer cela en utilisant une seule pile.

Mais puisque vous avez demandé un moyen d’évaluer les expressions de préfixe sans récursion et en utilisant des piles (pour un moyen probablement plus simple, voir EDIT: ci-dessous), voici un moyen:

Nous pouvons le faire en utilisant deux piles.

Une pile (appelez-la Evaluation) contient les opérateurs (comme +, sin, etc.) et les opérandes (comme 3,4, etc.) et l'autre pile (appelez-la Count) contient un tuple du nombre d'opérandes restants à afficher + le nombre d'opérandes attend un opérateur.

Chaque fois que vous voyez un opérateur, vous le poussez sur la pile d'évaluation et placez le tuple correspondant sur la pile de comptage.

Chaque fois que vous voyez un opérande (comme 3,5, etc.), vous vérifiez le tuple supérieur de la pile Count et décrémentez le nombre d'opérandes restants dans ce tuple.

Si le nombre d'opérandes qu'il reste à voir devient zéro, vous extrayez le tuple de la pile de comptes. Ensuite, dans la pile d'évaluation, indiquez le nombre d'opérandes requis (vous le savez grâce à l'autre valeur du tuple), supprimez l'opérateur et effectuez l'opération pour obtenir une nouvelle valeur (ou opérande).

Poussez maintenant le nouvel opérande sur la pile d’évaluation. Cette nouvelle opération sur les opérandes vous oblige à jeter un nouveau regard sur le haut de la pile de comptage et à faire la même chose que nous venons de faire (décrémenter les opérandes vus, comparer à zéro, etc.).

Si le nombre d'opérandes ne devient pas zéro, continuez avec le prochain jeton dans l'entrée.

Par exemple, vous devez évaluer + 3 + 4/20 4

Les piles vont ressembler (le sommet de la pile est à gauche)

Count                  Evaluation                   Input
                                                   + 3 + 4 / 20 4

(2,2)                   +                            3 + 4 / 20 4

(2,1)                   3 +                            + 4 / 20 4

(2,2) (2,1)             + 3 +                            4 / 20 4

(2,1) (2,1)             4 + 3 +                            / 20 4

(2,2) (2,1) (2,1)       / 4 + 3 +                            20 4

(2,1) (2,1) (2,1)       20 / 4 + 3 +                            4

(2,0) (2,1) (2,1)       4 8 / 4 + 3 +                   

Since it has become zero, you pop off two operands, the operator / 
and evaluate and push back 5. You pop off (2,0) from the Count stack.

(2,1) (2,1)                5 4 + 3 +

Pushing back you decrement the current Count stack top.

(2,0) (2,1)               5 4 + 3 + 

Since it has become zero, you pop off 5,4 and + and evaluate and push back 9. 
Also pop off (2,0) from the count stack.

(2,0)                          9 3 + 

                               12

MODIFIER:

Un ami a suggéré un moyen de faire cela sans plusieurs piles:

Commencez par la fin, allez au premier opérateur. Les jetons à droite de ce seront des opérandes. Évaluer et refaire. Cela semble beaucoup plus simple que de le faire avec deux piles. Nous pouvons utiliser une liste doublement chaînée pour représenter l'entrée que nous modifions au cours du traitement. Lorsque vous évaluez, vous supprimez des nœuds, puis insérez le résultat. Ou vous pourriez peut-être simplement utiliser une pile.


Réponse populaire

KISS, évalue à l'envers comme une expression postfixée.




Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi
Sous licence: CC-BY-SA with attribution
Non affilié à Stack Overflow
Est-ce KB légal? Oui, apprenez pourquoi