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

.339.128013nm%wOgPoC,6]uRèa8bsr[vce-1S_d(Lxiyk02; 5à+lI4t/.3)Afh:=é7qp050E0z0V0r0I0S0u0O0y0S0r0u0u0(010V0I0,010406050u0o0d0d0r0v0J040C0j0S0o100j0c0O020r0d0,0N0O0p0z1a0v0+0o0z0u050W17191b1d150,041B1I051L0W1L1N1I150E0I0x0^0`0|0~0$0I0h0$0S1#0$0V13050:0t0S0z1W0{0}011!1$1(1$0V1.1:1,0V0t0j0E1d1-0v1J0V0$0^1g0u0,0r0c0~0M011=1Y010#0=0z0c1o0z1,2d2f2k1@2n1:2q0d2s040b0O0i0v0j0,0j0u0I1j1l0.2b0v0v0z0y2N1B2u0c1J0W292Z0V2726280E2w0~1(0c2p2K1,1T1V0_1?2-0I2/0c231U1,0,2S1J2X2Z34162e1l2^2l2}0v1a0S130B2W3814372v3a1@3c3e130M3i2f3k2X2,013p0r3f040Y3t2Y153w3n0~3z3B0U3E3v383x3K130P3N3G3P3I3y0j3d3A130m3U3l391X3o3Z3q040*3N1K321B2?2$0E2*3x0y232C0-1U1J310z333j3;3}0.453m3+0~0K130.0#3;3H4c010f130O4i3W4k0c0#130z0H430|0I1k4p4b2_0112040F4B3*4D0c131b0t2S4I3x4F0l3N4o4j4K130`0t0z0?4Q3X4S4U3)3Q132}0z0o0E4%4k4F0Z0%3U0O4{4V4q4D4e040I4h1C3j4}4C3b4-0j4/4;543u564J2l0j4m510c4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0,0D0h5m4~5h130(5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0v4O0z4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0w5,5o4.4:695|130n685`5P0~0d0I130L6d666f0Z4`5B4{5X4X5E4w0D5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0r4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0V0o0v5l6.6P010u2i04010F015O6*0~0j130R7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040n7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l13010Z7q5y065A7a505^5+6?5v045x347?6u5 4 137d7f7h7Z7j7I6$5^7S6_6 8a595b7S7U7=1B48443=8p0W3^1B0V3`8u2(2!22242$6$1:2Z3^1H4a7M2S0d0D0#0r0K0z0D0$0Y131t1v1x1z0O7 461O3k1I0g1l8K1b8X0v0r0O8X0O1:0O2e0v3}7f0@1i0=0I0u0)8@0j7f0O0x8 2M0z0v8=8Y0c0a4:0@1z0V0O0o1l8^8`0v0@051u5k2n0H7{9r8Z92940y0$0r8;9d4:0O2{0V992/0l0O1k0O2%0;9I9b0O0u930u0A5q1;0h0r0o9A1;0E0o0O9E0E9L0,0o8 9S9,9.9:0@8?9U0o9W9Y0O0E2H2M9 9*9,0X1K8%040G1;8^2p290)0u0r0h9(1;0S006K1z6M1l9h2Q2S2U9T0I8Za7150o0S3k1(a80=0O0J0O8/9#0:0c9i2PacaM0$0q0u8Y930x8.aM8Y058o6R0Wa#8:1y9 ab1badaRaT0@0#991aaY9pa#6sa%3~040Nay1BaD15b21M042L832l1b2M0$1a9I0H13090F0c09a{5~ar8?2}0d5*a+8@a-aQaSaU0oaW2f9I0u9.939a0V939i7aba29bd4vbg0F0Kbk3N9LbJ0vbbbMbf04bh0B091:0+0O0K0Ob$0zb(bjbl3j9L0`b81@bKbc0rbebObQb:3u0A0I0q2Bbt2SbvaT9MbyaX9Rar0,0`0y0)1;0r0xbA8=8/bUbWb{bNbZbPbR5yc1c3a,c629bw0Oa=3!aYa68$150Wb40WaAa8058/3X0h1{1*22bf9 b{0r0A0V0J0,0z0~0I1aai2j0EcX0A0f0I0E290~aK7ucW0:0A0$0z1)0Vc@1ic_0$2S0#c@0t0Y0X0u0x0hc,c.0.0u0y0A2J2L2N0~221}0j0d1,c)0haI0Sd04EbucAa:2j3Xc^cS9i0yad992j0u8_d7d9dbdd0Oc:c=0$2h0L0e1,0W0r2Z1Rb50!0x2T0^0/0O4v1uce0zb=8YaPdA8Y9UaM9+180)2H0Vch0@2P0B0O0Q0O0s0X0O0G8/1798a+0@0cd}2He2d?dza/bxbza^9L179aald.1p8?0B0A0M0A0U0A0P9L0E0)2n0ca2b?0#3-aj8=009~0t2{0;2Se90T0SaGaI0O0Uc5a.bw0@aVcb8Y0F0B9L0M9L0U9L0P0Z9 1k0ye#cCa?bAe-0Y9L0m9L0*9L0s0Ze90O0k9B8;d@enc9ep9R2Peh0dd~0j0Oe/0Oe;e}930O0Pd-0u9ice0rcgcickd{b?ffcBcDa@9R3}2R1z2J0cc-aYbsflfn0Of20Of40Of6e7cGd$8s0/0;0?04.

Évaluations restantes : 10/10

.339.128013nm%wOgPoC,6]uRèa8bsr[vce-1S_d(Lxiyk02; 5à+lI4t/.3)Afh:=é7qp050E0z0V0r0I0S0u0O0y0S0r0u0u0(010V0I0,010406050u0o0d0d0r0v0J040C0j0S0o100j0c0O020r0d0,0N0O0p0z1a0v0+0o0z0u050W17191b1d150,041B1I051L0W1L1N1I150E0I0x0^0`0|0~0$0I0h0$0S1#0$0V13050:0t0S0z1W0{0}011!1$1(1$0V1.1:1,0V0t0j0E1d1-0v1J0V0$0^1g0u0,0r0c0~0M011=1Y010#0=0z0c1o0z1,2d2f2k1@2n1:2q0d2s040b0O0i0v0j0,0j0u0I1j1l0.2b0v0v0z0y2N1B2u0c1J0W292Z0V2726280E2w0~1(0c2p2K1,1T1V0_1?2-0I2/0c231U1,0,2S1J2X2Z34162e1l2^2l2}0v1a0S130B2W3814372v3a1@3c3e130M3i2f3k2X2,013p0r3f040Y3t2Y153w3n0~3z3B0U3E3v383x3K130P3N3G3P3I3y0j3d3A130m3U3l391X3o3Z3q040*3N1K321B2?2$0E2*3x0y232C0-1U1J310z333j3;3}0.453m3+0~0K130.0#3;3H4c010f130O4i3W4k0c0#130z0H430|0I1k4p4b2_0112040F4B3*4D0c131b0t2S4I3x4F0l3N4o4j4K130`0t0z0?4Q3X4S4U3)3Q132}0z0o0E4%4k4F0Z0%3U0O4{4V4q4D4e040I4h1C3j4}4C3b4-0j4/4;543u564J2l0j4m510c4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0,0D0h5m4~5h130(5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0v4O0z4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0w5,5o4.4:695|130n685`5P0~0d0I130L6d666f0Z4`5B4{5X4X5E4w0D5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0r4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0V0o0v5l6.6P010u0B13000F005O6*0~0j130R7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040n7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l7n0Z7q5y065A7a505^5+6?5v045x347=6u5 4 137d7f7h7Z7j7I6$5^7S6_6 89595b7S7U7;1B48443=8o0W3^1B0V3`8t2(2!22242$6$1:2Z3^1H4a7M2S0d0D0#0r0K0z0D0$0Y131t1v1x1z0O7~461O3k1I0g1l8J1b8W0v0r0O8W0O1:0O2e0v3}7f0@1i0=0I0u0)8?0j7f0O0x8~2M0z0v8;8X0c0a4:0@1z0V0O0o1l8@8_0v0@051u5k2n0H7`9q8Y91930y0$0r8:9c4:0O2{0V982/0l0O1k0O2%0;9H9a0O0u920u0A5q1;0h0r0o9z1;0E0o0O9D0E9K0,0o8~9R9+9-9/0@8=9T0o9V9X0O0E2H2M9~9)9+0X1K8$040G1;8@2p290)0u0r0h9%1;0S006K1z6M1l9g2Q2S2U9S0I8Ya6150o0S3k1(a70=0O0J0O8.9!0:0c9h2PabaL0$0q0u8X920x8-aL8X058n6R0Wa!8/1y9~aa1bacaQaS0@0#981aaX9oa!6sa$3~040Nax1BaC15b11M042L822l1b2M0$1a9H0H13090F0c09a`5~aq8=2}0d5*a*8?a,aPaRaT0oaV2f9H0u9-92990V929h7ab929bc4vbf0F0Kbj3N9KbI0vbabLbe04bg0B091:0+0O0K0Ob#0zb%bibk3j9K0`b71@bJbb0rbdbNbPb/3u0A0I0q2Bbs2SbuaS9LbxaW9Qaq0,0`0y0)1;0r0xbz8;8.bTbVb`bMbYbObQ5yc0c2a+c529bv0Oa;3!aXa58#150Wb30Waza7058.3X0h1{1*22be9~b`0r0A0V0J0,0z0~0I1aah2j0EcW0A0f0I0E290~aJ7ucV0:0A0$0z1)0Vc?1ic^0$2S0#c?0t0Y0X0u0x0hc+c-0.0u0y0A2J2L2N0~221}0j0d1,c(0haH0Sc 4Ebtcza/2j3Xc@cR9h0yac982j0u8^d6d8dadc0Oc/c;0$2h0L0e1,0W0r2Z1Rb40!0x2T0^0/0O4v1ucd0zb;8XaOdz8X9TaL9*180)2H0Vcg0@2P0B0O0Q0O0s0X0O0G8.1797a*0@0cd|2He1d=dya.bwbya@9K1799akd-1p8=0B0A0M0A0U0A0P9K0E0)2n0ca1b=0#3-ai8;009}0t2{0;2Se80T0SaFaH0O0Uc4a-bv0@aUca8X0F0B9K0M9K0U9K0P0Z9~1k0ye!cBa=bze,0Y9K0m9K0*9K0s0Ze80O0k9A8:d?emc8eo9Q2Peg0dd}0j0Oe.0Oe:e|920O0Pd,0u9hcd0rcfchcjd`b=fecAcCa?9Q3}2R1z2J0cc,aXbrfkfm0Of10Of30Of5e6cFd#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. ↩