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




[python] ... [/python] pour insérer un code Python.
[latex] ... [/latex] pour insérer au format latex.

Exemple:

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

[latex]\sqrt{x}[/latex]


Poster un commentaire



Programmes proches

Notation polonaise inversé ou post-fixée
Permutation circulaire d'une pile
Permutation circulaire d'une file d'attente
Copier une pile
Copier une file d'attente
Expression bien parenthésée
Renverser une file d'attente
Les primitives d'une file d'attente : FIFO
Les primitives d'une pile: LIFO