P
'
t
i
t
e
C
h
a
t
t
e
 
spacer~ THE CODE THAT IS THE HARDEST TO DEBUG IS THE CODE THAT YOU KNOW CANNOT POSSIBLY BE WRONG Articles | Connexion
 
~Fonctions et hashtables

Précédent  
  Python  
  Suivant
 Présentation

Grâce aux listes, le programmeur Python peut manipuler des dictionnaires à clés et des piles. Ces caractéristiques, soutenues par les fonctions, nous serviront de base pour l'écriture d'une calculatrice en RPN.
 Sommaire


 Une calculatrice RPN

Le système de notation de calculs "RPN" est bien connu de tous les utilisateurs de calculatrices HP. La fameuse HP48 avait en son temps séduit de nombreuses personnes par son approche originale du calcul. Le système RPN (pour Reverse Polish Notation) incarne une forme d'écriture particulière puisque inversée. Prenons l'exemple simple de l'expression mathématique "2 + 3". Le calcul équivalent en RPN se note "2 3 +". Cette notation, bien que très obscure au début, s'avère extrêmement puissante puisqu'elle évite l'écueil des parenthèses multiples. Examinons maintenant l'expression "2 + (3 * (4 + 1))". En RPN nous pouvons déomposer le calcul en petites étapes pour écrire "4 1 + 3 * 2 +".

Pour bien comprendre le fonctionnement de cette notation, il convient de savoir qu'une pile se trouve au cour des machines RPN. Lorsque la calculatrice évalue une expression, chaque terme (le séparateur unique est l'espace) se voit déposé au sommet d'une pile. Dès qu'un opérateur mathématique intervient, la machine prend au sommet de la pile le nombre exact d'opérandes requis pour effectuer le calcul.

La réalisation de l'outil met en ouvre les dictionnaires, les piles et les fonctions. Nous venons d'expliquer l'utilité de la pile. Les dictionnaires nous permettent d'associer une valeur à une clé donnée. Dans notre cas, nous allons associer à un nom de fonction mathématique, comme cos, une valeur. La valeur en question sera une fonction. Python permet en effet de manipuler les fonctions comme des objets.

Si maFonction(x) une fonction définie dans un script, Python permet de réaliser ceci:

f = maFonction
print f(2)
       
      
JextCopier dans Jext | Jext | Plugin Codegeek

 Les fonctions

Pour déclarer une fonction en Python il convient d'employer le mot clé "def". Voici un exemple:

def reponse(x):
  print "La réponse est", x
       
      
JextCopier dans Jext | Jext | Plugin Codegeek
Nous sommes en présence d'une fonction attendant en paramètre une valeur désignée par la variable x. Pour documenter la fonction, une simple chaîne de caractère à la suite de la déclaration suffit:

def reponse(x):
  "La fonction réponse affiche x"
  print "La réponse est", x
       
      
JextCopier dans Jext
Les fonctions peuvent aussi contenir des paramètres optionnels. En attribuant une valeur par défaut aux paramètres, l'interpréteur permettra de ne pas définir tous les paramètres:

def f(x, y = 2, z = 3):
  print x * y * z
       
      
JextCopier dans Jext
L'appel de f(2) sera équivalent à f(2, 2, 3) et f(2, 5) sera équivalent à f(2, 5, 3). Il arrivera que le programmeur souhaite changer la valeur du dernier paramètre sans préciser celle du paramètre précédent. Une fois de plus, Python offre un moyen simple d'y parvenir, les paramètres nommés. Ainsi, l'appel f(2, z = 5) s'interprétera comme f(2, 2, 5).

Notre calculatrice devra proposer une fonction par fonction mathématique supportée. Chacune de ces fonctions nécessitera le passage d'un paramètre. Il s'agira d'un tableau contenant les opérandes nécessaires au fonctionnement de la fonction. La fonction cos recevra ainsi un tableau de 2 éléments alors que la fonction + recevra un tableau d'un seul élément.

