Exercices supplémentaires.

Écris une fonction qui prend en paramètre une chaîne texte et qui renvoie la même chaîne privée des espaces placés devant, s'il y en a. Les espaces situés ailleurs ne bougent pas.

Si la chaîne ne contient que des espaces, on renvoie la chaîne vide.

>>> enleve_espaces_devant("     coucou")
'coucou'
>>> enleve_espaces_devant("coucou")
'coucou'
>>> enleve_espaces_devant("     cou cou")
'cou cou'
>>> enleve_espaces_devant("     cou cou  ")
'cou cou  '
>>> enleve_espaces_devant("      ")
''

Piste : avance un indice tant que le caractère lu est un espace, puis renvoie la tranche qui commence à cet indice.

Même travail, mais à la fin de la chaîne cette fois.

>>> enleve_espaces_a_la_fin("coucou       ")
'coucou'
>>> enleve_espaces_a_la_fin("coucou")
'coucou'
>>> enleve_espaces_a_la_fin("cou cou                    ")
'cou cou'
>>> enleve_espaces_a_la_fin("     cou cou  ")
'     cou cou'
>>> enleve_espaces_a_la_fin("      ")
''

Piste : la même idée, en partant de l'indice len(texte)-1 et en reculant.

Écris une fonction qui prend en paramètres une chaîne texte et une chaîne caractere composée d'un seul caractère, et qui renvoie un int : le nombre de fois où ce caractère apparaît dans texte.

>>> nb_occurences("coucou", "c")
2
>>> nb_occurences("coucou", "h")
0
>>> nb_occurences("coucou.", ".")
1
>>> nb_occurences("coucou ça va?", " ")
2
>>> nb_occurences("", "a")
0

Écris une fonction qui prend en paramètre une chaîne nombre et qui renvoie un booléen : True si cette chaîne représente un nombre, False sinon.

Précisément, après avoir enlevé les espaces du début et de la fin (tu viens d'écrire les deux fonctions qu'il faut), la chaîne est un nombre si et seulement si les trois conditions suivantes sont réunies :

1. elle peut commencer par un + ou un - — un seul, et en première position ;
2. tout le reste n'est composé que de chiffres et d'au plus un point . ;
3. elle contient au moins un chiffre.

Attention, un espace à l'intérieur de la chaîne interdit tout.

>>> est_un_nombre("32")
True
>>> est_un_nombre("165204652456156416532")
True
>>> est_un_nombre("-32")
True
>>> est_un_nombre("+32")
True
>>> est_un_nombre("       -32          ")
True
>>> est_un_nombre("   000.0000002    ")
True
>>> est_un_nombre("-.0000002    ")
True
>>> est_un_nombre("32.")
True
>>> est_un_nombre("32x")
False
>>> est_un_nombre("32+")
False
>>> est_un_nombre("--32")
False
>>> est_un_nombre("3-2")
False
>>> est_un_nombre("- 32")
False
>>> est_un_nombre("-3 .2")
False
>>> est_un_nombre("-3.2.2")
False
>>> est_un_nombre(".")
False
>>> est_un_nombre("")
False

Piste : nb_occurences te dit tout de suite combien il y a de points.

Écris une fonction qui prend en paramètre une chaîne expression acceptée par est_un_nombre, et qui renvoie le nombre qu'elle représente : un int si ce nombre est entier, un float sinon.

Cette distinction n'est pas un détail : c'est elle qui fera écrire 13 et non 13.0 dans les calculs de la fin de page.

>>> conversion_nombres("     +32            ")
32
>>> conversion_nombres("32.0")
32
>>> conversion_nombres("32.5")
32.5
>>> conversion_nombres("-00032.00000000000000000000")
-32

Première difficulté : le caractère "7" n'est pas le nombre 7. Il faut retrouver la valeur d'un chiffre à la main, en le cherchant dans la chaîne "0123456789" : sa valeur est tout simplement son indice dans cette chaîne.

