Quelques explications sur la notation polonaise inverse (RPN), utilisée par exemple sur les calculatrices de la marque HP (vidéo sur ma chaine Youtube pour en savoir plus) :
Utilisez ce simulateur pour faire les calculs ci-dessous :
2 ENTER 3 + Affichage : 5 3 ENTER 4 ENTER 5 * + Affichage : 23
Ces calculatrices utilisent une pile (stack) pour placer (empiler) les valeurs (opérandes) et les calculs sont effectués dès que l'on appuie sur un opérateur (+, -, , sin, etc.). Pour cela la machine dépile 1 ou plusieurs éléments sur le principe du "dernier arrivé, premier sorti" (LIFO = Last In First Out). Pour des opérateurs dyadiques* comme l'addition ou la multiplication, il faut dépiler 2 éléments. Pour un opérateur monadique, comme sinus, on ne dépile qu'une seule valeur.
Reprenons les étapes de l'exemple proposé dans l'énoncé : 5 1 2 + 4 * + 3 -
5 ENTER 1 ENTER 2 // Pile = 5 | 1 | 2 (3 éléments empilés) + // Pile = 5 | 3 (calcul 1 + 2 = 3) 4 // Pile = 5 | 3 | 4 (4 empilé) * // Pile = 5 | 12 (calcul 3 * 4 = 12) + // Pile = 17 (calcul 5 + 12 = 17) 3 // Pile = 17 | 3 (3 empilé) - // Pile = 14 (calcul 17 - 3 = 14)
Un des intérêts du RPN est qu'il n'y a pas besoin de parenthèses, d'ailleurs vous n'en trouverez pas sur les anciennes calculatrices HP.
Les piles sont simplement des listes où l'on va pouvoir empiler et/ou dépiler des éléments :
pile = [ ] # pile vide
pile.append(2) # on empile la valeur 2
pile.append(9) # et la valeur 9
pile
[2, 9]
pile.pop() # On dépile suivant "Last In First Out"
pile
[2]
Une première solution est d'utiliser eval
:
eval('2 + 3')
5
Une autre idée est de voir 2 + 3 comme l'opérateur +
appliqué aux opérandes 2
et 3
, c'est-à-dire +(2,3)
. C'est tout simplement la notation f(x,y)
utilisée en mathématique.
OPS = { \
'+': lambda x, y: x + y, '-': lambda x, y: x - y, \
'*': lambda x, y: x * y, '/': lambda x, y: x / y \
}
OPS['+'](2,3)
5
Gardons l'exemple : 5 1 2 + 4 * + 3 -
On va séparer (split
) les différents éléments de la chaine puis, en partant de la gauche, empiler si c'est un nombre, sinon si c'est un opérateur, dépiler les 2 derniers éléments (les 4 opérateurs +-/*
étant tous dyadiques), effectuer le calcul et empiler le résultat.
On empile 5 puis 1 puis 2 '+' étant un opérateur dyadique, on dépile 1 et 2 On effectue le calcul +(1,2) qui donne 3 On empile cette valeur, etc.
def calc(s):
OPS = { \
'+': lambda x, y: x + y, '-': lambda x, y: x - y, \
'*': lambda x, y: x * y, '/': lambda x, y: x / y \
}
pile = [ ] # Pile vide
for v in s.split(): # On parcourt les éléments
if v in OPS: # Est-ce un opérateur ?
b, a = pile.pop(), pile.pop() # on dépile 2 éléments
pile.append(OPS[v](a, b)) # calcul + empiler le résultat
else: # sinon
pile.append(float(v)) # on empile la valeur
return pile.pop() # Contenu de la pile
calc('5 1 2 + 4 * + 3 -')
14.0
calc('3.5 2.5 +')
6.0