Afin de retourner le résultat de nos calculs, les fonctions que nous allons implémenter utiliseront le mot-clé "return". Si l'opération peut-être effectuée, c'est à dire si le nombre d'opérandes est suffisant, nos fonctions retourneront le résultat du calcul. Dans le cas contraire, la valeur None sera renvoyée. La vérification du nombre d'opérandes utilise la fonction len(). Voici par exemple la définition de la multiplication:

def compute_multiply(ops):
    if len(ops) == 2:
        return ops[1] * ops[0]
    else:
        return None
       
      
JextCopier dans Jext
Sachez enfin que les fonctions Python peuvent retourner plusieurs valeurs. Ce sont les tuples qui permettent ceci. Un tuple se veut un ensemble de valeur. Un tuple s'écrit comme une liste, mais avec des parenthèses: tuple = (1, 2, "trois"). Voici un exemple d'utilisation des tuples dans des fonctions:

def getOrigin():
  return (0, 0)
x, y = getOrigin()
       
      
JextCopier dans Jext
Nous observons ici que le langage Python permet de réaliser des assignations multiples de variables. On peut ainsi échanger le contenu de deux variables en écrivant "a, b = b, a".


 Pile et dictionnaires

Pour les interpréteurs Python, rien ne différencie une pile d'une liste. En effet, les listes possèdent des fonctions leur permettant de se comporter comme des piles.

pile = [] #liste vide
pile.append(1)
pile.append(2)
x = pile.pop()
       
      
JextCopier dans Jext | Jext | Plugin Codegeek
La fonction append() ajoute un élément au sommet de la pile. A l'inverse, la fonction pop() retire l'élément au sommet et renvoie sa valeur.

Un dictionnaire se déclare de manière un peu différente.

dic = { "clé1" : 1, "clé2" : 2, "clé3" : 3 }
print dic["clé1"] #affiche 1
print dic["clé3"] #affiche 3
       
      
JextCopier dans Jext
Lorsque le programmeur désire ajouter une nouvelle paire de clé/valeur il lui faut procéder comme pour une assignation:

#change la valeur associée à clé1
dic["clé1"] = 33
#ajoute une clé key de valeur 17
dic["key"] = 17
       
      
JextCopier dans Jext
Dans le cadre de notre application, le dictionnaire dont nous allons nous servir associera à chaque nom de fonction un tuple. Ce tuple comprendra un élément décrivant le nombre d'opérandes nécessaires pour appeler la fonction et l'objet Python correspondant à la fonction.

_op_ = {"cow" : (1, compute_cos),   "/"   : (2, compute_division), \
"-"   : (2, compute_minus), "*"   : (2, compute_multiply), \
"+"   : (2, compute_plus),  "sin" : (1, compute_sin)}
       
      
JextCopier dans Jext
La définition sur plusieurs lignes impose d'employer le caractère \. L'emploi de ce dictionnaire est trivial. Pour accéder au tuple de la fonction cos() nous exécutons _op_["cos"]. Le nombre d'arguments attendus par cette fonction est connu grâce à _op_["cos"][0]. Nous avons dit qu'un tuple était une liste fixe. Ses éléments sont donc indéxés.


 La fonction compute()

La partie principale de notre outil se situe dans la fonction compute(). Son paramètre unique doit être une chaîne de caractère. La partie main() de l'application appelle compute() en lui donnant soit une chaîne lue depuis l'entrée standard soit une chaîne offerte en paramètre au script. La première étape consiste à découper la chaîne de caractère en mots utilisables par notre interpréteur. C'est ce que réalise la fonction split() des chaînes de caractère. Nous obtenons alors une liste de mots. Le parcours de cette liste se fait par énumération:

tokens = line.split()
for token in tokens:
  # .
       
      
