Aller au contenu

Analyser une expression arithmétique afin d'en extraire les « jetons »⚓︎

Dans un terminal Python il est possible de saisir des expressions arithmétiques, des « calculs », afin de les exécuter.

🐍 Console Python
>>> 2 +3* 4.5
15.5

Cette opération a l'air anodine, mais elle n'est pas si immédiate à effectuer pour Python.

L'une des étapes indispensables est d'analyser l'expression 2 +3* 4.5 afin d'en extraire les différents jetons (les anglo-saxons parlent de tokens comme dans cette page) : 2, +, 3, * et 4.5. Le but de cet exercice est d'effectuer cette analyse.

Remarque

On ne va pas procéder exactement comme Python mais l'idée générale reste la même.

On se donne donc des expressions arithmétiques, chaines de caractères Python, composées de :

  • nombres entiers ou décimaux (le séparateur décimal est le point '.') ;
  • de symboles d'opérations : '+', '-', '*' et '/' ;
  • de parenthèses '(' et ')' ;
  • d'espaces ' ' placées entre les jetons, mais pas toujours (voir remarque ci-dessous).

Remarque

On considère que les expressions arithmétiques proposées sont bien formées et correspondent donc à des calculs valides.

Par contre, les différents jetons (nombres et symboles) peuvent être séparés par zéro, un ou plusieurs espaces.

On demande d'écrire la fonction analyse qui prend en argument une telle expression et renvoie la liste des jetons, chacun étant une chaine de caractères. Les espaces seront ignorées.

Exemples

🐍 Console Python
>>> analyse("35.896 ")
["35.896"]
>>> analyse("3*   5+8")
["3", "*", "5", "+", "8"]
>>> analyse("3.9  * (5+8.6)")
["3.9", "*", "(", "5", "+", "8.6", ")"]
###
# Testsbksl-nlassert analyse("35.896 ") == ["35.896"]bksl-nlassert analyse("3py-str5 +8") == ["3", "py-str", "5", "+", "8"]bksl-nlassert analyse("3.9 py-str (5+8.6)") == ["3.9", "py-str", "(", "5", "+", "8.6", ")"]bksl-nlbksl-nl# Tests supplémentairesbksl-nlassert analyse("") == []bksl-nlassert analyse("1.986") == ["1.986"]bksl-nlassert analyse("((3))") == list("((3))")bksl-nlfrom random import choice, random, randrangebksl-nlbksl-nlfor numpy-undtest in range(20):bksl-nl jetons = []bksl-nl for py-und in range(randrange(10, 100)):bksl-nl jetons.extend(bksl-nl [bksl-nl "(",bksl-nl str(randrange(0, 2000)),bksl-nl choice("+-py-str/"),bksl-nl " " py-str randrange(1, 3),bksl-nl str(100 py-str random()),bksl-nl ")",bksl-nl choice("+-py-str/"),bksl-nl ]bksl-nl )bksl-nl assert analyse("".join(jetons)) == [j for j in jetons if j[0] != " "]bksl-nlbksl-nl 5/5

SYMBOLES = "+-py-str/()"bksl-nlbksl-nlbksl-nldef analyse(expression):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert analyse("35.896 ") == ["35.896"]bksl-nlassert analyse("3py-str5 +8") == ["3", "py-str", "5", "+", "8"]bksl-nlassert analyse("3.9 py-str (5+8.6)") == ["3.9", "py-str", "(", "5", "+", "8.6", ")"]bksl-nlbksl-nlSYMBOLES = "+-py-str/()"bksl-nlbksl-nlbksl-nldef analyse(expression):bksl-nl elements = []bksl-nl temp = []bksl-nl for caractere in expression:bksl-nl if caractere in SYMBOLES:bksl-nl if len(temp) > 0:bksl-nl elements.append("".join(temp))bksl-nl elements.append(caractere)bksl-nl temp = []bksl-nl elif caractere != " ":bksl-nl temp.append(caractere)bksl-nl if len(temp) > 0:bksl-nl elements.append("".join(temp))bksl-nl return elementsbksl-nlbksl-nlbksl-nl# Testsbksl-nlassert analyse("35.896 ") == ["35.896"]bksl-nlassert analyse("3py-str 5+8") == ["3", "py-str", "5", "+", "8"]bksl-nlassert analyse("3.9 py-str (5+8.6)") == ["3.9", "py-str", "(", "5", "+", "8.6", ")"]bksl-nlbksl-nl

A

L'algorithme est classique et ne présente pas de difficultés majeures. On le retrouve de façon très proche dans le calcul des termes de la suite audio-active de Conway et dans la compression Run-Length Encoding.

Il est aussi possible de résoudre l'exercice en utilisant une variable temporaire du type chaine de caractères. Alors, au lieu de faire temp.append(caractere), on fait simplement temp += caractere. De même l'instruction jetons.append("".join(temp)) devient jetons.append(temp).

Enfin, les expressions régulières permettent de résoudre rapidement ce problème. Une expression régulière est une chaine de caractères décrivant d'autres chaines de caractères. Par exemple chat(on)?s? désigne les mots chat, chaton, chats et chatons.

On utilise alors l'expression régulière \d+(?:\.\d+)?|[+\-*\/()]. Il est possible de tester cette expression régulière sur le site de regex101.

Le code Python devient alors :

🐍 Script Python
import re
def analyse(expression):
    return re.findall("\d+(?:\.\d+)?|[+\-*\/()]", expression)

Z

Conseil (1)

On pourra utiliser une variable temporaire afin de stocker les différents caractères composant un nombre.

Conseil (2)

Avant d'ajouter un symbole (opérateur ou parenthèse), on vérifiera que la variable temporaire est non vide. Si c'est le cas, on pourra ajouter un nombre et le symbole à la liste des jetons.

Conseil (3)

Un nombre n'est ni un symbole (opérateur ou parenthèse), ni une espace.