chiffres = "0123456789"
valeur = 0
while chiffres[valeur] != c:     # on avance tant qu'on n'est pas tombé sur le bon
    valeur += 1
# ici, valeur contient le nombre représenté par le caractère c

Deuxième difficulté : assembler les chiffres. On reconstruit d'abord la partie entière en multipliant le total par 10 avant d'ajouter chaque nouveau chiffre, puis la partie décimale en divisant par 10 de plus en plus.

Écris une fonction qui prend en paramètre une chaîne expression représentant un calcul sans parenthèse, et qui renvoie la liste des nombres et des opérations qui le composent. Les opérations gérées sont +, -, *, / et ^ (la puissance). Les espaces sont ignorés.

Les nombres deviennent des int ou des float (grâce à la question 5), les opérations restent des chaînes.

Reste un point à trancher : un - est-il une soustraction ou le signe du nombre qui suit ? La règle est la suivante :

Un + ou un - est le signe du nombre qui suit s'il est au tout début de l'expression ou s'il suit immédiatement une autre opération. Dans tous les autres cas, c'est une opération.

>>> liste_expression_numerique("     223    +   4          ")
[223, '+', 4]
>>> liste_expression_numerique("-223")
[-223]
>>> liste_expression_numerique("-2.5+45*7")
[-2.5, '+', 45, '*', 7]
>>> liste_expression_numerique("-45.000-7")
[-45, '-', 7]
>>> liste_expression_numerique("2^80+7")
[2, '^', 80, '+', 7]
>>> liste_expression_numerique("3*-2")
[3, '*', -2]

Piste : parcours l'expression caractère par caractère en accumulant dans une chaîne morceau tout ce qui appartient au nombre en cours ; dès que tu tombes sur une opération, tu convertis morceau et tu vides la chaîne.

Écris une fonction qui prend en paramètre une liste comme celles de la question 6 et qui renvoie le résultat du calcul.

L'algorithme respecte les priorités en trois passages :

1. tous les calculs de puissance, en parcourant la liste de la droite vers la gauche (car \(2^{3^3}=2^{27}\), et non \((2^3)^3\)) ;
2. tous les produits et quotients, de la gauche vers la droite ;
3. toutes les sommes et différences, de la gauche vers la droite.

Le sens de parcours n'est pas une coquetterie : [100, '/', 5, '/', 2] vaut 10 et non 40.

Une division renvoie un float, comme toujours en Python : ce n'est pas à toi de le corriger ici.

>>> evaluation_liste_sans_parenthese([2, '+', 3])
5
>>> evaluation_liste_sans_parenthese([2, '^', 3, '^', 3])
134217728
>>> evaluation_liste_sans_parenthese([2, '-', 3, '*', 4])
-10
>>> evaluation_liste_sans_parenthese([7])
7
>>> evaluation_liste_sans_parenthese([10, '/', 4])
2.5

Piste : travaille sur une copie de la liste. Quand tu traites une opération à l'indice i, remplace les trois cases i-1, i, i+1 par leur résultat : la liste raccourcit de deux cases à chaque fois, jusqu'à n'en contenir qu'une.

Une première satisfaction.

Complète la fonction calculs_expressions_sans_parentheses(expression) qui prend en paramètre une chaîne représentant un calcul sans parenthèse et qui en renvoie le résultat.

def calculs_expressions_sans_parentheses(expression):
    return  .............................................................

Oui, il n'y a bien qu'une seule ligne à écrire. Tu as déjà tout fait.

>>> calculs_expressions_sans_parentheses(" 23 + 5 * 4")
43
>>> calculs_expressions_sans_parentheses(" 23.0 + 5 * 4-2^3")
35
>>> calculs_expressions_sans_parentheses("2^3^2")
512

Une deuxième dans la foulée.

