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.339,%è Ow5e(8CR0pkoic6S1vqAd:xIy24fln-]3m=)rh[us;b/.àt_gLéaP+7050A0j0!0)0s0I0U0f0t0I0)0U0U0O010!0s0p010406050U0T0N0N0)0Q0E040v0r0I0T100r0J0f020)0N0p0V0f0n0j1a0Q0y0T0j0U050X17191b1d150p041B1I051L0X1L1N1I150A0s0x0^0`0|0~0R0s0$0R0I1#0R0!13050:0W0I0j1W0{0}011!1$1(1$0!1.1:1,0!0W0r0A1d1-0Q1J0!0R0^1g0U0p0)0J0~0F011=1Y010H0=0j0J1o0j1,2d2f2k1@2n1:2q0N2s040a0f0*0Q0r0p0r0U0s1j1l0.2b0Q0Q0j0t2N1B2u0J1J0X292Z0!2726280A2w0~1(0J2p2K1,1T1V0_1?2-0s2/0J231U1,0p2S1J2X2Z34162e1l2^2l2}0Q1a0I130w2W3814372v3a1@3c3e130F3i2f3k2X2,013p0)3f040M3t2Y153w3n0~3z3B0G3E3v383x3K130i3N3G3P3I3y0r3d3A130u3U3l391X3o3Z3q040,3N1K321B2?2$0A2*3x0t232C0-1U1J310j333j3;3}0.453m3+0~0q130.0H3;3H4c010h130f4i3W4k0J0H130j0C430|0s1k4p4b2_0112040k4B3*4D0J131b0W2S4I3x4F0c3N4o4j4K130`0W0j0?4Q3X4S4U3)3Q132}0j0T0A4%4k4F0P0B3U0f4{4V4q4D4e040s4h1C3j4}4C3b4-0r4/4;543u564J2l0r4m510J4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0p0#0$5m4~5h130O5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0Q4O0j4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0S5,5o4.4:695|130L685`5P0~0N0s130o6d666f0P4`5B4{5X4X5E4w0#5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0)4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0!0T0Q5l6.6P010U2i04010k015O6*0~0r130+7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040L7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l13010P7q5y065A7a505^5+6?5v045x347?6u5 4 137d7f7h7Z7j7I6$5^7S6_6 8a595b7S7U7=1B48443=8p0X3^1B0!3`8u2(2!22242$6$1:2Z3^1H4a7M2S0N0#0H0)0q0j0#0R0M131t1v1x1z0f7 461O3k1I0g1l8K1b8X0Q0)0f8X0f1:0f2e0Q3}7f0@1i0=0s0U0(8@0r7f0f0x8 2M0j0Q8=8Y0J0b4:0@1z0!0f0T1l8^8`0Q0@051u5k2n0C7{9r8Z92940t0R0)8;9d4:0f2{0!992/0c0f1k0f2%0;9I9b0f0U930U0K5q1;0$0)0T9A1;0A0T0f9E0A9L0p0T8 9S9,9.9:0@8?9U0T9W9Y0f0A2H2M9 9*9,0Y1K8%040%1;8^2p290(0U0)0$9(1;0I006K1z6M1l9h2Q2S2U9T0s8Za7150T0I3k1(a80=0f0E0f8/9#0:0J9i2PacaM0R0e0U8Y930x8.aM8Y058o6R0Xa#8:1y9 ab1badaRaT0@0H991aaY9pa#6sa%3~040Vay1BaD15b21M042L832l1b2M0R1a9I0C13090k0J09a{5~ar8?2}0N5*a+8@a-aQaSaU0TaW2f9I0U9.939a0!939i7aba29bd4vbg0k0qbk3N9LbJ0QbbbMbf04bh0w091:0y0f0q0fb$0jb(bjbl3j9L0`b81@bKbc0)bebObQb:3u0K0s0e2Bbt2SbvaT9MbyaX9Rar0p0`0t0(1;0)0xbA8=8/bUbWb{bNbZbPbR5yc1c3a,c629bw0fa=3!aYa68$150Xb40XaAa8058/3X0$1{1*22bf9 b{0)0K0!0E0p0j0~0s1aai2j0AcX0K0h0s0A290~aK7ucW0:0K0R0j1)0!c@1ic_0R2S0Hc@0W0M0Y0U0x0$c,c.0.0U0t0K2J2L2N0~221}0r0N1,c)0$aI0Id04EbucAa:2j3Xc^cS9i0tad992j0U8_d7d9dbdd0fc:c=0R2h0o0d1,0X0)2Z1Rb50z0x2T0^0/0f4v1uce0jb=8YaPdA8Y9UaM9+180(2H0!ch0@2P0w0f0Z0f0l0Y0f0%8/1798a+0@0Jd}2He2d?dza/bxbza^9L179aald.1p8?0w0K0F0K0G0K0i9L0A0(2n0Ja2b?0H3-aj8=009~0W2{0;2Se90D0IaGaI0f0Gc5a.bw0@aVcb8Y0k0w9L0F9L0G9L0i0P9 1k0te#cCa?bAe-0M9L0u9L0,9L0l0Pe90f0m9B8;d@enc9ep9R2Peh0Nd~0r0fe/0fe;e}930f0id-0U9ice0)cgcickd{b?ffcBcDa@9R3}2R1z2J0Jc-aYbsflfn0ff20ff40ff6e7cGd$8s0/0;0?04.