JextCopier dans Jext | Jext | Plugin Codegeek
A chaque passage dans la boucle for, la variable token contient le mot courant. Si ce mot correspond à une valeur numérique, le test est réalisé grâce à une expression régulière, nous l'ajoutons au sommet de la pile nommée "stack". Sinon, il s'agit peut-être d'une fonction. L'interpréteur récupère alors le nombre d'opérandes attendus et l'objet fonction:

op, count = _op_[token][1], _op_[token][0]
       
      
JextCopier dans Jext
L'objet op peut alors être appelé comme une fonction normale. Si aucun tuple n'est trouvé, une exception est générée et nous interrompons l'interprétation. Une fois l'appel à la fonction effectué, nous testons si l'opération a pu être calculée avec succès. En ce cas, la valeur du calcul est placée au sommet de la pile. Sinon, l'utilisateur est prévenu de l'erreur.

La prochaine étape de notre initiation consistera à réécrire cet exemple en employant des objets plutôt que des fonctions.


 Exemple complet

#! /usr/bin/env python

##
## IMPORTS STATEMENTS
##
# sin() and cos()
import math
import re
import sys

def compute_cos(ops):
    if len(ops) == 1:
        return math.cos(ops[0])
    else:
        return None

def compute_division(ops):
    if len(ops) == 2:
        if ops[0] == 0:
            return None
        else:
            return ops[1] / ops[0]
    else:
        return None

def compute_minus(ops):
    if len(ops) == 2:
        return ops[1] - ops[0]
    else:
        return None

def compute_multiply(ops):
    if len(ops) == 2:
        return ops[1] * ops[0]
    else:
        return None

def compute_plus(ops):
    if len(ops) == 2:
        return ops[1] + ops[0]
    else:
        return None

def compute_sin(ops):
    if len(ops) == 1:
        return math.sin(ops[0])
    else:
        return None

# grammar
_nb_ = "[-]?\d+[\.]?\d*"
_op_ = {"cos" : (1, compute_cos),   "/"   : (2, compute_division), \
        "-"   : (2, compute_minus), "*"   : (2, compute_multiply), \
        "+"   : (2, compute_plus),  "sin" : (1, compute_sin)}

# performs the computation
def compute(line):
    # the stack
    stack = []
    # tokens
    tokens = line.split()
    # state
    error = 0

    # stack pushes
    for token in tokens:
        # if the token is a number
        if re.match(_nb_, token) != None:
            try:
                stack.append(float(token))
            except:
                # unknown operator
                print "Invalid number:", token
                error = 1
        else:
            # we check if the token is an operator
            try:
                op, count = _op_[token][1], _op_[token][0]
                # it is a valid operator
                opList = []

                # we check if the stack contains enough elements
                if len(stack) >= count:
                    # we pops the requested amount of operands
                    for i in range(count):
                        opList.append(stack.pop())
                    # compute
                    result = op(opList)
                else:
                    result = None
                    print count - len(stack), "operand(s) is(are) missing"

                # check result
                if result:
                    stack.append(result)
                else:
                    # error during calcul
                    print "Following operation caused an error:", token
                    error = 1
            except:
                # unknown operator
                print "Unknown keyword:", token
                error = 1

        if error:
            break
    else:
        print "Result:", stack.pop()

# main
def main():
    print "\n", sys.argv[0], "is an RPN computation program."
    print "(C)2001 Romain Guy"
    # RPNit can perform calculs from an argument or
    # from the standard input pipe
    if len(sys.argv) < 2:
        sys.stdout.write("> ")
        compute(sys.stdin.readline())
    else:
        compute(sys.argv[1])

##
## MAIN ENTRY POINT
##
if __name__ == '__main__':
    main()

# End of rpnit.py
       
      
JextCopier dans Jext | Jext | Plugin Codegeek


par Romain Guy
romain.guy@jext.org
http://www.jext.org
Dernière mise à jour : 14/10/2006


Précédent  
  Python  
  Suivant

 
#ProgX©2005 Mathieu GINOD - Romain GUY - Erik LOUISE