Complète la fonction calculs_expressions(expression) qui prend en paramètre une chaîne représentant un calcul pouvant contenir des parenthèses, et qui en renvoie le résultat.

L'idée est de trouver la première parenthèse fermante, de remonter jusqu'à la parenthèse ouvrante qui lui correspond, de calculer ce petit morceau sans parenthèse, puis de recommencer sur l'expression ainsi raccourcie. C'est une fonction récursive.

def calculs_expressions(expression):
    if .................... :          # si l'expression comporte un caractère "("
        indice_droit = 0
        while expression[indice_droit] != ")":
            indice_droit += 1
        indice_gauche = indice_droit
        while expression[indice_gauche] != "(":
            indice_gauche -= 1
        nb = calculs_expressions_sans_parentheses(expression[indice_gauche+1:indice_droit])
        if indice_gauche == 0 or expression[indice_gauche-1] in ["+", "-", "*", "/", "^"]:
            nouvelle_expression = expression[:indice_gauche] + str(nb) + expression[indice_droit+1:]
        else:   # pour traiter la multiplication sous-entendue. Par ex 4(2+6)
            nouvelle_expression = expression[:indice_gauche] + "*" + str(nb) + expression[indice_droit+1:]
        # print(nouvelle_expression)   # décommente pour voir l'expression se simplifier
        return ......................   # on relance calculs_expressions sur la nouvelle expression
    else:
        return ..........................    # on lance le calcul sans parenthèse

Avec le print décommenté, voilà ce que tu verras :

>>> calculs_expressions("3*(2*(4+5))")
3*(2*9)
3*18
54
>>> calculs_expressions("3 + 4.0 *(6 +(2*4-(5/2)+(3/2))) ")
3 + 4.0 *(6 +(2*4-2.5+(3/2)))
3 + 4.0 *(6 +(2*4-2.5+1.5))
3 + 4.0 *(6 +7.0)
3 + 4.0 *13
55

Deux remarques pour les curieux. D'abord, dans l'avant-dernière ligne, 6+7.0 donne 13 et non 13.0 : c'est conversion_nombres qui a transformé 7.0 en entier au tour suivant. Ensuite, le test indice_gauche == 0 est écrit avant l'autre : à l'indice 0, expression[indice_gauche-1] désignerait le dernier caractère de la chaîne, ce qui n'a aucun sens ici.

Cette version gère la multiplication sous-entendue à gauche d'une parenthèse (4(2+6)) mais pas à sa droite ((2+6)4) : les tests ne te la demandent pas.

Écris une fonction qui fait le même travail que la question 6, mais sur une expression littérale en \(x\), toujours sans parenthèse. La lettre "x" apparaît telle quelle dans la liste renvoyée.

Pour que la suite soit simple, on adopte une convention unique :

Tout x est précédé dans la liste de son coefficient et d'un "*". Ce coefficient est le nombre collé devant lui dans l'expression, ou 1 (ou -1) s'il n'y en a pas.

Autrement dit, la multiplication par \(x\) s'écrit toujours par juxtaposition (3x, -x, x^2) et jamais 3*x.

>>> liste_expression_litterale("x")
[1, '*', 'x']
>>> liste_expression_litterale("-x+5")
[-1, '*', 'x', '+', 5]
>>> liste_expression_litterale("x^2")
[1, '*', 'x', '^', 2]
>>> liste_expression_litterale("12x^2+54x-3.25")
[12, '*', 'x', '^', 2, '+', 54, '*', 'x', '-', 3.25]
>>> liste_expression_litterale("4x^5*2")
[4, '*', 'x', '^', 5, '*', 2]

Vérifie que la convention tient debout : [1, '*', 'x', '^', 2] se lit \(1\times x^2\) puisque la puissance est prioritaire sur le produit. Et -x^2 donne bien \(-(x^2)\), comme en mathématiques.

