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 binaire¹. 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.

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)'

Version videVersion à trous

Évaluations restantes : 10/10

.128013.3395[4)2R,%a- ièà8m16Cl7.e:A;S/dktf+Ir3sogu0x]PpOnh=céLyv(wq_b050E0y0G0k0n0v0M0m0Z0v0k0M0M0Y010G0n0U010406050M0P0r0r0k0K0$040C0N0v0P100N0W0m020k0r0U0B0m0h0y1a0K0*0P0y0M050D17191b1d150U041B1I051L0D1L1N1I150E0n0%0^0`0|0~0X0n0O0X0v1#0X0G13050:0,0v0y1W0{0}011!1$1(1$0G1.1:1,0G0,0N0E1d1-0K1J0G0X0^1g0M0U0k0W0~0g011=1Y010H0=0y0W1o0y1,2d2f2k1@2n1:2q0r2s040a0m0T0K0N0U0N0M0n1j1l0.2b0K0K0y0Z2N1B2u0W1J0D292Z0G2726280E2w0~1(0W2p2K1,1T1V0_1?2-0n2/0W231U1,0U2S1J2X2Z34162e1l2^2l2}0K1a0v130s2W3814372v3a1@3c3e130g3i2f3k2X2,013p0k3f040L3t2Y153w3n0~3z3B0e3E3v383x3K130c3N3G3P3I3y0N3d3A130t3U3l391X3o3Z3q040w3N1K321B2?2$0E2*3x0Z232C0-1U1J310y333j3;3}0.453m3+0~0F130.0H3;3H4c010)130m4i3W4k0W0H130y0R430|0n1k4p4b2_0112040(4B3*4D0W131b0,2S4I3x4F0i3N4o4j4K130`0,0y0?4Q3X4S4U3)3Q132}0y0P0E4%4k4F0f0z3U0m4{4V4q4D4e040n4h1C3j4}4C3b4-0N4/4;543u564J2l0N4m510W4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0U0+0O5m4~5h130Y5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0K4O0y4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0d5,5o4.4:695|130S685`5P0~0r0n130Q6d666f0f4`5B4{5X4X5E4w0+5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0k4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0G0P0K5l6.6P010M2i04010(015O6*0~0N130I7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040S7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l13010f7q5y065A7a505^5+6?5v045x347?6u5 4 137d7f7h7Z7j7I6$5^7S6_6 8a595b7S7U7=1B48443=8p0D3^1B0G3`8u2(2!22242$6$1:2Z3^1H4a7M2S0r0+0H0k0F0y0+0X0L131t1v1x1z0m7 461O3k1I0V1l8K1b8X0K0k0m8X0m1:0m2e0K3}7f0@1i0=0n0M0!8@0N7f0m0%8 2M0y0K8=8Y0W0b4:0@1z0G0m0P1l8^8`0K0@051u5k2n0R7{9r8Z92940Z0X0k8;9d4:0m2{0G992/0i0m1k0m2%0;9I9b0m0M930M0l5q1;0O0k0P9A1;0E0P0m9E0E9L0U0P8 9S9,9.9:0@8?9U0P9W9Y0m0E2H2M9 9*9,0x1K8%040#1;8^2p290!0M0k0O9(1;0v006K1z6M1l9h2Q2S2U9T0n8Za7150P0v3k1(a80=0m0$0m8/9#0:0W9i2PacaM0X0o0M8Y930%8.aM8Y058o6R0Da#8:1y9 ab1badaRaT0@0H991aaY9pa#6sa%3~040Bay1BaD15b21M042L832l1b2M0X1a9I0R13090(0W09a{5~ar8?2}0r5*a+8@a-aQaSaU0PaW2f9I0M9.939a0G939i7aba29bd4vbg0(0Fbk3N9LbJ0KbbbMbf04bh0s091:0*0m0F0mb$0yb(bjbl3j9L0`b81@bKbc0kbebObQb:3u0l0n0o2Bbt2SbvaT9MbyaX9Rar0U0`0Z0!1;0k0%bA8=8/bUbWb{bNbZbPbR5yc1c3a,c629bw0ma=3!aYa68$150Db40DaAa8058/3X0O1{1*22bf9 b{0k0l0G0$0U0y0~0n1aai2j0EcX0l0)0n0E290~aK7ucW0:0l0X0y1)0Gc@1ic_0X2S0Hc@0,0L0x0M0%0Oc,c.0.0M0Z0l2J2L2N0~221}0N0r1,c)0OaI0vd04EbucAa:2j3Xc^cS9i0Zad992j0M8_d7d9dbdd0mc:c=0X2h0Q0j1,0D0k2Z1Rb50A0%2T0^0/0m4v1uce0yb=8YaPdA8Y9UaM9+180!2H0Gch0@2P0s0m0p0m0q0x0m0#8/1798a+0@0Wd}2He2d?dza/bxbza^9L179aald.1p8?0s0l0g0l0e0l0c9L0E0!2n0Wa2b?0H3-aj8=009~0,2{0;2Se90J0vaGaI0m0ec5a.bw0@aVcb8Y0(0s9L0g9L0e9L0c0f9 1k0Ze#cCa?bAe-0L9L0t9L0w9L0q0fe90m0u9B8;d@enc9ep9R2Peh0rd~0N0me/0me;e}930m0cd-0M9ice0kcgcickd{b?ffcBcDa@9R3}2R1z2J0Wc-aYbsflfn0mf20mf40mf6e7cGd$8s0/0;0?04.

Évaluations restantes : 10/10

.128013.3395[4)2R,%a- ièà8m16Cl7.e:A;S/dktf+Ir3sogu0x]PpOnh=céLyv(wq_b050E0y0G0k0n0v0M0m0Z0v0k0M0M0Y010G0n0U010406050M0P0r0r0k0K0$040C0N0v0P100N0W0m020k0r0U0B0m0h0y1a0K0*0P0y0M050D17191b1d150U041B1I051L0D1L1N1I150E0n0%0^0`0|0~0X0n0O0X0v1#0X0G13050:0,0v0y1W0{0}011!1$1(1$0G1.1:1,0G0,0N0E1d1-0K1J0G0X0^1g0M0U0k0W0~0g011=1Y010H0=0y0W1o0y1,2d2f2k1@2n1:2q0r2s040a0m0T0K0N0U0N0M0n1j1l0.2b0K0K0y0Z2N1B2u0W1J0D292Z0G2726280E2w0~1(0W2p2K1,1T1V0_1?2-0n2/0W231U1,0U2S1J2X2Z34162e1l2^2l2}0K1a0v130s2W3814372v3a1@3c3e130g3i2f3k2X2,013p0k3f040L3t2Y153w3n0~3z3B0e3E3v383x3K130c3N3G3P3I3y0N3d3A130t3U3l391X3o3Z3q040w3N1K321B2?2$0E2*3x0Z232C0-1U1J310y333j3;3}0.453m3+0~0F130.0H3;3H4c010)130m4i3W4k0W0H130y0R430|0n1k4p4b2_0112040(4B3*4D0W131b0,2S4I3x4F0i3N4o4j4K130`0,0y0?4Q3X4S4U3)3Q132}0y0P0E4%4k4F0f0z3U0m4{4V4q4D4e040n4h1C3j4}4C3b4-0N4/4;543u564J2l0N4m510W4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0U0+0O5m4~5h130Y5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0K4O0y4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0d5,5o4.4:695|130S685`5P0~0r0n130Q6d666f0f4`5B4{5X4X5E4w0+5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0k4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0G0P0K5l6.6P010M0s13000(005O6*0~0N130I7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040S7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l7n0f7q5y065A7a505^5+6?5v045x347=6u5 4 137d7f7h7Z7j7I6$5^7S6_6 89595b7S7U7;1B48443=8o0D3^1B0G3`8t2(2!22242$6$1:2Z3^1H4a7M2S0r0+0H0k0F0y0+0X0L131t1v1x1z0m7~461O3k1I0V1l8J1b8W0K0k0m8W0m1:0m2e0K3}7f0@1i0=0n0M0!8?0N7f0m0%8~2M0y0K8;8X0W0b4:0@1z0G0m0P1l8@8_0K0@051u5k2n0R7`9q8Y91930Z0X0k8:9c4:0m2{0G982/0i0m1k0m2%0;9H9a0m0M920M0l5q1;0O0k0P9z1;0E0P0m9D0E9K0U0P8~9R9+9-9/0@8=9T0P9V9X0m0E2H2M9~9)9+0x1K8$040#1;8@2p290!0M0k0O9%1;0v006K1z6M1l9g2Q2S2U9S0n8Ya6150P0v3k1(a70=0m0$0m8.9!0:0W9h2PabaL0X0o0M8X920%8-aL8X058n6R0Da!8/1y9~aa1bacaQaS0@0H981aaX9oa!6sa$3~040Bax1BaC15b11M042L822l1b2M0X1a9H0R13090(0W09a`5~aq8=2}0r5*a*8?a,aPaRaT0PaV2f9H0M9-92990G929h7ab929bc4vbf0(0Fbj3N9KbI0KbabLbe04bg0s091:0*0m0F0mb#0yb%bibk3j9K0`b71@bJbb0kbdbNbPb/3u0l0n0o2Bbs2SbuaS9LbxaW9Qaq0U0`0Z0!1;0k0%bz8;8.bTbVb`bMbYbObQ5yc0c2a+c529bv0ma;3!aXa58#150Db30Daza7058.3X0O1{1*22be9~b`0k0l0G0$0U0y0~0n1aah2j0EcW0l0)0n0E290~aJ7ucV0:0l0X0y1)0Gc?1ic^0X2S0Hc?0,0L0x0M0%0Oc+c-0.0M0Z0l2J2L2N0~221}0N0r1,c(0OaH0vc 4Ebtcza/2j3Xc@cR9h0Zac982j0M8^d6d8dadc0mc/c;0X2h0Q0j1,0D0k2Z1Rb40A0%2T0^0/0m4v1ucd0yb;8XaOdz8X9TaL9*180!2H0Gcg0@2P0s0m0p0m0q0x0m0#8.1797a*0@0Wd|2He1d=dya.bwbya@9K1799akd-1p8=0s0l0g0l0e0l0c9K0E0!2n0Wa1b=0H3-ai8;009}0,2{0;2Se80J0vaFaH0m0ec4a-bv0@aUca8X0(0s9K0g9K0e9K0c0f9~1k0Ze!cBa=bze,0L9K0t9K0w9K0q0fe80m0u9A8:d?emc8eo9Q2Peg0rd}0N0me.0me:e|920m0cd,0M9hcd0kcfchcjd`b=fecAcCa?9Q3}2R1z2J0Wc,aXbrfkfm0mf10mf30mf5e6cFd#8r0/0;0?04.

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. ↩