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.push(2) // on empile 2
pile.push(9) // et 9
pile
[ 2, 9 ]
pile.pop() // on dépile
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 = {
'+': (x, y) => x + y, '-': (x, y) => x - y,
'*': (x, y) => x * y, '/': (x, y) => x / y
}
{ '+': [Function: +], '-': [Function: -], '*': [Function: *], '/': [Function: /] }
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.
Pour récupèrer les clés d’un dictionnaire on peut utiliser la fonction Object.keys
.
var calc = s =>
{
OPS =
{
'+': (x, y) => x + y, '-': (x, y) => x - y,
'*': (x, y) => x * y, '/': (x, y) => x / y
};
pile = [ ];
for (v of s.split(' '))
{
if (Object.keys(OPS).includes(v)) // includes = contient
{
[b, a] = [pile.pop(), pile.pop()];
pile.push(OPS[v](a, b)) // Ajout du résultat
}
else
{
pile.push(+v) // '+' pour convertir en nombre
}
}
return pile.pop()
}
calc('5 1 2 + 4 * + 3 -')
14
calc('3.5 2.5 +')
6