Complète la fonction evaluation_litterale_sans_parentheses(expression, valeur) qui prend en paramètres une chaîne représentant une expression littérale sans parenthèse et un nombre valeur, et qui renvoie le résultat obtenu en remplaçant \(x\) par valeur.

Ne pourrait-on pas utiliser deux fonctions déjà écrites, avec une toute petite étape entre les deux ?

>>> evaluation_litterale_sans_parentheses("-x+2", 45)
-43
>>> evaluation_litterale_sans_parentheses("x^2", 9)
81
>>> evaluation_litterale_sans_parentheses("32x^3-45x+22+10x-x", 3)
778
>>> evaluation_litterale_sans_parentheses("4x^5*2", 5)
25000

La récompense d'un dur labeur.

Complète la fonction evaluation_litterale(expression, valeur) qui prend en paramètres une chaîne représentant une expression littérale pouvant contenir des parenthèses et un nombre valeur, et qui renvoie le résultat.

C'est exactement la structure de la question 9, en remplaçant la fonction appelée au milieu.

def evaluation_litterale(expression, valeur):
    if ............................:          # si l'expression comporte un caractère "("
        indice_droit = 0
        while expression[indice_droit] != ")":
            indice_droit += 1
        indice_gauche = indice_droit
        while expression[indice_gauche] != "(":
            indice_gauche -= 1
        nb = evaluation_litterale_sans_parentheses(expression[indice_gauche+1:indice_droit], valeur)
        if indice_gauche == 0 or expression[indice_gauche-1] in ["+", "-", "*", "/", "^"]:
            nouvelle_expression = expression[:indice_gauche] + str(nb) + expression[indice_droit+1:]
        else:   # pour traiter la multiplication sous-entendue. Par ex 4(2+6)
            nouvelle_expression = expression[:indice_gauche] + "*" + str(nb) + expression[indice_droit+1:]
        # print(nouvelle_expression)   # décommente pour voir l'expression se simplifier
        return ........................................   # on relance evaluation_litterale
    else:
        return ..................................................   # on lance le calcul sans parenthèse

>>> evaluation_litterale("x(x+2)", 5)
x*7
35
>>> evaluation_litterale("4x^5(-2x+2+(x+5))", 5)
4x^5(-2x+2+10)
4x^5*2
25000

Ça y est : tu sais évaluer n'importe quelle expression littérale en \(x\). C'est très exactement ce que fait un logiciel de tracé de courbes avant de dessiner quoi que ce soit. Les quatre dernières questions vont plus loin : au lieu de calculer une valeur, elles manipulent le polynôme lui-même.

La première des quatre questions consacrées au développement d'expressions littérales.

Complète la fonction produit_litteral(expression) qui prend en paramètre une chaîne représentant un produit de facteurs en \(x\) (sans parenthèse, sans somme, sans différence) et qui renvoie un tuple de deux éléments : l'exposant de \(x\), puis le coefficient.

>>> produit_litteral("x^2*5*2x")   # rappel : x^2*5*2x = 10x^3
(3, 10)
>>> produit_litteral("3*8*5")
(0, 120)
>>> produit_litteral("3x*8*x^2*5*x*-2")   # oui, il manque des parenthèses à -2, le programme s'en remet
(4, -240)
>>> produit_litteral("x")
(1, 1)

Piste : appelle liste_expression_litterale, puis parcours la liste obtenue. Le coefficient est le produit de tous les nombres qui ne sont pas des exposants ; l'exposant est la somme des exposants de chaque "x" rencontré (1 quand aucun "^" ne le suit). Grâce à la convention de la question 10, il n'y a aucun cas particulier.

À partir d'ici, on ne calcule plus une valeur : on manipule le polynôme lui-même. Et pour le manipuler, il faut d'abord le ranger.

Un polynôme sera représenté par la liste de ses coefficients, rangés par degré croissant : la case d'indice i contient le coefficient de \(x^i\). Ainsi [-3, 54, 12] représente \(12x^2+54x-3\), et [0, 1] représente \(x\).