Évaluations restantes : 10/10

.128013.339,%è Ow5e(8CR0pkoic6S1vqAd:xIy24fln-]3m=)rh[us;b/.àt_gLéaP+7050A0j0!0)0s0I0U0f0t0I0)0U0U0O010!0s0p010406050U0T0N0N0)0Q0E040v0r0I0T100r0J0f020)0N0p0V0f0n0j1a0Q0y0T0j0U050X17191b1d150p041B1I051L0X1L1N1I150A0s0x0^0`0|0~0R0s0$0R0I1#0R0!13050:0W0I0j1W0{0}011!1$1(1$0!1.1:1,0!0W0r0A1d1-0Q1J0!0R0^1g0U0p0)0J0~0F011=1Y010H0=0j0J1o0j1,2d2f2k1@2n1:2q0N2s040a0f0*0Q0r0p0r0U0s1j1l0.2b0Q0Q0j0t2N1B2u0J1J0X292Z0!2726280A2w0~1(0J2p2K1,1T1V0_1?2-0s2/0J231U1,0p2S1J2X2Z34162e1l2^2l2}0Q1a0I130w2W3814372v3a1@3c3e130F3i2f3k2X2,013p0)3f040M3t2Y153w3n0~3z3B0G3E3v383x3K130i3N3G3P3I3y0r3d3A130u3U3l391X3o3Z3q040,3N1K321B2?2$0A2*3x0t232C0-1U1J310j333j3;3}0.453m3+0~0q130.0H3;3H4c010h130f4i3W4k0J0H130j0C430|0s1k4p4b2_0112040k4B3*4D0J131b0W2S4I3x4F0c3N4o4j4K130`0W0j0?4Q3X4S4U3)3Q132}0j0T0A4%4k4F0P0B3U0f4{4V4q4D4e040s4h1C3j4}4C3b4-0r4/4;543u564J2l0r4m510J4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0p0#0$5m4~5h130O5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0Q4O0j4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0S5,5o4.4:695|130L685`5P0~0N0s130o6d666f0P4`5B4{5X4X5E4w0#5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0)4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0!0T0Q5l6.6P010U0w13000k005O6*0~0r130+7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040L7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l7n0P7q5y065A7a505^5+6?5v045x347=6u5 4 137d7f7h7Z7j7I6$5^7S6_6 89595b7S7U7;1B48443=8o0X3^1B0!3`8t2(2!22242$6$1:2Z3^1H4a7M2S0N0#0H0)0q0j0#0R0M131t1v1x1z0f7~461O3k1I0g1l8J1b8W0Q0)0f8W0f1:0f2e0Q3}7f0@1i0=0s0U0(8?0r7f0f0x8~2M0j0Q8;8X0J0b4:0@1z0!0f0T1l8@8_0Q0@051u5k2n0C7`9q8Y91930t0R0)8:9c4:0f2{0!982/0c0f1k0f2%0;9H9a0f0U920U0K5q1;0$0)0T9z1;0A0T0f9D0A9K0p0T8~9R9+9-9/0@8=9T0T9V9X0f0A2H2M9~9)9+0Y1K8$040%1;8@2p290(0U0)0$9%1;0I006K1z6M1l9g2Q2S2U9S0s8Ya6150T0I3k1(a70=0f0E0f8.9!0:0J9h2PabaL0R0e0U8X920x8-aL8X058n6R0Xa!8/1y9~aa1bacaQaS0@0H981aaX9oa!6sa$3~040Vax1BaC15b11M042L822l1b2M0R1a9H0C13090k0J09a`5~aq8=2}0N5*a*8?a,aPaRaT0TaV2f9H0U9-92990!929h7ab929bc4vbf0k0qbj3N9KbI0QbabLbe04bg0w091:0y0f0q0fb#0jb%bibk3j9K0`b71@bJbb0)bdbNbPb/3u0K0s0e2Bbs2SbuaS9LbxaW9Qaq0p0`0t0(1;0)0xbz8;8.bTbVb`bMbYbObQ5yc0c2a+c529bv0fa;3!aXa58#150Xb30Xaza7058.3X0$1{1*22be9~b`0)0K0!0E0p0j0~0s1aah2j0AcW0K0h0s0A290~aJ7ucV0:0K0R0j1)0!c?1ic^0R2S0Hc?0W0M0Y0U0x0$c+c-0.0U0t0K2J2L2N0~221}0r0N1,c(0$aH0Ic 4Ebtcza/2j3Xc@cR9h0tac982j0U8^d6d8dadc0fc/c;0R2h0o0d1,0X0)2Z1Rb40z0x2T0^0/0f4v1ucd0jb;8XaOdz8X9TaL9*180(2H0!cg0@2P0w0f0Z0f0l0Y0f0%8.1797a*0@0Jd|2He1d=dya.bwbya@9K1799akd-1p8=0w0K0F0K0G0K0i9K0A0(2n0Ja1b=0H3-ai8;009}0W2{0;2Se80D0IaFaH0f0Gc4a-bv0@aUca8X0k0w9K0F9K0G9K0i0P9~1k0te!cBa=bze,0M9K0u9K0,9K0l0Pe80f0m9A8:d?emc8eo9Q2Peg0Nd}0r0fe.0fe:e|920f0id,0U9hcd0)cfchcjd`b=fecAcCa?9Q3}2R1z2J0Jc,aXbrfkfm0ff10ff30ff5e6cFd#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. ↩