{"id":310,"date":"2022-06-09T07:02:27","date_gmt":"2022-06-09T06:02:27","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=310"},"modified":"2022-06-19T08:02:52","modified_gmt":"2022-06-19T07:02:52","slug":"kata8","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2022\/06\/09\/kata8\/","title":{"rendered":"Huiti\u00e8me exercice en Python, JavaScript et APL"},"content":{"rendered":"\n
\"\"<\/a><\/figure>\n\n\n\n

Quelques explications sur la notation polonaise inverse<\/strong> (RPN<\/strong>), utilis\u00e9e par exemple sur les calculatrices de la marque HP<\/strong> (vid\u00e9o sur ma chaine Youtube pour en savoir plus<\/a>) :<\/p>\n\n\n\n

\"Aucune
Calculateur HP-11C utilisant le mode RPN (collection personnelle)<\/figcaption><\/figure>\n\n\n\n

Utilisez ce simulateur<\/a> pour faire les calculs ci-dessous :<\/p>\n\n\n\n

2 ENTER 3 +\nAffichage : 5\n\n3 ENTER 4 ENTER 5 * +\nAffichage : 23<\/code><\/pre>\n\n\n\n
Ces calculatrices utilisent une pile<\/strong> (stack<\/strong>) pour placer (empiler<\/strong>) les valeurs (op\u00e9randes<\/strong>) et les calculs sont effectu\u00e9s d\u00e8s que l’on appuie sur un op\u00e9rateur<\/strong> (+, -, *, sin, etc.). Pour cela la machine d\u00e9pile 1 ou plusieurs \u00e9l\u00e9ments sur le principe du \u00ab\u00a0dernier arriv\u00e9, premier sorti\u00a0\u00bb (LIFO = Last In First Out). Pour des op\u00e9rateurs dyadiques<\/strong> comme l’addition<\/strong> ou la multiplication<\/strong>, il faut d\u00e9piler 2 \u00e9l\u00e9ments<\/strong>. Pour un op\u00e9rateur monadique<\/strong>, comme sinus<\/strong>, on ne d\u00e9pile qu’une seule<\/strong> valeur.<\/p>\n\n\n\n
Reprenons les \u00e9tapes de l’exemple propos\u00e9 dans l’\u00e9nonc\u00e9 : 5 1 2 + 4 * + 3 –<\/strong><\/p>\n\n\n\n
5 ENTER 1 ENTER 2  \/\/ Pile = 5 | 1 | 2     (3 \u00e9l\u00e9ments empil\u00e9s)\n+                  \/\/ Pile = 5 | 3         (calcul 1 + 2 = 3)\n4                  \/\/ Pile = 5 | 3 | 4     (4 empil\u00e9)\n*                  \/\/ Pile = 5 | 12        (calcul 3 * 4 = 12)\n+                  \/\/ Pile = 17            (calcul 5 + 12 = 17) \n3                  \/\/ Pile = 17 | 3        (3 empil\u00e9)\n-                  \/\/ Pile = 14            (calcul 17 - 3 = 14) <\/code><\/pre>\n\n\n\n
Un des int\u00e9r\u00eats du RPN est qu’il n’y a pas besoin de parenth\u00e8ses<\/strong>, d’ailleurs vous n’en trouverez pas sur les anciennes calculatrices HP.<\/p>\n\n\n\n
Les piles en python et javascript<\/h3>\n\n\n\n
Les piles<\/strong> sont simplement des listes<\/strong> o\u00f9 l’on va pouvoir empiler<\/strong> et\/ou d\u00e9piler<\/strong> des \u00e9l\u00e9ments :<\/p>\n\n\n\n
En Python<\/span>\n\n>> pile = [ ]        # pile vide\n>> pile.append(2)    # on empile la valeur 2\n>> pile.append(9)    # et la valeur 9\n>> pile\n[2, 9]\n>> pile.pop()        # On d\u00e9pile suivant \"Last In First Out\"\n9\n>> pile\n[2]                  # Il n'y a plus qu'un seul \u00e9l\u00e9ment dans la pile\n\nEn JavaScript<\/span>\n\n>> pile = [ ]\n>> pile.push(2)\n1\n>> pile.push(9)\n2\n>> pile\n[2, 9]\n>> pile.pop()\n9\n>> pile\n[2]<\/code><\/pre>\n\n\n\n
Evaluer une expression en python et javascript<\/h3>\n\n\n\n
Une premi\u00e8re solution (Python et JavaScript) est d’utiliser eval<\/strong> :<\/p>\n\n\n\n
>> eval('2 + 3')\n5<\/code><\/pre>\n\n\n\n
Une autre id\u00e9e est de voir 2 + 3<\/strong> comme l’op\u00e9rateur<\/strong> +<\/strong> appliqu\u00e9 aux op\u00e9randes<\/strong> 2<\/strong> et 3<\/strong>, c’est-\u00e0-dire +(2,3)<\/strong>. C’est tout simplement la notation f(x,y)<\/strong> utilis\u00e9e en math\u00e9matique.<\/p>\n\n\n\n
Voici comment traduire les 4 op\u00e9rations en JavaScript \u00e0 l’aide d’un dictionnaire<\/strong> :<\/p>\n\n\n\n
>> OPS = {\n  '+': (x, y) => x + y, '-': (x, y) => x - y, \n  '*': (x, y) => x * y, '\/': (x, y) => x \/ y\n}\n\n>> OPS['+'](2,3)\n5<\/code><\/pre>\n\n\n\n
Et en Python :<\/p>\n\n\n\n
>> OPS = {  \\\n  '+': lambda x, y: x + y, '-': lambda x, y: x - y, \\\n  '*': lambda x, y: x * y, '\/': lambda x, y: x \/ y  \\\n  }\n\n>> OPS['+'](2,3)\n5<\/code><\/pre>\n\n\n\n
Id\u00e9e du programme<\/h2>\n\n\n\n
Gardons l’exemple : 5 1 2 + 4 * + 3 –<\/strong><\/p>\n\n\n\n
On va s\u00e9parer<\/strong> (split<\/strong>) les diff\u00e9rents \u00e9l\u00e9ments de la chaine puis, en partant de la gauche, empiler<\/strong> si<\/strong> c’est un nombre<\/strong>, sinon si <\/strong>c’est un op\u00e9rateur<\/strong>, d\u00e9piler<\/strong> les 2 derniers<\/strong> \u00e9l\u00e9ments (les 4 op\u00e9rateurs +-\/*<\/strong> \u00e9tant tous dyadiques), effectuer le calcul<\/strong> et empiler<\/strong> le r\u00e9sultat.<\/p>\n\n\n\n
On empile 5 puis 1 puis 2\n'+' \u00e9tant un op\u00e9rateur dyadique, on d\u00e9pile 1 et 2\nOn effectue le calcul +(1,2) qui donne 3\nOn empile cette valeur, etc.<\/code><\/pre>\n\n\n\n
Python<\/h3>\n\n\n\n
Vous pouvez tester le programme ici <\/a>: <\/p>\n\n\n\n
def calc(s):\n  OPS = {  \\\n  '+': lambda x, y: x + y, '-': lambda x, y: x - y, \\\n  '*': lambda x, y: x * y, '\/': lambda x, y: x \/ y  \\\n  }\n  pile = [ ]                         # Pile vide\n  for v in s.split():                # On parcourt les \u00e9l\u00e9ments\n    if v in OPS:                     # Est-ce un op\u00e9rateur ?\n      b, a = pile.pop(), pile.pop()  # on d\u00e9pile 2 \u00e9l\u00e9ments\n      pile.append(OPS[v](a, b))      # calcul + empiler le r\u00e9sultat\n    else:                            # sinon\n      pile.append(float(v))          # on empile la valeur\n  return pile.pop()                  # Contenu de la pile\n\n>> calc('5 1 2 + 4 * + 3 -')\n14.0\n>> calc('3.5 2.5 +')\n6.0<\/code><\/pre>\n\n\n\n
JavaScript<\/h3>\n\n\n\n
Pour r\u00e9cup\u00e8rer les cl\u00e9s<\/strong> d’un dictionnaire on peut utiliser la fonction Object.keys<\/strong>. Vous pouvez tester le programme ici<\/a> : <\/p>\n\n\n\n
>> const calc = s => \n{\n    OPS = \n    {\n      '+': (x, y) => x + y, '-': (x, y) => x - y, \n      '*': (x, y) => x * y, '\/': (x, y) => x \/ y\n    };\n    pile = [ ];\n    for (v of s.split(' ')) \n    {\n      if (Object.keys(OPS).includes(v))    \/\/ includes = contient\n      {\n         [b, a] = [pile.pop(), pile.pop()];\n         pile.push(OPS[v](a, b))     \/\/ Ajout du r\u00e9sultat\n      }\n      else \n      {\n         pile.push(+v)        \/\/ '+' pour convertir en nombre\n      }\n    }\n    return pile.pop()\n}\n\n>> calc('5 1 2 + 4 * + 3 -')\n14\n>> calc('3.5 2.5 +')\n6<\/code><\/pre>\n\n\n\n
Version APL<\/h2>\n\n\n\n
Un peu plus loin avec les r\u00e9ductions<\/h3>\n\n\n\n
Les calculs s’effectuant de la droite vers la gauche, nous allons d\u00e9j\u00e0 retourner<\/strong> le vecteur :<\/p>\n\n\n\n
      s \u2190 5 1 2 '+' 4 '\u00d7' '+' 3 '-'\n      \u233ds\n- 3 +\u00d7 4 + 2 1 5<\/code><\/pre>\n\n\n\n
Nous avons vu des r\u00e9ductions simples<\/strong> comme +\/<\/strong>, \u00d7\/<\/strong> etc :<\/p>\n\n\n\n
      +\/ 1 2 3 4       \u235d Somme des \u00e9l\u00e9ments du vecteur\n10\n      \u00d7\/ 1 2 3 4       \u235d Produit des \u00e9l\u00e9ments du vecteur\n24<\/code><\/pre>\n\n\n\n
Mais il est possible de faire des r\u00e9ductions plus complexes<\/strong>, premier exemple :<\/p>\n\n\n\n
            {\u237a,\u237a,\u2375} \/ 1 3 4\n\u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510\n\u25021 1 3 3 4\u2502\n\u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518<\/code><\/pre>\n\n\n\n
Etape 1<\/span> : \u2375 = 4 (terme de droite)
Etape 2<\/span> : \u237a = 3 que l’on ajoute 2 fois \u00e0 \u2375 (concat\u00e9nation \u237a,\u237a,\u2375), ce qui donne \u2375 = 3 3 4
Etape 3<\/span> : \u237a = 1 que l’on ajoute 2 fois \u00e0 \u2375 = 3 3 4 d’o\u00f9 le 1 1 3 3 4<\/p>\n\n\n\n
Autre exemple<\/span> :<\/p>\n\n\n\n
      {\u237a, \u233d\u2375} \/ 1 2 3 4\n\u250c\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2510\n\u25021 3 4 2\u2502\n\u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2500\u2518<\/code><\/pre>\n\n\n\n
Etape 1<\/span> : \u2375 = 4 (terme de droite)
Etape 2<\/span> : Ajouter \u237a = 3 et inverser \u2375 = 4, on obtient \u2375 = 3 4
Etape 3<\/span> : Ajouter \u237a = 2 et inverser \u2375 = 3 4, on obtient \u2375 = 2 4 3
Etape 4<\/span> : Ajouter \u237a = 1 et inverser \u2375 = 2 4 3, on obtient \u2375 = 1 3 4 2<\/p>\n\n\n\n
\u00e9valuation d’une expression<\/h3>\n\n\n\n
Voici comment on peut transformer un vecteur \u00e0 3 \u00e9l\u00e9ments, par exemple  ‘+’ 4 2 <\/strong>en ‘4 + 2’<\/strong> et l’\u00e9valuer<\/strong> :<\/p>\n\n\n\n
      '+' 4 2 [2 1 3]    \u235d Prendre 2e 1er et 3e \u00e9l\u00e9ment dans cet ordre\n4 + 2                    \u235d Le r\u00e9sultat reste un vecteur \u00e0 3 \u00e9l\u00e9ments\n     \u2355 '+' 4 2 [2 1 3]   \u235d Transformer ce vecteur en chaine avec \u2355\n4 + 2\n    \u234e \u2355 '+' 4 2 [2 1 3]  \u235d Evaluer le r\u00e9sultat avec \u234e\n6<\/code><\/pre>\n\n\n\n
simulation d’une pile<\/h3>\n\n\n\n
      pile \u2190 4 6 8 9        \u235d Une pile de 4 \u00e9l\u00e9ments\n      \u00af1\u2191pile               \u235d R\u00e9cup\u00e9rer le dernier \u00e9l\u00e9ment\n9\n      \u00af1\u2193pile               \u235d Supprimer le dernier \u00e9l\u00e9ment\n4 6 8\n      \u00af2\u2191pile               \u235d R\u00e9cup\u00e9rer les 2 derniers \u00e9l\u00e9ments\n8 9<\/code><\/pre>\n\n\n\n
Programme final<\/h3>\n\n\n\n
Lien pour tester directement le code ci-dessous<\/a> :<\/p>\n\n\n\n
      calc \u2190 {\u237a \u220a '+-\u00d7\u00f7' : (\u00af2\u2193\u2375), \u234e\u2355 (\u237a,\u00af2\u2191\u2375)[2 1 3] \u22c4 \u2375, \u237a} \/ \u233d\n\n      calc 4 2 '+'\n\u250c\u2500\u2510\n\u25026\u2502\n\u2514\u2500\u2518\n      calc 5 1 2 '+' 4 '\u00d7' '+' 3 '-'\n\u250c\u2500\u2500\u2510\n\u250214\u2502\n\u2514\u2500\u2500\u2518<\/code><\/pre>\n\n\n\n
Explications<\/span> :

Si l’\u00e9l\u00e9ment \u237a<\/strong> du vecteur est un op\u00e9rateur (\u237a \u220a ‘+-\u00d7\u00f7’<\/strong>) alors supprimer les 2 derniers \u00e9l\u00e9ments de la pile ( \u00af2\u2193\u2375<\/strong> ) et concat\u00e9ner le calcul (\u234e<\/strong>) entre l’op\u00e9rateur \u237a<\/strong> et les 2 op\u00e9randes au sommet de la pile ( \u00af2\u2191\u2375<\/strong> ) en les mettant dans le bon ordre ([2 1 3]<\/strong>). Sinon, ajouter la valeur \u237a<\/strong> \u00e0 la pile ( \u2375,\u237a <\/strong>).<\/p>\n","protected":false},"excerpt":{"rendered":"
Quelques explications sur la notation polonaise inverse (RPN), utilis\u00e9e par exemple sur les calculatrices de la marque HP (vid\u00e9o sur ma chaine Youtube pour en savoir plus) : Utilisez ce simulateur pour faire les calculs ci-dessous : Ces calculatrices utilisent … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-310","post","type-post","status-publish","format-standard","hentry","category-twitter"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/310","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/users\/4913"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/comments?post=310"}],"version-history":[{"count":42,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/310\/revisions"}],"predecessor-version":[{"id":657,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/310\/revisions\/657"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=310"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=310"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=310"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}