#####################################################
# CORRECTION TP1 (MATHEMATIQUES POUR L'INFORMATIQUE)
# SUJET: CALCUL BOOLÉEN.
#
# NB. Les listes et dictionnaires sont mutables mais
# pas les chaînes ni les tuples. D'autre part les
# listes étant des références, les modifications des
# valeurs d'une liste dans une fonction sont en fait
# réalisées sur la liste d'appel.
#
###################################################n##


######################################################
# DEBUT DES FONCTIONS POUR LE TRI
# Dans cette correction, le tri est effectué par
# l'algorithme du tri à bulles et non par la
# méthode Python .sort().
######################################################

#-----------------------------------------------------
# ECHANGE LES VALEURS AUX INDICES I ET J dans une
# structure énumérée mutable. Pour éviter l'emploi 
# de x,y = y,x spécifique au Python et qui
# donne de mauvaises habitudes de programmation.
# Noter qu'il n'y a pas de valeur de retour car les
# listes sont des références.
# Les indices i et j sont supposés appartenir à
# l'intervalle (mathématique) [0,#L[
#-----------------------------------------------------
def Echanger(L,i,j):
    aux = L[i]
    L[i] = L[j]
    L[j] = aux

#-----------------------------------------------------
# FAIT REMONTER LA PLUS GRANDE VALEUR de l'intervalle
# [i,j] de la liste L en position j en comparant les
# termes d'indices k et k + 1 pour k allant de i à
# j - 1.
# Les indices i et j sont supposés appartenir à
# l'intervalle (mathématique) [0,#L[
#-----------------------------------------------------
def Propager(L,i,j):
    k = i
    while k < j:
        if L[k] > L[k + 1]:
            Echanger(L,k,k+1)
        k = k + 1
    return L

#-----------------------------------------------------
# ALGORITHME DU TRI À BULLES.
# On répète la propagation 
#-----------------------------------------------------
def TriBulles(L):
    d = len(L) - 1
    while (d > 0):
        Propager(L,0,d)
        d = d - 1
    return L
######################################################
# FIN DES FONCTIONS POUR LE TRI
######################################################



#-----------------------------------------------------
# EXTRACTION DES VARIABLES BOOLÉENNES (VERSION 1)
# (Sans préoccupation d'efficacité..)
# Ici le tri de la liste n'est pas fait directement
# dans la fonction mais dans le code principal après
# l'appel pour faire apparaître l'appel du
# tri à bulle.
#-----------------------------------------------------
#def ListerVariables(expression):
#    variables = []
#    lexique = "abcdefghijklmnopqrstuvwxyz"
#    for symbole in expression:
#        if (symbole in lexique) and not (symbole in variables):
#            variables.append(symbole)
#    return variables


#-----------------------------------------------------
# EXTRACTION DES VARIABLES BOOLÉENNES. (VERSION 2)
# On utilise une structure d'ensemble, ainsi
# la méthode .add ne rajoute pas un élément
# déja présent dans un ensemble, conformément
# à son homologue mathématique.
#-----------------------------------------------------
#def ListerVariables(expression):
#    variables = set()
#    for symbole in expression.lower():
#        if symbole.isalpha():
#            variables.add(symbole)
#    return list(variables)


#-----------------------------------------------------
# EXTRACTION DES VARIABLES BOOLÉENNES. (VERSION 3)
# Evite de trier en testant tous les caractères
# possibles autorisés dans l'expression dans
# l'ordre alphabétique.
# On aurait pu utiliser chr(i) pour balayer les
# lettres minuscules plutôt que la chaîne "ab...z"
# Même remarque que la V1 pour le tri.
#-----------------------------------------------------
def ListerVariables(expression):
    variables = []
    for car in "abcdefghijklmnopqrstuvwxyz":
        if car in expression:
            variables.append(car)
    return variables

#-----------------------------------------------------
# CONSTRUCTION DU DICTIONNAIRE. À partir de la liste
# des variables. On associe à une variable sa position
# dans la liste, sachant qu'elles ont été triées dans
# l'ordre alphabétique au préalable.
#-----------------------------------------------------
def DicoVariables(liste):
    dico = {}
    i = 0
    while i < len(liste):
        dico[liste[i]] = i
        i = i + 1
    return dico

#-----------------------------------------------------
# CONVERTIT UN ENTIER EN BINAIRE SUR N BITS.
# Complète par des 0 à gauche si sa représentation
# comporte moins de n bits.
# La chaîne renvoyée servira d'interprétation des
# variables booléennes de la fonction.
#----------------------------------------------------
def Int2Bin(entier,n):
    bits = bin(entier)[2:]
    if len(bits) < n:
        bits = "0" * (n - len(bits)) + bits
    return bits
        