Écris une fonction polynome(expression) qui prend en paramètre une chaîne représentant une somme ou une différence de monômes sans parenthèse, et qui renvoie cette liste.

Deux conventions pour que la représentation soit unique :

• pas de zéro inutile à la fin de la liste (le dernier coefficient n'est jamais nul) ;
• le polynôme nul est représenté par [0].

>>> polynome("12x^2+54x-3")
[-3, 54, 12]
>>> polynome("5")
[5]
>>> polynome("x")
[0, 1]
>>> polynome("-x^3")
[0, 0, 0, -1]
>>> polynome("x^2+1")
[1, 0, 1]
>>> polynome("x-x")
[0]

Piste : découpe d'abord l'expression en monômes, en coupant sur les + et les - qui sont des opérations — c'est exactement la règle de la question 6, et le signe reste collé au monôme qui suit. Chaque morceau est alors un produit : produit_litteral te donne son degré et son coefficient, il ne reste qu'à le déposer dans la bonne case.

Pour agrandir la liste au fur et à mesure : while len(coefficients) <= exposant: coefficients.append(0).

Écris une fonction qui prend en paramètres deux listes de coefficients comme celles de la question 14 et qui renvoie la liste des coefficients de leur produit, avec les deux mêmes conventions.

Le principe tient en une phrase : en multipliant le terme de degré \(i\) de l'un par le terme de degré \(j\) de l'autre, on obtient un terme de degré \(i+j\). Deux boucles imbriquées suffisent.

>>> produit_polynomes([1, 1], [2, 1])     # (x+1)(x+2)
[2, 3, 1]
>>> produit_polynomes([2], [3])
[6]
>>> produit_polynomes([-1, 1], [1, 1])    # (x-1)(x+1)
[-1, 0, 1]
>>> produit_polynomes([0], [1, 1])
[0]

Piste : un produit d'un polynôme de degré \(n\) par un polynôme de degré \(m\) a au plus le degré \(n+m\). Tu peux donc partir d'une liste de zéros de la bonne longueur, puis y ajouter chaque produit à sa place.

Le bouquet final.

Écris une fonction developpe(expression) qui prend en paramètre une chaîne représentant un produit de facteurs — chaque facteur étant soit un groupe entre parenthèses, soit un monôme — et qui renvoie la liste des coefficients du polynôme développé.

Comme à la question 9, les facteurs sont écrits côte à côte, sans * entre eux. Un signe moins devant une parenthèse s'écrit donc -1(x+1). Il n'y a pas de parenthèses imbriquées.

>>> developpe("(x+1)(x-1)")
[-1, 0, 1]
>>> developpe("(x+1)(x+1)")
[1, 2, 1]
>>> developpe("3x(x+2)")
[0, 6, 3]
>>> developpe("(2x-3)(x+4)")
[-12, 5, 2]
>>> developpe("2(x+1)(x+1)(x+1)")
[2, 6, 6, 2]
>>> developpe("x^2+1")
[1, 0, 1]

Piste : pars du polynôme [1] (l'élément neutre du produit) et parcours la chaîne. Dès que tu rencontres une parenthèse ouvrante, va chercher la fermante, passe le contenu à polynome et multiplie. Les caractères rencontrés en dehors des parenthèses forment eux aussi un facteur, à passer à polynome et à multiplier de la même façon.

Le dernier test de la page est le plus joli : il vérifie que ton polynôme développé, évalué en \(x=3\), donne bien le même nombre que evaluation_litterale sur l'expression de départ. Les deux moitiés de la page se répondent.

Regarde developpe("(x+1)(x+1)") qui renvoie [1, 2, 1] : tu viens de faire démontrer une identité remarquable à ton programme. C'est le cœur d'un logiciel de calcul formel, et tu l'as écrit en partant de zéro.