#!/usr/bin/python3 -B




## Question 1.1

from abe import *


## Question 1.2

A1=arbre('+', arbre('*',1,2), arbre('/', arbre('+',3,4), 5))

# autre arbres pour faire plus de tests
A1 = arbre('+', arbre('*', 1, 2), arbre('/', arbre('+', 3, 4), 5))
A2 = arbre('-',  arbre('*',  2, 42), arbre('+', 11, 'y'))
A3 = arbre('+',A1,A2)
A4 = arbre('-',  5, arbre('/', 11, 'x'))
A5 = arbre('+', A3, A4)







## Question 2.1


def contient42(A):
    if est_feuille(A):
        return A == 42
    else:
        résultat_gauche = contient42(fg(A))
        résultat_droit = contient42(fd(A))
        return résultat_gauche or résultat_droit


def contient42(A):
    if est_feuille(A):
        return A == 42
    else:
        return contient42(fg(A)) or contient42(fd(A))

## Question 2.2

def compte_pairs(A):
    if est_feuille(A):
        if A%2 == 0:
            return 1
        else:
            return 0
    else:
        return compte_pairs(fg(A)) + compte_pairs(fd(A))

## Question 2.3

def feuilles_paires(A):
    if est_feuille(A):
        if A%2 == 0:
            return [A]
        else:
            return []
    else:
        g = feuilles_paires(fg(A))
        d = feuilles_paires(fd(A))
        return g + d


## Question 2.4

def liste_profondeur(A, n):
    if est_feuille(A):
        return []
    else:
        if n == 0:
            return [racine(A)]
        else:
            g = liste_profondeur(fg(A), n-1)
            d = liste_profondeur(fd(A), n-1)
            return g + d

## Question 2.5

def profondeur_max_pair(A):
    if est_feuille(A):
        if A%2==0:
            return 0
        else:
            return None
    else:
        rg = profondeur_max_pair(fg(A))
        rd = profondeur_max_pair(fd(A))
        if rg==None and rd==None:
            return None
        elif rg==None: # rd est bien définie
            return rd+1
        elif rd==None: # rg est bien définie
            return rg+1
        else: # rg et rd sont bien définie
            return max(rg,rd)+1 # on ajoute 1 à la profondeur maximale trouvée







## Question 3.1
def compter(A, op):
    if est_feuille(A):
        return 0
    else:
        rg = compter(fg(A),op)
        rd = compter(fd(A),op)
        if racine(A) == op:
            return 1 + rg + rd
        else:
            return  rg + rd


## Question 3.2

def remplacer(A, op1, op2):
    if est_feuille(A):
        return A
    else:
        Ag = remplacer(fg(A),op1,op2)
        Ad = remplacer(fd(A),op1,op2)
        if racine(A)==op1:
            op=op2
        else:
            op=racine(A)
        return arbre(op,Ag,Ad)






def miroir(A):
    if est_feuille(A):
        return A
    else:
        return arbre(racine(A), miroir(fd(A)), miroir(fg(A)))






# Fonction du cours
def pp_suffixe(A):
    if est_feuille(A):
        return [A]
    return  pp_prefixe(fg(A)) + pp_prefixe(fd(A)) + [racine(A)]

# Pour faire des tests
L1 = [1,5,'+',3,'*',2,1,'-','+']
L2 = [1, 2, '-', 3, 4, '/', '*']

s1="1 5 + 3 * 2 1 - +"
s2="1 2 - 3 4 / *"

## Question 5.1

import pile

def arboriser(L):
    P = pile.nouvelle_pile()
    for e in L :
        if e in "+-*/":
            a = pile.dépile(P)
            b = pile.dépile(P)
            pile.empile(P,arbre(e,b,a))
        else:
            pile.empile(P,e)
    return pile.dépile(P) # Si le calcul a une bonne syntaxe, il ne
                          # doit rester qu'un élément dans la pile

## Question 5.2

def valeur(A):
    if est_feuille(A):
        return A
    else:
        r = racine(A)
        vg = valeur(fg(A))
        vd = valeur(fd(A))
        if r == '+' : return vg + vd
        if r == '-' : return vg - vd
        if r == '*' : return vg * vd
        if r == '/' : return vg / vd


def calcul(L):
    return valeur(arboriser(L))





## Question 5.3


def calcul_simple(e,a,b):
    if e == '+' : return a+b
    if e == '-' : return a-b
    if e == '*' : return a*b
    if e == '/' : return a/b


def calcul_direct(L):
    P = pile.nouvelle_pile()
    for e in L :
        if est_opérateur(e):
            a = pile.dépile(P)
            b = pile.dépile(P)
            pile.empile(P,calcul_simple(e,b,a)) # il suffit de changer cette ligne !
        else:
            pile.empile(P,e)
    return pile.dépile(P) # Si le calcul a une bonne syntaxe, il ne
                          # doit rester qu'un élément dans la pile


## Question 5.4

def calcul_chaine(s):
    Ls = s.split()
    L = []
    for e in Ls:
        if e.isdigit():
            L.append(int(e))
        else:
            L.append(e)
    return calcul_direct(L)