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:Lp%(40ed3;è 1o5_An)h]6,qc[yCuvài2+xms7=wlSIatf-ORrg.éPkb8/050k0j0V0U0I0R0N0o0B0R0U0N0N0P010V0I0e010406050N0F0M0M0U0!0D040S0q0R0F100q0u0o020U0M0e0m0o0Z0j1a0!0A0F0j0N050,17191b1d150e041B1I051L0,1L1N1I150k0I0G0^0`0|0~0w0I0#0w0R1#0w0V13050:0*0R0j1W0{0}011!1$1(1$0V1.1:1,0V0*0q0k1d1-0!1J0V0w0^1g0N0e0U0u0~0J011=1Y010W0=0j0u1o0j1,2d2f2k1@2n1:2q0M2s040a0o0(0!0q0e0q0N0I1j1l0.2b0!0!0j0B2N1B2u0u1J0,292Z0V2726280k2w0~1(0u2p2K1,1T1V0_1?2-0I2/0u231U1,0e2S1J2X2Z34162e1l2^2l2}0!1a0R130p2W3814372v3a1@3c3e130J3i2f3k2X2,013p0U3f040l3t2Y153w3n0~3z3B0h3E3v383x3K130r3N3G3P3I3y0q3d3A130y3U3l391X3o3Z3q040O3N1K321B2?2$0k2*3x0B232C0-1U1J310j333j3;3}0.453m3+0~0)130.0W3;3H4c010Q130o4i3W4k0u0W130j0L430|0I1k4p4b2_0112040g4B3*4D0u131b0*2S4I3x4F0z3N4o4j4K130`0*0j0?4Q3X4S4U3)3Q132}0j0F0k4%4k4F0v0c3U0o4{4V4q4D4e040I4h1C3j4}4C3b4-0q4/4;543u564J2l0q4m510u4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0e0s0#5m4~5h130P5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0!4O0j4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0C5,5o4.4:695|130x685`5P0~0M0I130i6d666f0v4`5B4{5X4X5E4w0s5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0U4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0V0F0!5l6.6P010N2i04010g015O6*0~0q130K7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040x7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l13010v7q5y065A7a505^5+6?5v045x347?6u5 4 137d7f7h7Z7j7I6$5^7S6_6 8a595b7S7U7=1B48443=8p0,3^1B0V3`8u2(2!22242$6$1:2Z3^1H4a7M2S0M0s0W0U0)0j0s0w0l131t1v1x1z0o7 461O3k1I0Y1l8K1b8X0!0U0o8X0o1:0o2e0!3}7f0@1i0=0I0N0%8@0q7f0o0G8 2M0j0!8=8Y0u0b4:0@1z0V0o0F1l8^8`0!0@051u5k2n0L7{9r8Z92940B0w0U8;9d4:0o2{0V992/0z0o1k0o2%0;9I9b0o0N930N0X5q1;0#0U0F9A1;0k0F0o9E0k9L0e0F8 9S9,9.9:0@8?9U0F9W9Y0o0k2H2M9 9*9,0$1K8%040d1;8^2p290%0N0U0#9(1;0R006K1z6M1l9h2Q2S2U9T0I8Za7150F0R3k1(a80=0o0D0o8/9#0:0u9i2PacaM0w0n0N8Y930G8.aM8Y058o6R0,a#8:1y9 ab1badaRaT0@0W991aaY9pa#6sa%3~040may1BaD15b21M042L832l1b2M0w1a9I0L13090g0u09a{5~ar8?2}0M5*a+8@a-aQaSaU0FaW2f9I0N9.939a0V939i7aba29bd4vbg0g0)bk3N9LbJ0!bbbMbf04bh0p091:0A0o0)0ob$0jb(bjbl3j9L0`b81@bKbc0UbebObQb:3u0X0I0n2Bbt2SbvaT9MbyaX9Rar0e0`0B0%1;0U0GbA8=8/bUbWb{bNbZbPbR5yc1c3a,c629bw0oa=3!aYa68$150,b40,aAa8058/3X0#1{1*22bf9 b{0U0X0V0D0e0j0~0I1aai2j0kcX0X0Q0I0k290~aK7ucW0:0X0w0j1)0Vc@1ic_0w2S0Wc@0*0l0$0N0G0#c,c.0.0N0B0X2J2L2N0~221}0q0M1,c)0#aI0Rd04EbucAa:2j3Xc^cS9i0Bad992j0N8_d7d9dbdd0oc:c=0w2h0i0f1,0,0U2Z1Rb50t0G2T0^0/0o4v1uce0jb=8YaPdA8Y9UaM9+180%2H0Vch0@2P0p0o0H0o0+0$0o0d8/1798a+0@0ud}2He2d?dza/bxbza^9L179aald.1p8?0p0X0J0X0h0X0r9L0k0%2n0ua2b?0W3-aj8=009~0*2{0;2Se90T0RaGaI0o0hc5a.bw0@aVcb8Y0g0p9L0J9L0h9L0r0v9 1k0Be#cCa?bAe-0l9L0y9L0O9L0+0ve90o0E9B8;d@enc9ep9R2Peh0Md~0q0oe/0oe;e}930o0rd-0N9ice0Ucgcickd{b?ffcBcDa@9R3}2R1z2J0uc-aYbsflfn0of20of40of6e7cGd$8s0/0;0?04.

Évaluations restantes : 10/10

