DEUG MIAS 2 - année 2000-2001
Institut Galilée
Informatique

TD 4-suite
Récursivité et manipulation d’expressions

On considère une fonction f() de 2 arguments. On appelle expression une séquence de ‘0’, ‘f’,‘(‘, ‘,’ et  ‘)’. On dira qu’une expression est bien formée si elle s’écrit ‘0’, ou bien f(expression, expression). Dans la suite, on dira “ expression ” pour “ expression bien formée ”.

1. 	Ecrire quelques expressions.

2. 	Ecrire une fonction récursive qui vérifie si une expression est bien formée. L’expression sera stockée dans une chaîne de caractères.

3. 	On veut stocker une expression dans une structure de données plus maniable qu’une chaîne de caractères. Pour cela, on va utiliser un tableau dont chaque case sera :

       - Soit 0
       - Soit f, suivi des indices des 2 cases où commencera la description des 2 arguments.

On convient que la description commence à la case 1.

a)	Ecrire le type Texpression

b)	Exhiber le tableau qui stocke f(f(0,f(0,0)),0)

c)	Ecrire une procédure récursive qui affiche une expression

d)	On veut écrire une fonction qui renvoie l’expression qui correspond à une chaîne. Pour çà :

i)	Ecrire une fonction zero : Texpression qui renvoie l’expression ‘0’.
ii)	Ecrire une fonction f(e1,e2 : Texpression) : Texpression qui renvoie f(e1,e2).
iii)	En déduire une fonction récursive qui renvoie l’expression qui correspond à une chaîne. On supposera l’expression bien formée.

e)	En convenant que ‘0’ = 0 et que f(n,m) = (n+1)*(m+1), écrire une fonction récursive qui évalue une expression.

f)	Ecrire une fonction récursive qui met une expression sous forme post-fixe. Là encore, on supposera l’expression bien formée.
Exemple. la forme post-fixe de f(f(0,f(0,0)),0) est : 0 0 0 f f 0 f