Arbre d'expression arithmétique

On considère un arbre binaire et on associe à chaque nœud une étiquette (en anglais label) contenant un opérateur binaire1. Les nœuds sont numérotés 0, 1, 2, ...

À un arbre binaire étiqueté ne contenant que des opérateurs, on peut associer un arbre étiqueté en ajoutant des opérandes comme ci-dessous.

arbre binaire et arbre

L'arbre binaire à gauche correspond à l'expression: \(((.+.)\times (. - (. / .)))\).

L'arbre à droite correspond à l'expression: \(((a+b)\times (c - (d / e)))\). Les opérandes \(a\), \(b\), \(c\), \(d\), \(e\) peuvent êtres des variables ou des nombres.

La numérotation des nœuds permet de représenter les arbres avec deux dictionnaires :

  • un dictionnaire des liens dans lequel les clés sont les numéros des nœuds internes. La valeur associée à une clé est la liste ordonnée donnant les numéros des deux enfants du nœud étudié ;
  • un dictionnaires des étiquettes associant à chaque numéro de nœud de l'arbre, l'étiquette de celui-ci.

On remarquera que les nœuds étiquetés avec des opérandes ne sont pas des clés du premier dictionnaire.

Exemple

L'arbre de la figure ci-dessus est représenté par :

  • le dictionnaire des liens arbre = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]} ;
  • le dictionnaire des étiquettes labels = {0: '*', 1: '+', 2: '-', 3: '/', 4: 'a', 5: 'b', 6: 'c', 7: 'd', 8: 'e'}.

Ce couple arbre et labels correspond à l'expression :

\[((a+b)\times (c - (d / e)))\]

qui est noté '((a+b)*(c-(d/e)))' en machine.

En modifiant la valeur des étiquettes en labels = {0: '+', 1: '-', 2: '/', 3: '*', 4: '0', 5: '1', 6: '2', 7: '3', 8: '4'}, on obtient l'expression :

\[((0-1)+(2 /(3 * 4)))\]

qui est noté '((0-1)+(2/(3*4)))' en machine.

Écrire une fonction récursive expression qui prend en paramètres :

  • les deux dictionnaires représentant un arbre et ses étiquettes,
  • un entier donnant le numéro de la racine.

Cette fonction renvoie l'expression parenthésée correspondant à l'expression arithmétique modélisée par les paramètres.

