#### Question 1) ####


L_Symboles=[["(",")"],["[","]"],["{","}"]]
L_Symboles_Ouvrant=[S[0] for S in L_Symboles]
L_Symboles_Fermant=[S[1] for S in L_Symboles]

def Test_Fermant(symbole) :
    """ teste si symbole est un symbole fermant et si oui, renvoie le symbole ouvrant associé """
    k=0
    while k<len(L_Symboles) :
        if L_Symboles_Fermant[k]==symbole :
            return L_Symboles_Ouvrant[k]
            break
        else :
            k+=1
    return False

# print(Test_Fermant("]"))
        
def Test(chaine) :
    """ teste si chaine est bien parenthésée et si non, revoie l'endroit de l'erreur"""
    
    L_Pile=[] # on prépare une pile de symboles ouvrant ou fermant
    
    for k in range(len(chaine)):
        symbole=chaine[k]
        Test_Parenthese=True
        if symbole in L_Symboles_Ouvrant :
            L_Pile.append(symbole) 
            # on empile le délimiteur ouvrant dans la pile
        Symb_Temp=Test_Fermant(symbole)
        if Symb_Temp : # si symbole est un délimiteur fermant
            if L_Pile!=[] and L_Pile[-1]==Symb_Temp :
                # si on a affaire à un bon parenthésage, pour l'instant...
                L_Pile.pop()
                # on dépile le symbole ouvrant
            else :
                # on a une erreur de parenthésage
                print("Il y a une erreur de délimiteur à cet endroit dans la chaine :\n"+chaine[:k]+"***")
                Test_Parenthese=False
                break    
            ### remarque : la pile peut devenir vide à un moment donné puis repartir...
        
    if L_Pile==[] and Test_Parenthese :
        print("La chaîne de caractères est bien parenthésée.")
    elif L_Pile==[] and not(Test_Parenthese) :
        print("Il y a un délimiteur fermant en trop  !!!!")
    else :
        p=0
        while L_Symboles_Ouvrant[p]!=L_Pile[-1] :
            p+=1
        print("Il manque le délimiteur fermant : "+L_Symboles_Fermant[p])
        
chaine="Une phrase [(normale)]{jjj}{({((@[oo])])})};"
#chaine="[yy{}][{}][]"
Test(chaine)

#### Question 2) ####

"""
On effectue une récurrence. 

Lorsque n=0, il y a une seule façon de parenthéser : " " (avec aucune parenthèse).

Supposons la formule vraie jusqu'au rang n.

Au rang (n+1), étant donné un bon parenthésage avec (n+1) parenthèses ouvrantes et (n+1) parenthèses fermantes, on note 2k, le nombre de parenthèses (k ouvrantes et k fermantes) entre la première parenthèse et sa parenthèse fermante.

Par récurrence forte, il y a C_k façons de parenthèser à l'aide de 2k délimiteurs, et il y a C_(n-k) façons de parenthèser à l'aide des autres délimiteurs. Ces choix sont indépendants car conduisent à des bons parenthésages (car à l'intérieur ou à l'extérieur de deux parenthèses). Il suffit d'effectuer la somme, lorsque k varie de 0 à n. """

### Question 3) ###

def Catalan(n) :
    if n==0 :
        return 1
    else :
        return sum([Catalan(k)*Catalan(n-1-k) for k in range(n)])

# for k in range(1,10) :
#     print("Nombre de Catalan indice ",k," égal à :",Catalan(k))

### Question 4) ###

def Catalan_Bis(n) :
    if n==0 :
        return 1
    else :
        return int(2*(2*n-1)/(n+1)*Catalan_Bis(n-1))
    
# for k in range(1,10) :
#     print("Nombre de Catalan indice ",k," égal à :",Catalan_Bis(k))

#### Question 5) ####

from pylab import *

import time

def Traces_Perf(n) :
    LX=list(range(n+1))
    LT_1,LT_2=[],[]
    for k in LX :
        t_0=time.clock()
        Catalan(k)
        t_1=time.clock()
        LT_1.append(log(t_1-t_0))
    for k in LX :
        t_0=time.clock()
        Catalan_Bis(k)
        t_1=time.clock()
        LT_2.append(log(t_1-t_0))
    figure()
    plot(LX,LT_1,color="blue",marker="o")
    plot(LX,LT_2,color="red",marker="o")
    legend(('Catalan','Catalan_Bis'),'upper center', shadow=True)
    ylabel("Temps d'exécution")
    xlabel('Entiers')
    show()

# Traces_Perf(12)



### Conclusion : Catalan_Bis bien meilleur que Catalan... conforme à la théorie.