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.128013bqO,vià3o_x;lpwf( g0]6-)2As18+e%né4è[m5tCLRPhk:c.a=rySIu/7d050,0G0P0Z0h0o0C0t0X0o0Z0C0C0!010P0h0p010406050C0)0N0N0Z0#0$040%0k0o0)100k0I0t020Z0N0p0n0t0S0G1a0#0d0)0G0C050*17191b1d150p04051I1B1L0*1I150,0h0g0^0`0|0~0U0h0u0U0o1Z0U0P13050:0c0o0G1U0{0}011Y1!1$1!0P1,1.1*0P0#1J0P0U0^1g0C0p0Z0I0~0A011:1W010r0=0G0I1o0G1*26282d1=2g1.2j0N2l040b0t0T0#0k0p0k0C0h1j1l0.240#0#0G0X2G1B2n0I1J0*222S1 21201+0,2p0~1$0I2i2D1*1R1T0_1;2$0h2(0I0k2,1*0p2L1J2Q2S2}16271l2.2e2?0#1a0o130D2P3114302o331=3537130A3b283d2Q2#013i0Z38040j3m2R153p3g0~3s3u0K3x3o313q3D130O3G3z3I3B3r0k363t130x3N3e321V3h3S3j040+3G1M2{1B2,2V0,212!3Q0X2@2v0-1S1J2`0G2|3c3*3@0.3 3f3!0~0V130.0r3*3A46010q130t4c3P4e0I0r130G0m3}0|0h1k4j452/0112040s4v3Z4x0I131b0c2L4C3q4z0f3G4i4d4E130`0c0G0?4K3Q4M4O3Y3J132?0G0)0,4X4e4z0z0W3N0t4=4P4k4x48040h4b1C3c4@4w344%0k4)4+4~3n504D2e0k4g4{0I4!4Q52044H4J572R4#4Y134:5m144?5u594$044p0p0l0u5g4^5b130!5D513h4o4q2L4s4u5s5o4-134B5Q5h5K5j0#4I0G4,4x4Z5s5w3Q4F044T4V1A5V5E1=5(2}5*4l4G5Z5l2 5W0~4z0M5$5i4(4*635?130w625;5J0~0N0h130v6760690z4;5v4=5R4R5y4q0l565^6q5F045H5)6x5X5z5N2E5P5~5=6k4A6j3r5{5!6M5@4 6C3C4S0Z4U4W6c5a68044N6B5 6N5Y6P6Z4L136b6I6d6*656v406)4z6a6M6f396Q6l6n6o6T014`2L0P0)0#5f6(6J010C2b04021x0k0P0n0s7i0)7k0n5I6!0~0k130F7s5x5z5B7y3Q7v047x7c6=5,5.6Y6;7t4y6/6M5,6@70040w7C4e7E7G6w6)5,7A6^58747Y7W4x7f137o7q0z7:7l725_4_4o0?5#6-5p045r2}066o6p6)760/797b7!7d7J6W5/7T6:6_8c53557T7V5s150*423~3+8s0*3.1B0P3:8x2Y2T6W1.2S3.1H447N2L0N0l0r0Z0V0G0l0U0j131t1v1x1z0t81401O3d1I0e1l8K1b8X0#0Z0t8X0t1.0t270#3@790@1i0=0h0C0J8@0k790t0g8 2F0G0#8=8Y0I0a4*0@1z0P0t0)1l8^8`0#0@051u5e2g0m7}9r8Z92940X0U0Z8;9d4*0t2;0P992(0f0t1k0t1 0;9I9b0t0C930C0y5k1/0u0Z0)9A1/0,0)0t9E0,9L0p0)8 9S9,9.9:0@8?9U0)9W9Y0t0,2A2F9 9*9,0Y1M8%040R1/8^2i220J0C0Z0u9(1/0o006E1z6G1l9h2J2L2N9T0h8Za7150)0o3d1$a80=0t0$0t8/9#0:0I9i2IacaM0U0L0C8Y930g8.aM8Y058r6L8q3^048:1y9 ab1badaRaT0@0r991aaY9pa#6ma%437r8$8paD15b21K042E7_2e1b2F0U1a9I0m13090s0I09a|5^ar8?2?0N5!a,8@a.aQaSaU0)aW289I0C9.939a0P939i74ba22bd4pbg0s0Vbk3G9LbJ0#bbbMbf04bh0D091.0d0t0V0tb$0Gb(bjbl3c9L0`b81=bKbc0ZbebObQb:3n0y0h0L2ubt2LbvaT9MbyaX9Rar0p0`0X0J1/0Z0gbA8=8/bUbWb{bNbZbPbR5sc1c3a-c622bw0ta?3TaYa6b01Bb40*aAa8058/3Q0u1_1(0c0kbf0t0U2L0r0~6W0j0Y0C0g0u2c0,b{0Z0y0P0$0p0G0~0h1aaic+c-0y0q0h0,22c!1i7v9 c|0U0G1%0Pd2bGc{0:0y0.0C0X0y2C2E2G0~cT1{0k0N1*c^0uaI0oda4ybucAa;2c3QaK1gd90^ad992c0C8_c!0cc$c(c*0tc~d00U2a0v0H2c0*2S0Z2S1Pb50B0g2MdH9i4p1uce0Gb=8YaPdA8Y9UaM9+180J2A0Pch0@2I0D0t0i0t0E0Y0t0R8/1798a,0@0Id~2Ae3d@dza:bxbza_9L179aald/1p8?0D0y0A0y0K0y0O9L0,0J2g0Ia2b?0r3$aj8=009~0c2;0;2Lea0(0oaGaI0t0Kc5a/bw0@aVcb8Y0s0D9L0A9L0K9L0O0z9 1k0Xe$cCa@bAe.0j9L0x9L0+9L0E0zea0t0Q9B8;d^eoc9eq9R2Iei0Nd 0k0te:0te=e~930t0O0tcdcfchaIckd|b?fgcBcDa^9R3@2K1z2C0Ic,aYbsfmfo0tf30tf50tf7e8cGd(8v0/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.128013bqO,9vià3o_x;lpwf( g0]6-)2As18+e%né4è[m5tCLRPhk:c.a=rySIu/7d050-0H0Q0!0i0p0D0u0Y0p0!0D0D0#010Q0i0q010406050D0*0O0O0!0$0%040(0l0p0*110l0J0u020!0O0q0o0u0T0H1b0$0d0*0H0D050+181a1c1e160q04051J1C1M0+1J160-0i0h0_0{0}0 0V0i0v0V0p1!0V0Q14050;0c0p0H1V0|0~011Z1#1%1#0Q1-1/1+0Q0$1K0Q0V0_1h0D0q0!0J0 0B011;1X010s0?0H0J1p0H1+27292e1?2h1/2k0O2m040b0u0U0$0l0q0l0D0i1k1m0/250$0$0H0Y2H1C2o0J1K0+232T2022211,0-2q0 1%0J2j2E1+1S1U0`1=2%0i2)0J0l2-1+0q2M1K2R2T2~17281m2/2f2@0$1b0p140E2Q3215312p341?3638140B3c293e2R2$013j0!39040k3n2S163q3h0 3t3v0L3y3p323r3E140P3H3A3J3C3s0l373u140y3O3f331W3i3T3k040,3H1N2|1C2-2W0-222#3R0Y2^2w0.1T1K2{0H2}3d3+3^0/403g3#0 0W140/0s3+3B47010r140u4d3Q4f0J0s140H0n3~0}0i1l4k462:0113040t4w3!4y0J141c0c2M4D3r4A0f3H4j4e4F140{0c0H0@4L3R4N4P3Z3K142@0H0*0-4Y4f4A0A0X3O0u4?4Q4l4y49040i4c1D3d4^4x354(0l4*4,4 3o514E2f0l4h4|0J4#4R53044I4K582S4$4Z144;5n154@5v5a4%044q0q0m0v5h4_5c140#5E523i4p4r2M4t4v5t5p4.144C5R5i5L5k0$4J0H4-4y4!5t5x3R4G044U4W1B5W5F1?5)2~5+4m4H5!5m305X0 4A0N5%5j4)4+645@140x635=5K0 0O0i140w68616a0A4=5w4?5S4S5z4r0m575_6r5G045I5*6y5Y5A5O2F5Q5 5?6l4B6k3s5|5#6N5^506D3D4T0!4V4X6d5b69044O6C606O5Z6Q6!4M146c6J6e6+666w416*4A6b6N6g3a6R6m6o6p6U014{2M0Q0*0$5g6)6K010D0E1402030k0g0o0t7j7l0o5J6#0 0l140G7s5y5A5C7y3R7v047x7d6?5-5/6Z6=7t4z6:6N5-6^71040x7C4f7E7G6x6*5-7A6_59757Y7W4y7g7i7k7m0A7p7m735`4`4p0@5$6.5q045s2~066p6q6*770:7a7c7!7e7J6X5:7T6;6`8c54567T7V5t160+433 3,8s0+3/1C0Q3;8x2Z2U6X1/2T3/1I457N2M0O0m0s0!0W0H0m0V0k141u1w1y1A0u81411P3e1J0e1m8K1c8X0$0!0u8X0u1/0u280$3^7a0^1j0?0i0D0K8@0l7a0u0h8 2G0H0$8=8Y0J0a4+0^1A0Q0u0*1m8^8`0$0^051v5f2h0n7}9r8Z92940Y0V0!8;9d4+0u2=0Q992)0f0u1l0u200=9I9b0u0D930D0z5l1:0v0!0*9A1:0-0*0u9E0-9L0q0*8 9S9,9.9:0^8?9U0*9W9Y0u0-2B2G9 9*9,0Z1N8%040S1:8^2j230K0D0!0v9(1:0p006F1A6H1m9h2K2M2O9T0i8Za7160*0p3e1%a80?0u0%0u8/9#0;0J9i2JacaM0V0M0D8Y930h8.aM8Y058r6M8q3_048:1z9 ab1cadaRaT0^0s991baY9pa#6na%447r8$8paD16b21L042F7_2f1c2G0V1b9I0n14090t0J09a|5_ar8?2@0O5#a,8@a.aQaSaU0*aW299I0D9.939a0Q939i75ba23bd4qbg0t0Wbk3H9LbJ0$bbbMbf04bh0E091/0d0u0W0ub$0Hb(bjbl3d9L0{b81?bKbc0!bebObQb:3o0z0i0M2vbt2MbvaT9MbyaX9Rar0q0{0Y0K1:0!0hbA8=8/bUbWb{bNbZbPbR5tc1c3a-c623bw0ua?3UaYa6b01Cb40+aAa8058/3R0v1`1)0c0lbf0u0V2M0s0 6X0k0Z0D0h0v2d0-b{0!0z0Q0%0q0H0 0i1baic+c-0z0r0i0-23c!1j7v9 c|0V0H1(0Qd2bGc{0;0z0/0D0Y0z2D2F2H0 cT1|0l0O1+c^0vaI0pda4zbucAa;2d3RaK1hd90_ad992d0D8_c!0cc$c(c*0uc~d00V2b0w0I2d0+2T0!2T1Qb50C0h2NdH9i4q1vce0Hb=8YaPdA8Y9UaM9+190K2B0Qch0^2J0E0u0j0u0F0Z0u0S8/1898a,0^0Jd~2Be3d@dza:bxbza_9L189aald/1q8?0E0z0B0z0L0z0P9L0-0K2h0Ja2b?0s3%aj8=009~0c2=0=2Mea0)0paGaI0u0Lc5a/bw0^aVcb8Y0t0E9L0B9L0L9L0P0A9 1l0Ye$cCa@bAe.0k9L0y9L0,9L0F0Aea0u0R9B8;d^eoc9eq9R2Jei0Od 0l0ue:0ue=e~930u0P0ucdcfchaIckd|b?fgcBcDa^9R3^2L1A2D0Jc,aYbsfmfo0uf30uf50uf7e8cGd(8v0: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. ↩