TP2 IPT : les Piles et la NPI

Soumis par mathemator le 7 Novembre 2014 - 12:38am

Une version purement pile. Les piles sont des listes qui se remplissent et se vident par la gauche:

Python

#! python3.4
#-*- coding: utf-8 -*-
 
import operator
 
###########################################################
#####
#####         IMPLÉMENTATION SPÉCIFIQUE (ICI AVEC listes par la gauche)
#####
###########################################################
class Pile(list):
 
    def est_vide(self):
        return len(self) == 0
 
    def empile(self,elmt):
        self[:] = [elmt] + self
 
    def depile(self):
        t = self[0]
        self[:] = self[1:]
        return t
# on peut faire aussi self.pop(0) ou del l[0] mais ce sont des boîtes noires
 
##############################################################
####
#### BARRIÈRE D'ABSTRACTION : NE DÉPEND PAS DE L'IMPLÉMENTATION DES PILES
####
################################################################
 
 
def from_liste(lst_p):
    """
    Construit une pile à partir d'une liste python
   
    """
    p = Pile()
    for k in lst_p[::-1]:
        p.empile(k)
    return p
 
operations = {
    '+' :  operator.add, '-' :  operator.sub,
    '*' :  operator.mul, '%' :  operator.mod,
    '**': operator.pow,  '//': operator.floordiv
}
 
def hp(expression_int):
    pile = Pile()
    pile_exp = from_liste(expression_int.split())
    while not pile_exp.est_vide():
        val = pile_exp.depile()
        if val in operations:
            op = operations[val]
            n1 = pile.depile()
            n2 = pile.depile()
            pile.empile(op(n2,n1))
        else:
            pile.empile(int(val))
    r = pile.depile()
    if not pile.est_vide():
        raise SyntaxError('Expression non valide')
    else:
        return r
    
def hp_inter():
    pile = Pile()
    print(str(pile))
    while True:
        try:
            val = eval(input("rentrer un entier ou un 'opérateur' ou 'fin': "))
            if type(val) in [int,float]:
                pile.empile(val)
                print(str(pile))
            elif val in operations:
                op = operations[val]
                n1 = pile.depile()
                n2 = pile.depile()
                pile.empile(op(n2,n1))
                print(str(pile))
            elif val == 'fin':
                break
        except ValueError:
            continue
 
 
def casio(expression):
    pilop      = Pile()
    pilnum     = Pile()
    pilpar     = Pile()
    expression = '( ' + expression + ' )'
    pile_exp = from_liste(expression.split())
    while not pile_exp.est_vide():
        val = pile_exp.depile()
        if val == ')':
            pilpar.depile()
            n1 = pilnum.depile()
            n2 = pilnum.depile()
            op = operations[pilop.depile()]
            pilnum.empile(op(n2,n1))
        elif val == '(':
            pilpar.empile(val)
        elif val in operations:
            pilop.empile(val)
        else:
            pilnum.empile(int(val))
    r = pilnum.depile()
    if not (pilop.est_vide() and pilpar.est_vide() and pilnum.est_vide()):
        raise SyntaxError('expression non valide')
    else:
        return r

On peut sinon utiliser pop et append mais dans ce cas les listes se lisent par la droite. Inconvénient : l'expression postfixe est écrite de gauce à droite donc sera elle dépilée par la gauche ce qui rend le tout un peu incohérent.

Python

import operator
 
 
######################################################################
#####
#####         IMPLÉMENTATION SPÉCIFIQUE (ICI AVEC LES LISTES DΕ PYTHON donc par la droite)
#####
######################################################################
 
 
class Pile(list):
 
    def est_vide(self):
        return self == []
 
    def empile(self,elmt):
        return self.append(elmt)
 
    def depile(self):
        return self.pop()
 
##############################################################
####
#### BARRIÈRE D'ABSTRACTION : NE DÉPEND PAS DE L'IMPLÉMENTATION DES PILES
####
################################################################
 
operations = {
    '+' :  operator.add, '-' :  operator.sub,
    '*' :  operator.mul, '%' :  operator.mod,
    '**': operator.pow,  '//': operator.floordiv
}
 
# le for "dépile" l'expression par la gauche
 
def hp(expression_int):
    pile = Pile()
    for val in expression_int.split(): #ici on lit l'expression dans le même sens que la pile
        if val in operations:
            op = operations[val]
            n1 = pile.depile()
            n2 = pile.depile()
            pile.empile(op(n2,n1))
        else:
            pile.empile(int(val))
    r = pile.depile()
    if not pile.est_vide():
        raise SyntaxError('Expression non valide')
    else:
        return r
    
 
def hp_inter():
    pile = Pile()
    print(str(pile))
    while True:
        try:
            val = eval(input("rentrer un entier ou un 'opérateur' ou 'fin': "))
            if type(val) in [int,float]:
                pile.empile(val)
                print(str(pile))
            elif val in operations:
                op = operations[val]
                n1 = pile.depile()
                n2 = pile.depile()
                pile.empile(op(n2,n1))
                print(str(pile))
            elif val == 'fin':
                break
        except ValueError:
            continue
 
 
def casio(expression):
    pilop      = Pile()
    pilnum     = Pile()
    pilpar     = Pile()
    expression = '( ' + expression + ' )'
    for val in expression.split():
        if val == ')':
            pilpar.depile()
            n1 = pilnum.depile()
            n2 = pilnum.depile()
            op = operations[pilop.depile()]
            pilnum.empile(op(n2,n1))
        elif val == '(':
            pilpar.empile(val)
        elif val in operations:
            pilop.empile(val)
        else:
            pilnum.empile(int(val))
    r = pilnum.depile()
    if not (pilop.est_vide() and pilpar.est_vide() and pilnum.est_vide()):
        raise SyntaxError('expression non valide')
    else:
        return r