Algorithmique Évaluation d’expressions Luc Brun luc.brun@greyc.ensicaen.fr ´ Ev

Algorithmique Évaluation d’expressions Luc Brun luc.brun@greyc.ensicaen.fr ´ Evaluation d’expressions – p.1/38 Plan Les différents types d’expressions Expression complètement parenthésée (ECP), Expression préfixée (EPRE), Expression postfixée (EPOST), Expression infixée (EINF). Évaluation d’expressions postfixée, complètement parenthésée, Conversion d’expressions ECP à postfixée, infixée à postfixée. ´ Evaluation d’expressions – p.2/38 Définition d’une expression Définition : Une expression est une suite de variables combinées par un ensemble d’opérateurs avec éventuellement un jeux de parenthèses ouvrantes et fermantes. Exemple :            NB : On ne fait pas intervenir de constantes ou de fonctions (petite simplification). L’évaluation d’une expression implique la définition d’un environnement (affectation de chaque variable à une valeur). ´ Evaluation d’expressions – p.3/38 Les opérateurs Opérateurs binaires opérateurs arithmétiques    opérateurs logiques           Opérateurs unaires opérateurs arithmétiques   NB :   , . opérateurs logiques   ´ Evaluation d’expressions – p.4/38 Expression complètement parenthésée Une expression complètement parenthésée se construit à partir des règles suivantes : 1. Une variable est une ECP, 2. si ! et " sont des ECP et # un opérateur binaire, alors ( ! # "  est une ECP, 3. si ! est une ECP et $ un opérateur unaire alors  $ !  est une ECP, 4. Il n’y a pas d’autre ECP que celles formées par les 3 règles précédentes. ´ Evaluation d’expressions – p.5/38 Grammaire des ECP Grammaire BNF (Backus-Naur Form)  ecp  % (  ecp   optbin   ecp  ) | (  optun   ecp  ) |  variable   optbin  %  & &  &  &  &  &  &  &  &  &   &   optun  %  & &   variable  %  &  &  & & ' ´ Evaluation d’expressions – p.6/38 Exemples d’ECP ECP conformes : ((A+B)*C) (((A/B)=C)et(E<F)) ( A) ECP non conformes : (A) ((A+B)) A  B ´ Evaluation d’expressions – p.7/38 Expressions préfixées Les expressions préfixées (EPRE) se construisent à partir des ( règles suivantes : 1. une variable est une EPRE, 2. si ! et " sont des EPRE et # un opérateur binaire alors # ! " est une EPRE, 3. Si ! est une EPRE et $ un opérateur unaire, alors $ ! est une EPRE, 4. il n’y a pas d’autres EPRE que celles formées à partir des ) règles précédentes. ´ Evaluation d’expressions – p.8/38 Grammaire des EPRE Règles :  epre  %  optbin   epre   epre  |  optun   epre  |  variable   optbin  %  & &  &  &  &  &  &  &  &  &   &   optun  %  & &   variable  %  &  &  & & ' NB : Seule la première règle a été changée. ´ Evaluation d’expressions – p.9/38 Exemples d’EPRE Expressions correctes : EPRE ECP + - A B C ((A-B)+C) et non  A B C ((non(A  B))et C) non = + A B C (non ((A+B)=C)) Expressions incorrectes A - + B C non B C ´ Evaluation d’expressions – p.10/38 Expressions postfixées Expressions utilisées par les calculatrices HP (cf TP Web) et données par les ( règles : 1. une variable est une EPOST, 2. si ! et " sont des EPOST et # un opérateur binaire alors ! " # est une EPOST, 3. Si ! est une EPOST et $ un opérateur unaire, alors ! $ est une EPOST, 4. il n’y a pas d’autres EPOST que celles formées à partir des ) règles précédentes. ´ Evaluation d’expressions – p.11/38 Grammaire des EPOST Règles :  epost  %  epost   epost   optbin  |  epost   optun  |  variable   optbin  %  & &  &  &  &  &  &  &  &  &   &   optun  %  & &   variable  %  &  &  & & ' NB : Seule la première règle a été changée. ´ Evaluation d’expressions – p.12/38 Exemples d’EPOST ECP EPRE EPOST (((A+B)-C)/D) / - + A B C D A B + C - D / ((A < B) et (non C)) et < A B non C A B < C non et ((non (A < B)) et (C>D)) et non < A B > C D A B < non C D > et ´ Evaluation d’expressions – p.13/38 Expressions Infixées Écriture ECP sans ambiguï té mais parfois un peu lourde. Suppressions de certaines parenthèses par * données implicites : 1. Priorité des opérateurs      +          2. Priorité à gauche pour les opérateurs de même priorité     +         Les parenthèses imposent des priorités    +              +        ´ Evaluation d’expressions – p.14/38 Priorité des opérateurs Opérateur Priorité ( 0        1 ou, +, - 2 et, *, / 3 ,  , non 4 ´ Evaluation d’expressions – p.15/38 Grammaire des EINF  !-.  : expression éventuellement présente un nombre quelconque de fois.  einf  %  esimple   op1   esimple    esimple  %  terme   op2   terme    terme  %  facteur   op3   facteur    facteur  %  variable  |  op4   facteur  | (  einf  )  op1  %  &  &  &  &  &   op2  %  & &    op3  %  &  &    op4  % &  &   variable  %  &  &  & & ' ´ Evaluation d’expressions – p.16/38 Exemples d’EINF EINF ECP A*B+C-D (((A * B) +C)-D) A+B*C (A+(B * C)) A=B et C>D ((A=(B et C))> D) A et B ou C et D ((A et B) ou (C et D)) A et (B ou C) et D ((A et (B ou C)) et D) non A et B ou C et non D (((non A) et B) ou (C et (non D))) ´ Evaluation d’expressions – p.17/38 Évaluation d’expression L’évaluation s’effectue par rapport à un environnement (affectation des variables). Idée : Ordonnancer l’évaluation de façon à ce que l’évaluation d’une opération s’effectue sur des variables ou des expressions déjà évaluées. Soit / appliquant # sur ! et " . evaluation(S) = opération( # , si variable(x) alors valeur(x) sinon evaluation(x), si variable(y) alors valeur(y) sinon evaluation(y)) ´ Evaluation d’expressions – p.18/38 Exemple d’évaluation Soit à évaluer S=(A+(B*C)) avec   *   )   ( . evaluation(S) = opération(+,A,évaluation(B*C)) = opération(+,A,opération(*,B,C)) = opération(+,2,opération(*,3,4)) = opération(+,2,12) = 14 ´ Evaluation d’expressions – p.19/38 Évaluation d’une expression postfixée Les opérandes apparaissent avant l’opération. L’évaluation d’une opération fournie soit le résultat soit un nouvel opérande. 10 3 + 5 6 - - = 13 5 6 - - = 13 -1 - = 14 Idée : empiler les opérandes, dépiler pour effectuer une opération. ´ Evaluation d’expressions – p.20/38 Exemple d’évaluation d’une EPOST évaluons A B * C D + / avec A=2,B=3,C=2,D=1 2 3 2 6 pile vide empiler A empiler B evaluer * AB*CD+/#  0 B*CD+/# A  0 *CD+/# AB  0 CD+/# 2 6 1 2 6 3 6 2 empiler C empiler D évaluer + evaluer / AB*  0 D+/# AB*C 0 +/# AB*CD  0 /# AB*CD+  0 # ´ Evaluation d’expressions – p.21/38 Évaluation d’EPOST : Énumération des cas Soit epost[1..MAX] une chaî ne de caractères contenant une EPOST et 1 une position dans la chaî ne. Si epost[i]=’#’ : l’évaluation est terminé. Résultat en sommet de pile. Si epost[i]  ’#’ Si epost[i] est une variable : empiler sa valeur Si epost[i] est un opérateur : on dépile son (ou ses 2 opérandes), on effectue l’opération et on empile le résultat. ´ Evaluation d’expressions – p.22/38 Évaluation d’EPOST : l’algorithme fonction evalPost (epost : Tableau[ 2  ] deCaratère ) : Réel Déclaration i :Entier,valG,valD :Réel,p : Pile début p 3 creer() i 3 1 tant que epost[i]  ’#’ faire si variable(epost[i]) alors empiler(epost[i],p) sinon si unaire(epost[i]) alors valD 3 dépiler(p) valD 3 oper1(epost[i],valD) empiler(valD,p) sinon valD 3 dépiler(p) valG 3 dépiler(p) uploads/s3/ algorithmique-expressions.pdf

Tags
Administrationd’expressions evaluation alors epost variable
Documents similaires
  • 39
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager