Aller au contenu

Expression parenthésée⚓︎

Une expression arithmétique ne comportant que les quatre opérations \(+, - , ×, ÷\) peut être représentée sous forme d'arbre. La disposition des nœuds indique les priorités opératoires.

  • Les feuilles représentent des nombres, elles ne possèdent pas de sous-arbre.
  • Les nœuds internes représentent des opérateurs binaires, ils possèdent exactement deux sous arbres.

Par exemple, avec un parcours en profondeur infixe de l'arbre ci-dessous, on peut retrouver l'expression notée habituellement : \(((3 × (8 + 7)) - (2 + 1))\).

arbre

La classe Noeud ci-après met en œuvre une structure d'arbre adaptée.

Il ne s'agit pas exactement d'un arbre binaire

Avec un arbre binaire, tous les nœuds ont exactement deux sous-arbres. Un sous arbre peut alors être vide.

Ici, il s'agit d'un arbre d'expression pour opérateurs binaires. C'est un arbre d'arité 2 ; il n'y a pas, ici, de notion d'arbre vide. Ici, chaque nœud possède 0 ou 2 sous-arbre.

Compléter la fonction récursive expression_parenthesee qui prend en paramètre un objet de la classe Noeud qui désigne la racine d'un arbre et qui renvoie l'expression arithmétique représentée par l'arbre passé en paramètre, sous forme d'une chaine de caractères contenant des parenthèses.

Exemple

Résultat attendu avec l'arbre ci-dessus :

🐍 Console Python
>>> somme_1 = Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))
>>> somme_2 = Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None))
>>> produit_1 = Noeud(Noeud(None, 3, None), '*', somme_1)
>>> expression = Noeud(produit_1, '-', somme_2)
>>> expression_parenthesee(expression)
'((3*(8+7))-(2+1))'

D'autres exemples

🐍 Console Python
>>> feuille = Noeud(None, 5, None)
>>> expression_parenthesee(feuille)
'5'
🐍 Console Python
>>> somme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))
>>> expression_parenthesee(somme)
'(2+3)'
🐍 Console Python
>>> somme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))
>>> produit = Noeud(Noeud(None, 4, None), '*', somme)
>>> expression_parenthesee(produit)
'(4*(2+3))'
###(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.128013fe)à61ipmSvk(q5rxNd;Po/aR lé+C8Ly7_3:-tg.U?=swc,èh2nb094u050u0d0O0z0i0C0U0B0W0C0z0U0U0T010O0i0j010406050U0*0k0k0z0r0I040l0x0C0*0~0x0#0B020z0k0j0v0B0A0d180r0p0*0d0U050y1517191b130j04051G1z1J0y1G130u0i0m0?0^0`0|0Z0i0P0Z0C1X0Z0O11050.0$0C0d1S0_0{011W1Y1!1Y0O1*1,1(0O0r1H0O0Z0?1e0U0j0z0#0|0!011.1U010c0:0d0#1m0d1(24262b1:2e1,2h0k2j040b0B0w0r0x0j0x0U0i1h1j0,220r0r0d0W2E1z2l0#1H0y202Q1}1 1~1)0u2n0|1!0#2g2B1(1P1R0@1/2!0i2$0#0x2*1(0j2J1H2O2Q2{14251j2,2c2;0r180C110B0h2N2 122~2m311:3335370!3a263c2O2Z013h0z36040B0L3l2P133o3f0|3r3t0B0)3x3n2 3p3D370q3H3z3J3B3q0x343s370g3O3d301T3g3T3i3u0J3Y3A3#3C3%3V3u0G3+3Q3-3S3U3E0(3?3e3^3L040h0%3}3!2-3_3(0h391A3b3P3~46400h3k4b3m4d45323/3t0h3w4j3y3Z3K4o110h3G4s3I4e4n3`4x3N4A4l4v4E413X4H4u3R4g3*4N3,4f4w413=4S3@4U4K0h3|4Y4C3$4K0!434(4m4*3(0!4a2{4I4P4V0!4i4@4O3 4`4r4}4T4D4;4z524Z543:0!4G574)3.4+4M5d4/5f4;4R5i4J4;4X5n4_4+4%5r4 4K0L4-2}1M2_1z2*2T0u1 2Y3R0W2=2t0+1Q1H2^0d2`3b3H055K0,5S5e010n113f5U531:0V375(583g0W110t0x0d0*0u5-5Z10040M443p5+3u0B635`5j010U0u11021v0x0O0v6b0*6d6f6c6e5 3R6837630B0F3#1-0i1n0C0D2s0#0.6A0B0*1j0#0a5^0B1P242B260O6J1-0L0B0z1_0r0i0$1g0=5~4.3p6o62630N0B0m3s5@0r0B0M0B0^6+6-0*6/2G0C02030L0(0v0D0~1v0-0O0d0X6m3^6%6q0B6*0P0z0*0W0Z1-6;1,0B0U0x0*0U0N190$2J0B0f0B7f7h7j0Q79467b6q6*0u2y2D7k6=1-7o7q7s0r7u1-7x7I0x7K7C4H4^7a696(6r1-0#6}6 0v1x6O250U0X0B0i0W0i7=2A6_6D1j7t7v0$2/0/2J7=180i0=7{6/6E6S7R7v0u7+70192D0D0B0!7Y5v7E7$7c6g6i8s6e8u0v3O7c4~465#040,0c65605,4A8A2c0c0k110K0K2/2D8P8G3R5|0o8U3^0$5|0U0d0C8F8J5)0|5|784A0B8K3g117z7i0d8Y468-3H8:8+3q116,1,6_8`2c8|8/8;3C117V7K951:5|0e6!4@7c8z8 8!118$8(9e0|0x118n5T8 0#8?7g8^8}99019t040T9C9x9z7A8_4H9k6q9D9n049p8)2}8 9F9v3m9D9y04926.9I5.9s119H989J9$6^0r8y9O8~9*019R9T9r9E9u9}9#9c769)5Z9F9-2{9^5Za17Ja37Z9l9_8C8E9}618:8*9_0#0c117.0K0c5@0:1,9}8W9}9{8%9U9w9_9g9i4c9@a9660U29048w1r0#0m7W1-8b0$0x1e0D2g7=6?0r0D2A0#8$7w6:7M0B6G6I7.0N0:7}1-at0*av1-0S8w9?9O9D8C2J0O6_0#a466aA9qama59 bb669#8@7jb73p0x6187bj3R0n5:045=2$bo3^bl11265_9.9_b9aC9Z9Wbd9Van9bac9Ma89Dbx04bnbB5Zbq5;1ibM4c067!8B9b0dbE2P9Daka0ap040d0s5Q0`0i1i0K252J6A7j8$bXbFaE118Xbe3Kaqax119ha aJ3p8C0ib(3u9!c5c33R9Xa0aq0U0Oasau0Cawci3^8Wc89N9@b111b3b5bv4f0$9o1}c604c2bIaachcL66ckct4f919;cI0ec9czb.0;b~b)8 5|aG4kaIcYcB0rb6bS66aycxaIb08 0U0h6a6~700o8g8xc?c@afbc040EcD32aqb:2Jb=b@b_2g201x0dc#5Yc;c1clb.9}cQcOc404bhdk9D9gc9d364bGd6d88=dpcR2cdraDcM9:939=d2dAcacj11d7c:dtb/b;2Cde19dgb|djcIcKdKbfcNd+bkbHd.4PbK7Wadds8Vc7dzdAbOdTdE0|c`c|7,0ed0d|dBc004cW4N0y5W5R1K5C0y5E1z0O5Gek2W2R0z1+efei5O1Fdl3p2J0kas0z0n0d0K0Z0L111r1t746Z5U1M3c1G0l0i8:eedGeT0B7.a@0Ba_a{7=1i7n7p0Z0/760Bb`aR0I0d6/6?9%7|0U2688d#b{0Y8$7=0u1i0W0Be%e.aSeS5L3p1=1Z1#1%ew4PcF9ScHdH9fdnfk9adGd_bwd:b dLe@dOfq8{d{8Jed5L3u6E1-7i0/2$6P0?190z2L0Ydc7Y1N1I1c2/1ie$30f26T0YfI0u0*0B760se,0z0m2K6=002z0D0r6T6.f85XdUeV6!fR0*0C3c1!040RfIdfe}a*7p0mf?6A0d7Yg213g20H00dXdcdZ1jg6200D0UaY6Jf%7O7r7 7T7y9A7ja,5VfCgddv1zeT1zgf05ghf:0jf=f@e^7p0=0c3%1-2Gf)76ge0ig1g#gigk1xgm0Bgo0Zgqgsf$e(7Pgxa+a27LgD5Xgdg_gHfCgJg#ggg#g41-g-e~a^e;18gcg!3c0yf he0,0.0:0U04.