#------------------------------------------------------------------------------
# ------------------------ TD sur les piles ------------------------------------------
#------------------------------------------------------------------------------

## Première version : avec une structure de tableau

n = 10               # Nombre maximum d'éléments dans la pile 
P = (n+1)*[0]        # Liste de n + 1 éléments. Indice 0 réservé
P[0] = 1             # Au début, le premier élément à insérer est d'indice 1
  
def EMPILER1(P, x) :
    if P[0] == n + 1 :     # Pile déjà pleine. On ne peut plus empiler.
        raise(IndexError)
    else :
        i = P[0]
        P[i] = x
        P[0] = i + 1

    
def DEPILER1(P) :
    if P[0] == 1 :        # Pile déjà vide. On ne peut plus dépiler. 
        raise(IndexError)
    else :
        P[0] = P[0] - 1
        i = P[0]
        return P[i]

def PILE_VIDE1(P) :
    if P[0] == 1 :
        return True
    else :
        return False

#----------------------------------------------------------------------------
#----- Définition d'une pile à l'aide des méthodes de la classe list --------
#----------------------------------------------------------------------------

## Deuxième version : ici la Pile est une structure de type Liste.

P = []      # Pile vide  = liste vide

def EMPILER(P, x) :
    P.append(x)     # Attention : la fonction EMPILER ne retourne rien
    
def DEPILER(P) :    # DEPILER retire le dernier élément de P et retourne cet élément. 
    x = P.pop()
    return x

def PILE_VIDE(P) :
    if [P] == [] :   # On pourrait aussi écrire : if len(P) == 0 :
        return True
    else :
        return False

#-----------------------------------------------------------------------------
#---------------------- Détecteur de parenthèses ----------------------------
#-----------------------------------------------------------------------------

def analyse_parenthese(ch) :
    Pile = []
    for car in ch :    # car va prendre successivement toutes les valeurs des caractères de ch
        if car == "(" :
            EMPILER(Pile, car)
        elif car == ")" :
            if PILE_VIDE(Pile) :
                print("Il manque une ou des parenthèse(s) ouvrante(s)")
                return False  # Pour sortir de la fonction. La valeur retournée n'a pas d'importance
            else :
                DEPILER(Pile)
    
    # Tous les caractères de ch ont maintenant été examinés
    
    if PILE_VIDE(P) :
        print("Placement des parenthèses correct")
        return True
    else :
        print("Il manque une ou des parenthèses fermantes")
        return False


# Une méthode alternative consiste à utiliser 2 piles.
# Une pile POuv pour empiler les parenthèses ouvrantes
# Une pile PFerm pour empiler les parenthèses fermantes


def analyse_parenthese2(ch) :
    POuv, PFerm = [], []      # Double affectation
    for car in ch :
        if car == "(" :
            EMPILER(POuv, car)
        elif car == ")" :
            EMPILER(PFerm, car)
    
    if len(POuv) == Len(PFerm) :
        print("Autant de parenthèses ouvrantes que fermantes")
    elif len(POuv) > Len(PFerm) :
        print("Plus de parenthèses ouvrantes que fermantes")
    else :
        print("Moins de parenthèses ouvrantes que fermantes")
        
 
#-------------------------------------------------------------------------------
#-------------- Analyse d'une chaine postfixée ---------------------------------
#-------------------------------------------------------------------------------

def calc_exp_arith(ch) :
    P = []
    for c in ch :
        
        if c in ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9' ] :
            EMPILER(P, int(c) )
        
        elif c == '+' :
            y = DEPILER(P)
            x = DEPILER(P)
            z = x + y
            EMPILER(P, z)
        
        elif c == '-' :
            y = DEPILER(P)
            x = DEPILER(P)
            z = x - y       # Attention à l'ordre des opérandes
            EMPILER(P, z)
            
        elif c == '*' :
            y = DEPILER(P)
            x = DEPILER(P)
            z = x * y
            EMPILER(P, z)
        
        elif c == '/' :
            y = DEPILER(P)
            x = DEPILER(P)
            z = x / y
            EMPILER(P, z)
    
    return P[0]

ch = "123+*4-"
resultat = calc_exp_arith(ch)
print(resultat)

## Bonus
#-------------------------------------------------------------------------------
#--------------- Exercices supplémentaires -------------------------------------
#-------------------------------------------------------------------------------

import random as r 

def melange(P1, P2) :
    P3 = []
    while ( len(P1) > 0 and len(P2) > 0 ) : # Tant qu'aucune pile n'est vide 
            
        i = r.randint(1, 2)    # On tire un entier au hasard : 1 ou 2
        if i == 1 :
            EMPILER(P3, DEPILER(P1))
        else :
            EMPILER(P3, DEPILER(P2))
        
    # A partir de maintenant, l'une des deux piles est vide (ou les deux)
                    
    while len(P1) > 0 :
        EMPILER(P3, DEPILER(P1))
    while len(P2) > 0 :
        EMPILER(P3, DEPILER(P2))
        
    return P3     # Sortie de fonction


def couper(P) :
    tailleP = len(P)
    k = r.randint(1, tailleP)      # Nombre tiré au hasard entre 1 et la taille de la pile
    autre_P = []                    # Initialisation
                    
    while ( tailleP > 0 and k > 0 ) :    # Tant que P non vide et que k > 0
        EMPILER(autre_P, DEPILER(P))
        k = k-1
    return autre_P


L = [9, 10, "valet", "dame", "roi", "as"]
K = 10           # On se donne une valeur de K
P = []

for i in range(K) :
    P = P + L
P1 = couper(P)
P2 = melange(P1, P)
print(P2)

##-----------------------------------------------------------------------

#-------------------------------------------------------------------------------
#---------------- La structure File --------------------------------------------
# #-----------------------------------------------------------------------------

F = [0, 0, [0 for i in range(10)]]  # Une file d'au plus 10 éléments

def ENFILER(F, x) :
    queue = F[0]    # On récupère la valeur de queue pour F
    tete = F[1]     # On récupère la valeur de tete pour F
    n = len(F[2])   # Taille de la file
    
    if ( queue == (tete - 1) ) : # La file est pleine
        print("La file est pleine")
        raise(IndexError)
    elif ( (queue == n-1) and (tete == 0) ) : # La file est pleine aussi
        print("La file est pleine")
        raise(IndexError)
    else :                  # Il reste de la place  
        F[2][queue] = x
        queue = (queue+1) % n    # On augmente queue d'une unité, modulo n
        F[0] = queue             # On sauvegarde la nouvelle valeur de qeue dans F[0]

def DEFILER(F) :
    queue = F[0]     # On récupère la valeur de queue pour F
    tete = F[1]      # On récupère la valeur de tete pour F
    n = len(F[2])    # Taille de la file
    
    if (queue == tete) :  # La file est vide
        print("La file est vide")
        raise(IndexError)
    else :                 # Il reste des éléments dans la File
        x = F[2][tete]
        tete = (tete+1) % n   # On augmente tete d'une unité, modulo n
        F[1] = tete           # On sauvegarde la nouvelle valeur de tete dans F[1]
        return x              # On retourne l'élément "défilé".