Notation polonaise inversé ou post-fixée

Exercice: Notation polonaise inversé ou post-fixée

Fonction Python PolonaiseInverse( expression ) qui permet d’évaluer des expressions écrites en polonaise inversée. La notation polonaise inversée ou post-fixée permet de noter les formules arithmétiques sans utiliser de parenthèses.

expression est une chaine de caractère sous forme notation polonaise inversé où les nombres ainsi les opérations sont séparés par des espaces.

Exemples:

  • la forme polonaise de m’expression (21 + 13)  * 40 est 21  13  +  40  *
  • la forme polonaise de m’expression 10 + (31   * 4 ) est 10  31  4  +  +
  • la forme polonaise de m’expression  ( 3 + ( 5 * ( 7 + 2 ))) + ( 4 + ( 8 * 9 )) est  3  5  7  2  +  *  +  4  8  9  *  +  +

Algorithme d’évaluation

Pour effectuer le calcul, chaque donnée numérique est empilée, et lorsqu’on lit un opérateur, les opérandes sont dépilés, l’opération est effectuée et le résultat est mis au sommet de la pile.

Par exemple, pour évaluer  2  3  +  4  * :

  1. lecture de 2 qui est reconnu comme donnée numérique et de ce fait est empilé
  2. lecture de 3 qui est également empilé
  3. lecture de + qui est un opérateur binaire : 2 et 3 sont dépilés, le calcul 2 + 3 est effectué, le résultat 5 est empilé
  4. lecture de 4 qui est empilé
  5. lecture de * , opérateur binaire : 4 et 5 sont dépilés, le calcul 4*5 est effectué et le résultat 20 est empilé
  6. l’expression est entièrement lue donc le résultat final est au sommet de la pile.

N.B :

  • Pour distinguer deux (ou plus) nombres consécutifs, ils ont séparé par des espaces.
  • Pour la résolution de cette fonction on utilise les primitives des piles.

Exemple d’exécution:

>>> polonaise( ‘ 30  15  7  12  +  *  +  11  8  10  *  +  + ‘ )
406

Partager avec...
Share on FacebookShare on Google+Tweet about this on Twitter
Tagués avec : , , , , , , , , , , , , , ,

Poster un Commentaire

Soyez le premier à commenter !

Utiliser [python] ... [/python] pour insérer un code Python.

$latex format_latex $ pour insérer au format latex.

Exemple:

[python]
print('Hello word')
[/python]

$latex \sqrt{x} $

Laisser un commentaire


Programme similaire