#-----------------------------------------------------
# CONVERTIT UNE CHAÎNE BINAIRE EN TUPLE DE BOOLEENS
# NB. Remarquer l'absence de condition if. 
#-----------------------------------------------------
def Bin2Bool(bits):
    booleens  = ()
    for b in bits:
        booleens = booleens + (b == "1",)
    return booleens

#-----------------------------------------------------
# CONVERTIT UNE FORMULE EN LANGAGE PYTHON.
# On balaie les symbole de l'expression en
# testant si le symbole courant est une
# variable, un opérateur ou autre.
#-----------------------------------------------------
def Math2Python(expression, vecteur, dicovar):
    pexp = ""
    operateurs = {"!":" not ","*":" and ","+":" or "}
    for symb in expression:
        if symb in dicovar.keys():
            pexp = pexp + str(vecteur[dicovar[symb]])
        elif symb in operateurs.keys():
            pexp = pexp + operateurs[symb]
        else:
            pexp = pexp + symb
    return pexp

#-------------------------------------------------------
# CALCULE LA TABLE DE VÉRITÉ D'UNE FONCTION.
# L'expression de la fonction est passee en
# parametre sous forme de liste contenant les 2^n valeurs
# possibles de l'expression de n variables logiques. 
#-------------------------------------------------------
def TableVerite(expression,dicovar):
    nbvar = len(dicovar.keys())
    TDV = [0] * (2**nbvar)
    for entier in range(2**nbvar):
        vecteur = Bin2Bool(Int2Bin(entier,nbvar))
        chaine = Math2Python(expression,vecteur,dicovar)
        if eval(chaine):
            TDV[entier] = 1
    return TDV

#--------------------------------------------------------
# FORMATE LA SORTIE DE L'ÉVALUATION DE L'EXPRESSION
# pour un tuple logique de nbvar variables codé sous
# forme d'entier. Utilisée pour afficher la TDV.
#--------------------------------------------------------
def AfficherLigne(entier, nbvar, TDV):
    for bit in Int2Bin(entier,nbvar):
        print(bit.rjust(2), end='')       
    print(' |' + str(TDV[entier]).rjust(2))

#-------------------------------------------------------
# AFFICHE UNE TABLE DE VÉRITÉ.
#-------------------------------------------------------
def AfficherTDV(TDV, dicovar):
    nbvar = len(dicovar.keys())
    for v in sorted(dicovar.keys()):
        print(v.rjust(2),end='')
    print(" | E".rjust(2))
    print((nbvar * "--") + "-|--")
    for entier in range(2**nbvar):
        AfficherLigne(entier,nbvar,TDV)

#-------------------------------------------------------
# AFFICHE LA FND D'UNE FONCTION à partir de sa table de
# vérité.
#-------------------------------------------------------     
def FND(TDV, listevar):
    n = len(listevar)
    debut = True
    print("FND = ", end='')
    entier = 0
    while entier < len(TDV):
        if (TDV[entier] == 1):
            bits = Int2Bin(entier,n)
            if debut:
                debut = False
            else:
                print(" + ",end='')
            i = 0
            while i < n:
                if bits[i] == "1":
                    print(listevar[i],end='')
                else:
                    print(listevar[i] + "\u0304",end='')
                i = i + 1
        entier = entier + 1
    print()

#-------------------------------------------------------
# AFFICHE LA FNC D'UNE FONCTION à partir de sa table de
# vérité. 
#-------------------------------------------------------     
def FNC(TDV, listevar):
    n = len(listevar)
    print("FNC = ", end='')
    entier = 0
    while entier < len(TDV):
        if (TDV[entier] == 0):
            bits = Int2Bin(entier,n)
            debut = True
            i = 0
            while i < n:
                if debut:
                    print('(', end='')
                    debut = False
                else:
                    print("+", end='')
                if bits[i] == "0":
                    print(listevar[i],end='')
                else:
                    print(listevar[i] + "\u0304",end='')
                i = i + 1
            print(')',end='')
        entier = entier + 1
    print()
        
##########################################################
# PROGRAMME PRINCIPAL
##########################################################
expression = input("Expression = ")
listevar = ListerVariables(expression)
print(listevar)
listevar = TriBulles(listevar)
print(listevar)
dicovar = DicoVariables(listevar)
print(dicovar)
TDV = TableVerite(expression,dicovar)
AfficherTDV(TDV,dicovar)
FND(TDV,listevar)
FNC(TDV,listevar)