Quelle expression postfixe est traduite par l'expression infixe suivante? 2 + 3 - 4/3 * 3 + 4 Je suis vraiment confus sur la façon dont cela se traduit par 2 3 4 3/3 * - + 4 + ?. Quelqu'un peut-il l'expliquer, s'il vous plaît?Veuillez expliquer comment fonctionne l'expression postfixe sur cette équation?
Merci à l'avance
Put parens autour du infix pour montrer l'ordre des opérations honorant la priorité et associativité:
((2 + 3) - ((4/3) * 3)) + 4
Maintenant, vous pouvez l'utiliser pour dessiner un arbre de syntaxe:
+
_________/ \_
| |
- 4
_/ \____
| |
+ *
/\ _/ \_
2 3 | |
'/' 3
/\
4 3
Maintenant, vous pouvez obtenir postfix en traversant l'arbre dans l'ordre suivant:
2 3 + 4 3/3 * - 4 +
Il existe d'autres commandes de poste qui donnent la bonne réponse. Par exemple, vous pouvez en obtenir plus en choisissant d'évaluer le sous-arbre gauche ou droit en premier pour chaque opérateur commutatif. De manière équivalente, vous pouvez inverser les sous-arborescences de gauche et de droite pour chaque opérateur commutatif et toujours utiliser une première recherche standard d'ordre post-enfant.
Vous pouvez vérifier l'ordre en exécutant avec une machine à pile:
Stack
read 2, push 2 [2
read 3, push 3 [2 3
read +, pop 3, pop 2, push 5 (i.e. 2 + 3) [5
read 4, push 4 [5 4
read 3, push 3 [5 4 3
read /, pop 3, pop 4, push 1.33... (i.e. 4/3) [5 1.33...
read 3, push 3 [5 1.33... 3
read *, pop 3, pop 1.33..., push 4 (i.e. 1.33... * 3)[5 4
read -, pop 4, pop 5, push 1 (i.e. 5 - 4) [1
read 4, push 4 [1 4
read +, pop 4, pop 1, push 5 (i.e. 1 + 4) [5
Alors 5 est la réponse, ce qui est d'accord avec l'évaluation de infix.