.128013.339:Lp%(40ed3;è 1o5_An)h]6,qc[yCuvài2+xms7=wlSIatf-ORrg.éPkb8/050k0j0V0U0I0R0N0o0B0R0U0N0N0P010V0I0e010406050N0F0M0M0U0!0D040S0q0R0F100q0u0o020U0M0e0m0o0Z0j1a0!0A0F0j0N050,17191b1d150e041B1I051L0,1L1N1I150k0I0G0^0`0|0~0w0I0#0w0R1#0w0V13050:0*0R0j1W0{0}011!1$1(1$0V1.1:1,0V0*0q0k1d1-0!1J0V0w0^1g0N0e0U0u0~0J011=1Y010W0=0j0u1o0j1,2d2f2k1@2n1:2q0M2s040a0o0(0!0q0e0q0N0I1j1l0.2b0!0!0j0B2N1B2u0u1J0,292Z0V2726280k2w0~1(0u2p2K1,1T1V0_1?2-0I2/0u231U1,0e2S1J2X2Z34162e1l2^2l2}0!1a0R130p2W3814372v3a1@3c3e130J3i2f3k2X2,013p0U3f040l3t2Y153w3n0~3z3B0h3E3v383x3K130r3N3G3P3I3y0q3d3A130y3U3l391X3o3Z3q040O3N1K321B2?2$0k2*3x0B232C0-1U1J310j333j3;3}0.453m3+0~0)130.0W3;3H4c010Q130o4i3W4k0u0W130j0L430|0I1k4p4b2_0112040g4B3*4D0u131b0*2S4I3x4F0z3N4o4j4K130`0*0j0?4Q3X4S4U3)3Q132}0j0F0k4%4k4F0v0c3U0o4{4V4q4D4e040I4h1C3j4}4C3b4-0q4/4;543u564J2l0q4m510u4*4W58044N4P5d2Y4+4(134_5s144|5A5f4,044v0e0s0#5m4~5h130P5J573o4u4w2S4y4A5y5u4?134H5W5n5Q5p0!4O0j4=4D4)5y5C3X4L044Z4#1A5#5K1@5.345:4r4M5)5r365$0~4F0C5,5o4.4:695|130x685`5P0~0M0I130i6d666f0v4`5B4{5X4X5E4w0s5c5~6w5L045N5/6D5%5F5T2L5V645{6q4G6p3y615*6S5}556I3J4Y0U4!4$6i5g6e044T6H656T5(6V6)4R136h6O6j6:6b6B466/4F6g6S6l3g6W6r6t6u6Z01502S0V0F0!5l6.6P010N0p13000g005O6*0~0q130K7r5D5F5H7x3X7u047w7i6{5=5@6(6`7s4E6^6S5=6}76040x7B4k7D7F6C6/5=7z6~5e7a7X7V4D7l7n0v7q5y065A7a505^5+6?5v045x347=6u5 4 137d7f7h7Z7j7I6$5^7S6_6 89595b7S7U7;1B48443=8o0,3^1B0V3`8t2(2!22242$6$1:2Z3^1H4a7M2S0M0s0W0U0)0j0s0w0l131t1v1x1z0o7~461O3k1I0Y1l8J1b8W0!0U0o8W0o1:0o2e0!3}7f0@1i0=0I0N0%8?0q7f0o0G8~2M0j0!8;8X0u0b4:0@1z0V0o0F1l8@8_0!0@051u5k2n0L7`9q8Y91930B0w0U8:9c4:0o2{0V982/0z0o1k0o2%0;9H9a0o0N920N0X5q1;0#0U0F9z1;0k0F0o9D0k9K0e0F8~9R9+9-9/0@8=9T0F9V9X0o0k2H2M9~9)9+0$1K8$040d1;8@2p290%0N0U0#9%1;0R006K1z6M1l9g2Q2S2U9S0I8Ya6150F0R3k1(a70=0o0D0o8.9!0:0u9h2PabaL0w0n0N8X920G8-aL8X058n6R0,a!8/1y9~aa1bacaQaS0@0W981aaX9oa!6sa$3~040max1BaC15b11M042L822l1b2M0w1a9H0L13090g0u09a`5~aq8=2}0M5*a*8?a,aPaRaT0FaV2f9H0N9-92990V929h7ab929bc4vbf0g0)bj3N9KbI0!babLbe04bg0p091:0A0o0)0ob#0jb%bibk3j9K0`b71@bJbb0UbdbNbPb/3u0X0I0n2Bbs2SbuaS9LbxaW9Qaq0e0`0B0%1;0U0Gbz8;8.bTbVb`bMbYbObQ5yc0c2a+c529bv0oa;3!aXa58#150,b30,aza7058.3X0#1{1*22be9~b`0U0X0V0D0e0j0~0I1aah2j0kcW0X0Q0I0k290~aJ7ucV0:0X0w0j1)0Vc?1ic^0w2S0Wc?0*0l0$0N0G0#c+c-0.0N0B0X2J2L2N0~221}0q0M1,c(0#aH0Rc 4Ebtcza/2j3Xc@cR9h0Bac982j0N8^d6d8dadc0oc/c;0w2h0i0f1,0,0U2Z1Rb40t0G2T0^0/0o4v1ucd0jb;8XaOdz8X9TaL9*180%2H0Vcg0@2P0p0o0H0o0+0$0o0d8.1797a*0@0ud|2He1d=dya.bwbya@9K1799akd-1p8=0p0X0J0X0h0X0r9K0k0%2n0ua1b=0W3-ai8;009}0*2{0;2Se80T0RaFaH0o0hc4a-bv0@aUca8X0g0p9K0J9K0h9K0r0v9~1k0Be!cBa=bze,0l9K0y9K0O9K0+0ve80o0E9A8:d?emc8eo9Q2Peg0Md}0q0oe.0oe:e|920o0rd,0N9hcd0Ucfchcjd`b=fecAcCa?9Q3}2R1z2J0uc,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. ↩