Exemples
Opérande seul
>>> arbre = {}
>>> labels = {0: '17'}
>>> expression(arbre, labels, 0)
'17'
Une opération
>>> arbre = {0: [1, 2]}
>>> labels = {0: '+', 1: '3', 2: '5'}
>>> expression(arbre, labels, 0)
'(3+5)'
Expression complexe
>>> arbre = {0: [1, 2], 1: [4, 5], 2: [6, 3], 3: [7, 8]}
>>> labels = {0: '*', 1: '+', 2: '-', 3: '/', 4: 'a', 5: 'b', 6: 'c', 7: 'd', 8: 'e'}
>>> expression(arbre, labels, 0)
'((a+b)*(c-(d/e)))'
>>> expression(arbre, labels, 1)
'(a+b)'

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.339.128013s3_8èufvIy n7aS1me(P24C:twi][hE)6Oo;bcdgM/0làqAp.rL-,=+k%5Rxé050O0t0A0p0C0T0c0m0N0T0p0c0c0%010A0C0X010406050c0h0s0s0p0Z0l040q0K0T0h120K0n0m020p0s0X0L0m0,0t1c0Z0V0h0t0c050R191b1d1f170X041D1K051N0R1N1P1K170O0C0j0`0|0~100F0C0P0F0T1%0F0A15050=0M0T0t1Y0}0 011$1(1*1(0A1:1=1.0A0M0K0O1f1/0Z1L0A0F0`1i0c0X0p0n100w011@1!010i0@0t0n1q0t1.2f2h2m1_2p1=2s0s2u040b0m0v0Z0K0X0K0c0C1l1n0:2d0Z0Z0t0N2P1D2w0n1L0R2b2#0A29282a0O2y101*0n2r2M1.1V1X0{1^2/0C2;0n251W1.0X2U1L2Z2#36182g1n2`2n2 0Z1c0T150r2Y3a16392x3c1_3e3g150w3k2h3m2Z2.013r0p3h040d3v2!173y3p103B3D0x3G3x3a3z3M150+3P3I3R3K3A0K3f3C150I3W3n3b1Z3q3#3s040o3P1M341D2^2(0O2,3z0N252E0/1W1L330t353l3?3 0:473o3-100)150:0i3?3J4e010B150m4k3Y4m0n0i150t0-450~0C1m4r4d2{0114040u4D3,4F0n151d0M2U4K3z4H0$3P4q4l4M150|0M0t0^4S3Z4U4W3+3S152 0t0h0O4)4m4H0H0z3W0m4}4X4s4F4g040C4j1E3l4 4E3d4/0K4;4?563w584L2n0K4o530n4,4Y5a044P4R5f2!4-4*154{5u164~5C5h4.044x0X0e0P5o505j150%5L593q4w4y2U4A4C5A5w4^154J5Y5p5S5r0Z4Q0t4@4F4+5A5E3Z4N044#4%1C5%5M1_5:365=4t4O5+5t385(104H0E5.5q4:4=6b5~150D6a5|5R100s0C150S6f686h0H4|5D4}5Z4Z5G4y0e5e606y5N045P5;6F5)5H5V2N5X665}6s4I6r3A635,6U5 576K3L4!0p4$4(6k5i6g044V6J676V5*6X6+4T156j6Q6l6=6d6D486;4H6i6U6n3i6Y6t6v6w6#01522U0A0h0Z5n6:6R010c2k04010u015Q6,100K150(7t5F5H5J7z3Z7w047y7k6}5@5_6*6|7u4G6`6U5@6 78040D7D4m7F7H6E6;5@7B705g7c7Z7X4F7n15010H7s5A065C7c525`5-6^5x045z367^6w6151157f7h7j7#7l7K6(5`7U6{718c5b5d7U7W7@1D4a463@8r0R3`1D0A3|8w2*2$24262(6(1=2#3`1J4c7O2U0s0e0i0p0)0t0e0F0d151v1x1z1B0m81481Q3m1K0J1n8M1d8Z0Z0p0m8Z0m1=0m2g0Z3 7h0_1k0@0C0c0.8_0K7h0m0j912O0t0Z8@8!0n0a4=0_1B0A0m0h1n8`8|0Z0_051w5m2p0-7}9t8#94960N0F0p8?9f4=0m2}0A9b2;0$0m1m0m2)0?9K9d0m0c950c0#5s1?0P0p0h9C1?0O0h0m9G0O9N0X0h919U9.9:9=0_8^9W0h9Y9!0m0O2J2Oa19,9.0Y1M8)040!1?8`2r2b0.0c0p0P9*1?0T006M1B6O1n9j2S2U2W9V0C8#a9170h0T3m1*aa0@0m0l0m8;9%0=0n9k2RaeaO0F0g0c8!950j8:aO8!058q6T0Ra%8=1Aa1ad1dafaTaV0_0i9b1ca!9ra%6ua)40040LaA1DaF17b41O042N852n1d2O0F1c9K0-15090u0n09a}60at8^2 0s5,a-8_a/aSaUaW0haY2h9K0c9:959c0A959k7cbc2bbf4xbi0u0)bm3P9NbL0ZbdbObh04bj0r091=0V0m0)0mb(0tb*blbn3l9N0|ba1_bMbe0pbgbQbSb=3w0#0C0g2Dbv2UbxaV9ObAaZ9Tat0X0|0N0.1?0p0jbC8@8;bWbYb}bPb#bRbT5Ac3c5a.c82bby0ma@3$a!a88(170Rb60RaCaa058;3Z0P1}1,24bha1b}0p0#0A0l0X0t100C1cak2l0OcZ0#0B0C0O2b10aM7wcY0=0#0F0t1+0Ac_1kc{0F2U0i1#1 0X0c0z0Ra~0:0-0Y0i3#ak0Y0p0Xdb0Y0t9+0Nb}4B0ndi0Z0R2p9C0C9b0c0R4x9b0N0C0N1B0R9!0e0M2}0?2U0e0;0C8Z1 0tdF0-0K0e0,0G0QdM0M0d0Y0c0j0Pc.c:0:0c0N0#2L2N2P10241 0K0s1.c+0PaK0Td24GbwcCa=2l3Zc`cU9kdKa!0Z2l0c8{d90Adbdddf4xdidk0tdmdo0cdqdsdu1mdxdzdJ1$dDdZdHdJdLdNdP2s0CdSdUdW9KdZd#d%d)6(d,d.d:0mc=c@0F2j0S0*1.dM2#1Tb70W0j2V0`0;0mdG1r1=b@8!aRea8!9WaO9-1a0.2J0Acj0_2R0r0m0U0m0f0Y0m0!8;199aa-0_0nf62Jfbe e9a;bzbBa`9N199cane{cg1?0r0#0w0#0x0#0+9N0O0.2p0na4b^dj3fal8@00a0eNdRev0m0k0TaIaK0m0xc7a:by0_aXcd8!0u0r9N0w9N0x9N0+0Ha11m0Nf-cEa^bCf^0d9N0I9N0o9N0f0Hfi0m0y9D8?f0fwcbfy9T2Rfq0sf70K0mf`0mf|g5950m0+e`0c9kcg0pcickcmf4b^gncDcFa_9T3 2T1B2L0nc/a!bugtgv0mga0mgc0mgefgcIe:8u0;0?0^04.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Entrer ou sortir du mode "deux colonnes"
(Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran"
(Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 10/10

.339.128013s3_8èufvIy n7aS1me(P24C:twi][hE)6Oo;bcdgM/0làqAp.rL-,=+k%5Rxé050O0t0A0p0C0T0c0m0N0T0p0c0c0%010A0C0X010406050c0h0s0s0p0Z0l040q0K0T0h120K0n0m020p0s0X0L0m0,0t1c0Z0V0h0t0c050R191b1d1f170X041D1K051N0R1N1P1K170O0C0j0`0|0~100F0C0P0F0T1%0F0A15050=0M0T0t1Y0}0 011$1(1*1(0A1:1=1.0A0M0K0O1f1/0Z1L0A0F0`1i0c0X0p0n100w011@1!010i0@0t0n1q0t1.2f2h2m1_2p1=2s0s2u040b0m0v0Z0K0X0K0c0C1l1n0:2d0Z0Z0t0N2P1D2w0n1L0R2b2#0A29282a0O2y101*0n2r2M1.1V1X0{1^2/0C2;0n251W1.0X2U1L2Z2#36182g1n2`2n2 0Z1c0T150r2Y3a16392x3c1_3e3g150w3k2h3m2Z2.013r0p3h040d3v2!173y3p103B3D0x3G3x3a3z3M150+3P3I3R3K3A0K3f3C150I3W3n3b1Z3q3#3s040o3P1M341D2^2(0O2,3z0N252E0/1W1L330t353l3?3 0:473o3-100)150:0i3?3J4e010B150m4k3Y4m0n0i150t0-450~0C1m4r4d2{0114040u4D3,4F0n151d0M2U4K3z4H0$3P4q4l4M150|0M0t0^4S3Z4U4W3+3S152 0t0h0O4)4m4H0H0z3W0m4}4X4s4F4g040C4j1E3l4 4E3d4/0K4;4?563w584L2n0K4o530n4,4Y5a044P4R5f2!4-4*154{5u164~5C5h4.044x0X0e0P5o505j150%5L593q4w4y2U4A4C5A5w4^154J5Y5p5S5r0Z4Q0t4@4F4+5A5E3Z4N044#4%1C5%5M1_5:365=4t4O5+5t385(104H0E5.5q4:4=6b5~150D6a5|5R100s0C150S6f686h0H4|5D4}5Z4Z5G4y0e5e606y5N045P5;6F5)5H5V2N5X665}6s4I6r3A635,6U5 576K3L4!0p4$4(6k5i6g044V6J676V5*6X6+4T156j6Q6l6=6d6D486;4H6i6U6n3i6Y6t6v6w6#01522U0A0h0Z5n6:6R010c0r15000u005Q6,100K150(7t5F5H5J7z3Z7w047y7k6}5@5_6*6|7u4G6`6U5@6 78040D7D4m7F7H6E6;5@7B705g7c7Z7X4F7n7p0H7s5A065C7c525`5-6^5x045z367@6w6151157f7h7j7#7l7K6(5`7U6{718b5b5d7U7W7?1D4a463@8q0R3`1D0A3|8v2*2$24262(6(1=2#3`1J4c7O2U0s0e0i0p0)0t0e0F0d151v1x1z1B0m80481Q3m1K0J1n8L1d8Y0Z0p0m8Y0m1=0m2g0Z3 7h0_1k0@0C0c0.8^0K7h0m0j902O0t0Z8?8Z0n0a4=0_1B0A0m0h1n8_8{0Z0_051w5m2p0-7|9s8!93950N0F0p8=9e4=0m2}0A9a2;0$0m1m0m2)0?9J9c0m0c940c0#5s1?0P0p0h9B1?0O0h0m9F0O9M0X0h909T9-9/9;0_8@9V0h9X9Z0m0O2J2Oa09+9-0Y1M8(040!1?8_2r2b0.0c0p0P9)1?0T006M1B6O1n9i2S2U2W9U0C8!a8170h0T3m1*a90@0m0l0m8:9$0=0n9j2RadaN0F0g0c8Z940j8/aN8Z058p6T0Ra$8;1Aa0ac1daeaSaU0_0i9a1caZ9qa$6ua(40040Laz1DaE17b31O042N842n1d2O0F1c9J0-15090u0n09a|60as8@2 0s5,a,8^a.aRaTaV0haX2h9J0c9/949b0A949j7cbb2bbe4xbh0u0)bl3P9MbK0ZbcbNbg04bi0r091=0V0m0)0mb%0tb)bkbm3l9M0|b91_bLbd0pbfbPbRb;3w0#0C0g2Dbu2UbwaU9NbzaY9Sas0X0|0N0.1?0p0jbB8?8:bVbXb|bOb!bQbS5Ac2c4a-c72bbx0ma?3$aZa78%170Rb50RaBa9058:3Z0P1}1,24bga0b|0p0#0A0l0X0t100C1caj2l0OcY0#0B0C0O2b10aL7wcX0=0#0F0t1+0Ac^1kc`0F2U0i1#1 0X0c0z0Ra}0:0-0Y0i3#aj0Y0p0Xda0Y0t9*0Nb|4B0ndh0Z0R2p9B0C9a0c0R4x9a0N0C0N1B0R9Z0e0M2}0?2U0e0;0C8Y1 0tdE0-0K0e2)9W0e0,0G0QdL0M0d0Y0c0j0Pc-c/0:0c0N0#2L2N2P10241 0K0s1.c*0PaJ0Td14GbvcBa;2l3Zc_cT9jdJaZ0Z2l0c8`d80Adadcde4xdhdj0tdldn0cdpdrdt1mdwdydI1$dCdYdGdIdKdMdO2s0CdRdTdV9JdYd!d$9}d(d*d,d.d:d=0mc;c?0F2j0S0*1.dL2#1Tb60W0j2V0`0;0mdF1r1=b?8ZaQec8Z9VaN9,1a0.2J0Aci0_2R0r0m0U0m0f0Y0m0!8:1999a,0_0nfa2Jfff3eba:bybAa_9M199bame cf1?0r0#0w0#0x0#0+9M0O0.2p0na3b@di3fak8?009 ePdQex0m0k0TaHaJ0m0xc6a/bx0_aWcc8Z0u0r9M0w9M0x9M0+0Ha01m0Nf;cDa@bBf|0d9M0I9M0o9M0f0Hfm0m0y9C8=f4fAcafC9S2Rfu0sfb0K0mf~0mg0g9940m0+e~0c9jcf0pchcjclf8b@grcCcEa^9S3 2T1B2L0nc.aZbtgxgz0mge0mgg0mgifkcHe@8t0;0?0^04.

  1. un opérateur binaire est un opérateur agissant sur deux opérandes. L'addition est un opérateur binaire : on additionne deux nombres. La racine carrée n'est pas un opérateur binaire : on calcule la racine carrée d'un nombre. ↩