Scribd
Importer
92 vues2 pages

Notation Postfixé

Le document explique la notation polonaise inverse (postfixe) pour les expressions mathématiques, où les opérateurs suivent leurs opérandes. Il décrit également un algorithme utilisant une pile pour évaluer une expression postfixe, en empilant les valeurs et en dépilant pour effectuer les opérations. Un exemple de code Python est fourni pour illustrer la mise en œuvre de cette évaluation.

Transféré par

alabemobes2
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
92 vues2 pages

Notation Postfixé

Le document explique la notation polonaise inverse (postfixe) pour les expressions mathématiques, où les opérateurs suivent leurs opérandes. Il décrit également un algorithme utilisant une pile pour évaluer une expression postfixe, en empilant les valeurs et en dépilant pour effectuer les opérations. Un exemple de code Python est fourni pour illustrer la mise en œuvre de cette évaluation.

Transféré par

alabemobes2
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Structure de données avancées : Piles & Files

1.5. Application 2 : Calcul d’une expression postfixée


La notation polonaise inverse consiste tout simplement à utiliser la notation postfixe des
opérateurs. Une opération binaire est généralement notée de manière infixe, c'est-à-dire avec les
opérandes de part et d'autre de l'opérateur, a + b par exemple. La notation postfixe consiste à placer
l'opérateur après les deux opérandes, donc a b +. Les parenthèses deviennent inutiles (les
parenthèses sont nécessaires uniquement en notation infixe).
Exemples:
l’expression : (3 + 5) * 2 s'écrira en notation postfixe (notation polonaise) : 3 5+2*
l’expression : 3 +(5 * 2) s'écrira en notation postfixe (notation polonaise) : 3 5 2*+

Exemple : Evaluation d’une expression postfixe en utilisant une pile


On suppose que l'on dispose d'une pile initialement vide et dont le contenu va évoluer en fonction de
la lecture gauche-droite de l'expression postfixe. Si on lit une valeur, on l’empilé, si on lit une
opérateur (+,*,-,/), alors on dépile les deux derniers opérandes a et b, et on empile le résultat de
l’opération correspondante à la valeur de l’opérateur.
Si on prend l'expression (32 2 12 3 7 2 - * - * - ) on a l'évolution suivante de la pile:
6 2
5 7 7 5
4 3 3 3 3 15
PILE

3 12 12 12 12 12 12 -3
2 2 2 2 2 2 2 2 2 -6
1 32 32 32 32 32 32 32 32 32 32 38
lecture 32 2 12 3 7 2 - * - * -

Écrire un programme qui évalue une expression postfixe saisie au clavier. Les éléments de
l’expression sont séparés par espace.
Structure de données avancées : Piles & Files

def initialiser():
return []

def empiler(p,x):
p.append(x)

def depiler(p):
assert not estVide(p)
return p.pop()

def estVide(p):
return p==[]

def sommet(p):
assert not estVide(p)
return p[-1]

def calculer(a,b,c):
if c=='+':
return a+b
elif c=='-':
return a-b
elif c=='*':
return a*b
elif c=='/' and b!=0:
return a/b

expression=input("Saisir une expression: ").split()

pile=initialiser()

try:
for c in expression:
if c not in '*+-/':
empiler(pile,eval(c))

else:
b=depiler(pile)
a=depiler(pile)
x=calculer(a,b,c)
empiler(pile,x)

assert len(pile)==1
print(" la valeur de l'expression est",depiler(pile))

except:
print("Expression incorrecte")

Vous aimerez peut-être aussi