1: ### implémentation du type abstrait Pile 2: ### avec des listes Python 3: 4: def pilevide (): 5: return [] 6: 7: # choix : sommet de pile en fin de liste 8: def ajoute (e,p) : 9: p.append(e) 10: 11: def sommet(p) : 12: return p[len(p)-1] 13: 14: def depile (p) : 15: p.pop() 16: 17: def estvide(p): 18: return len(p)==0 19: 20: def copiepile(p) : 21: return list(p) 22: 23: def affichepile(p): 24: print() 25: print('| |') 26: i = len(p)-1 27: while i>=0: 28: print('|---|') 29: print('|',p[i],'|') 30: i = i-1 31: print(' ---') 32: 33: ### fonctions avancées sur les piles 34: 35: # inversion d'une pile 36: 37: def inversepile(p): 38: q = copiepile(p) 39: r = pilevide() 40: while (not(estvide(q))): 41: ajoute(sommet(q),r) 42: depile(q) 43: return r 44: 45: # vérification parenthésage 46: 47: def estouvrante (c) : 48: return (c=='(') or (c=='{') or (c=='[') 49: 50: def fermante (c) : 51: if (c=='('): 52: return ')' 53: elif (c=='{'): 54: return '}' 55: elif (c=='['): 56: return ']' 57: else: 58: return '?' 59: 60: def verifparenthese (texte): 61: print() 62: print("-> vérification de «",texte,"»") 63: # on commence avec une pile vide 64: p = pilevide() 65: # parcours du texte caractère par caractère 66: for i in range(0,len(texte)): 67: if estouvrante(texte[i]): 68: # si le caractère est une ouvrante... 69: # ... on empile la fermante associée 70: ajoute(fermante(texte[i]),p) 71: else: 72: # sinon la fermante rencontrée doit 73: # être la même que celle sur la pile 74: if (estvide(p) or (texte[i] != sommet(p))): 75: print("erreur caractère",i) 76: else: 77: depile(p) 78: # à la fin du texte, la pile doit être vide 79: if (estvide(p)): 80: print("fin de vérification") 81: else: 82: # sinon il y a un problème 83: print("pile non vide !") 84: affichepile(p) 85: print() 86: 87: # évaluation d'une expression arithmétique 88: 89: def estoperation(c): 90: return (c=='+') or (c=='-') or (c=='*') or (c=='/') 91: 92: def ptitcalcul (o,a,b): 93: if (o=='+'): 94: return a+b 95: elif (o=='-'): 96: return a-b 97: elif (o=='*'): 98: return a*b 99: elif (o=='/'): 100: return a/b 101: 102: def evaluepostfix (expression): 103: print() 104: print("-> évaluation de «",expression,"»") 105: # on commence avec une pile vide 106: p = pilevide() 107: # parcours de l'expression caractère par caractère 108: for i in range(0,len(expression)): 109: if estoperation(expression[i]): 110: # si c'est un opérateur 111: # on dépile un premier entier 112: n = sommet(p) 113: depile(p) 114: # et puis un autre 115: m = sommet(p) 116: depile(p) 117: # on effectue le calcul 118: r = ptitcalcul(expression[i],n,m) 119: # et on empile le résultat 120: ajoute(r,p) 121: else: # c'est un entier et on l'empile 122: ajoute(int(expression[i]),p) 123: # à la fin, le résultat est sur la pile 124: print("résultat :",sommet(p)) 125: print() 126: 127: ### tests 128: 129: mapile = pilevide() 130: 131: ajoute(2,mapile) 132: ajoute(8,mapile) 133: ajoute(5,mapile) 134: ajoute(0,mapile) 135: ajoute(3,mapile) 136: ajoute(7,mapile) 137: ajoute(9,mapile) 138: 139: affichepile(mapile) 140: affichepile(inversepile(mapile)) 141: 142: verifparenthese("coucou") 143: verifparenthese("([{{{}}}]{)(()})") 144: verifparenthese("([{{{}}}]{()()})") 145: verifparenthese("(([{{{}}}]{()()})") 146: verifparenthese("([{{{}}}]{()()}))") 147: 148: evaluepostfix("12+4*3+") 149: 150: