Expression mathematique sous forme d'arbre binaire
Milhouse57
Messages postés6Date d'inscriptionlundi 26 janvier 2004StatutMembreDernière intervention27 janvier 2004
-
26 janv. 2004 à 23:22
LiftinG
Messages postés3Date d'inscriptionjeudi 20 février 2003StatutMembreDernière intervention31 juillet 2005
-
29 avril 2004 à 19:47
Je recherche un code qui transformerait une expression mathematique (donnée par l'utilisateur sous forme de chaine de charactere) en un arbre binaire (qui respecterait les priorités des opérateurs) et qui par la meme occasion le calculerait, en C++.
J'ai deja implanté la classe arbre binaire et les methodes utiles, mais je coinse au niveau de la transformation de l'expression en arbre !!!
cs_alain34270
Messages postés85Date d'inscriptionmardi 11 février 2003StatutMembreDernière intervention18 septembre 2005 27 avril 2004 à 18:00
Pour une meilleure compréhension des noms des méthodes, variables, etc... : il s'agissait d'un interpréteur de texte d'un "langage" dédié à la programmation d'algorithmes de tri par comparaison/échange de valeurs.
Si tu as des pb, n'hésites pas à me contacter.
Tel quel, la mise en page n'est pas terrible, mais je pense qu'une fois copié sur un traitement de texte ou autre, ça doit déjà être plus clair.
Algorithme::Algorithme()
//Précond : aucune
//Action : crée un nouvel objet algorithme (support)
{
source = 0; //Code source
lEntiers = 0; //pointeur sur liste d'entiers
vu=0; //Pointeur de variables
for (UINT i=0;i<maxBloc;i++)
{ bl[i]=0; } //Init des pointeurs de blocs à zéro
noBloc=-1; //numéro du bloc en cours
piMots= 0; //pile des mots
piEntiers=0; //pile des entiers
}
Algorithme::~Algorithme()
//Précond : aucune
//Action : détruit l'algorithme
{
delete source;source=0;
delete vu;vu=0;
if (piMots !=0) delete piMots;piMots=0;
if (piEntiers !=0) delete piEntiers;piEntiers=0;
for (UINT i=0;i<maxBloc;i++)
if (bl[i]!=0) delete bl[i];
}
void Algorithme::referenceTav(TeteActionView *tav)
//Précond : tav doit pointer sur un objet TeteActionView
//Action : référence le TeteActionView pour indiquer à CView les actions
// à effectuer
{ this->tav = tav; }
String Algorithme::leSource()
//Précond : aucune
//Résultat: retourne le code source de l'algorithme
{
if (source==0)
return String("");
else
return *source;
}
UINT Algorithme::laLigneCourante()
//Précond : aucune
//Action : retourne le numéro de la ligne courante
{
UINT temp=0;
if (source !=0)
{
for (UINT i=0;iiCourant;i++)
{
if ((*source)[i]=='\n')
temp++;
}
}
return temp;
}
void Algorithme::interprete()
//Précond : aucune
//Action : si un algorithme et une liste d'entiers sont présents,
// interprétation de l'instruction sous iCourant.
// Sinon, ne fait rien
{
if (lEntiers!=0 && source!=0)
{
//sauvegarde du début de l'instruction
bl[noBloc]->iDebInst=bl[noBloc]->iCourant;
//Initialisation des piles (vidage)
piMots->vide();
piEntiers->vide();
//Lecture du premier mot
String s=leMotSuivant();
bool fini=false;
while (s=="" && !fini)//fin de bloc ?
{
if (noBloc==0)
{
//l'algorithme est terminé
creeAction("algorithmetermine");
fini=true;
}
else
{
noBloc--;
s=leMotSuivant();
}
}
while (s.leNbCaracteres()!=0 && !fini)
{
if (s==""")
{
//Traitement chaine de caractères
laChaine="";
s=leMotSuivant();
if (s!=""")
{
laChaine=s;
}
s=leMotSuivant();
}
if (s!="+" && s!="-" && s.isEntier() ||
(s.leNbCaracteres()==1 &&
((s[0]>='a' && s[0]<='z') || (s[0]>='A' && s[0]<='Z'))))
//Si s contient un entier (ou un nom de variable), on l'empile
piEntiers->empile(s);
else
{
UINT nop = leNoOperateur(s);
switch (nop)
{
case 11: // (
piMots->empile(s);
break;
case 9999: // nom d'instruction (normalement sinon erreur)
piMots->empile(s);
break;
case 12: // )
//evalue jusqu'à la précédente (
evalueTerme();
piMots->depile(); //on supprime la parenthèse
//Si le dernier mot empilé est une instruction, on l'évalue ici
if (piMots->hauteur!=0 && /*alors*/
leNoOperateur(piMots->sommet())==9999)
{
//Si l'instruction est si ou tantque, il faut arrêter l'interprétation
//après l'avoir exécutée
if (String::compareTo(piMots->sommet(),"tantQue",String::compareSansCasse)==0
|| String::compareTo(piMots->sommet(),"si",String::compareSansCasse)==0)
fini = true;
evalue();
}
break;
case 13: // {
//création nouveau bloc
nouveauBloc();
fini = true;
break;
case 14: // }
//fin de bloc, on ne doit pas en rencontrer à ce niveau
MessageBox(NULL,
"fin de bloc",
"Impossible d'interpréter",0);
throw ErreurDeSyntaxe();
break;
case 15: // ,
evalueTerme();
//On n'empile pas la virgule
break;
case 16: // ;
//fin d'instruction
finitEvaluation();
fini=true;
break;
default: //Pour les autres, dépend du contenu déjà présent
while (piMots->hauteur()!=0 &&/*alors*/
(priorite(leNoOperateur(piMots->sommet()),nop)))
{
evalue();
}
piMots->empile(s);
}//switch
}//if s entier else
if (!fini)
s=leMotSuivant();
}//while
}//if (lEntiers!=0 && source!=0)
else
{
if (lEntiers==0 && source==0)
MessageBox(NULL,
"Vous devez charger un algorithme, et entrer une liste de nombres entiers",
"Impossible d'interpréter",0);
else
if (lEntiers==0)
MessageBox(NULL,
"Vous devez entrer une liste de nombres entiers",
"Impossible d'interpréter",0);
else
MessageBox(NULL,
"Vous devez charger un algorithme",
"Impossible d'interpréter",0);
}
}//interprete()
void Algorithme::evalueTerme()
//Précond : la pile piMots doit avoir une structure évaluable, et doit comporter
// une parenthèse ouvrante comme marque de fin d'expression à évaluer
//Action : évalue l'expression contenue dans les piles piMots et piEntiers jusqu'à
// rencontrer une parenthèse ouvrante
{
while (piMots->hauteur!=0 &&/*alors*/ piMots->sommet()!="(")
{
evalue();
}
}
void Algorithme::finitEvaluation()
//Précond : la pile piMots doit avoir une structure évaluable
//Action : évalue tout le restant de la pile.
// Si erreur, génère une exception ErreurDeSyntaxe
{
while (piMots->hauteur()!=0)
{
//Si (, l'expression est incorrecte
if (piMots->sommet()=="(")
throw ErreurDeSyntaxe();
else
evalue();
}
}
void Algorithme::evalue()
//Précond : aucune
//Action : évalue le sommet de la pile piMots (utilise piEntiers pour parametres évent)
// si un résultat doit être rendu, il est empilé sur piEntiers
// (pour les bouléens 0=faux, 1=vrai)
{
if(piMots->hauteur()!=0)
{
String s=piMots->sommet();
String e = "";
int v1,v2;
UINT nop = leNoOperateur(s);
switch(nop)
{
case 0:
case 1:
case 2:
case 3:
//Opérations +-*/
piMots->depile();
v2 = recupValeurPiEntiers();
v1 = recupValeurPiEntiers();
switch (nop)
{
case 0:
v1 = v1+v2;
break;
case 1:
v1 = v1-v2;
break;
case 2:
v1 = v1*v2;
break;
case 3:
v1 = v1/v2;
break;
}//switch
e = String::intToString(v1,6,"0",'+');
piEntiers->empile(e);
break;
case 4: //affectation
piMots->depile();
affectation();
break;
case 5: //Opérateurs de comparaison
case 6:
case 7:
case 8:
case 9:
case 10:
piMots->depile();
comparaison(nop);
break;
case 9999:
instruction();
break;
}//switch
}//if(!piMots->vide)
}
void Algorithme::nouveauBloc()
//Précond : aucune
//Action : initialise un nouveau bloc
{
//Le début du bloc commence immédiatement après la {
UINT debut=bl[noBloc]->iCourant;
//Sauvegarde du dernier index pour avoir l'index de l'accolade fermante
UINT iPrec=bl[noBloc]->iCourant;
//Recherche de la fin
int nbAccolades=0;
String s=leMotSuivant();
bool trouve=(s=="}");
//Parcours partiel de l'algorithme jusqu'à trouver l'accolade fermante correspondant
//à celle qui a généré la demande de création du bloc
while (s!="" && nbAccolades>=0)
{
if (s=="{")
nbAccolades++;
else
if (s=="}")
nbAccolades--;
if (nbAccolades>=0)
{
iPrec=bl[noBloc]->iCourant;
s=leMotSuivant();
}
}
//fin du bloc avant l'accolade fermante
UINT fin=iPrec-1;
//Création du nouveau bloc
noBloc++; //incrémente le numéro du bloc
bl[noBloc] = new Bloc(debut,fin);
}
int Algorithme::valeurEntiere(String s)
//Précond : s doit contenir un entier ou un nom de variable entière
// dans le premier caractère
//Résultat: valeur de l'entier contenu dans s
{
int temp;
if (s.isEntier())
temp = s.toInt();
else
temp = vu->laValeur(s[0]);
return temp;
}
int Algorithme::recupValeurPiEntiers()
//Précond : la pile d'entiers ne doit pas être vide
//Résultat: dépile un élément de piEntiers et retourne sa valeur
// si la pile n'est pas vide.
// sinon, génère un objet ErreurSyntaxe
{
int temp;
if (piEntiers->hauteur()==0)
throw ErreurDeSyntaxe();
else
{
String s=piEntiers->sommet();
piEntiers->depile();
temp = valeurEntiere(s);
}
return temp;
}
String Algorithme::recupNomVarPiEntiers()
//Précond : le sommet de la pile d'entiers doit contenir le nom d'une variable entière
//Résultat: retourne le nom de la variable entière dans une String,
// ou génère une ErreurDeSyntaxe()
{
String temp="";
if (piEntiers->hauteur()!=0)
{
temp=piEntiers->sommet();
piEntiers->depile();
if (!estNomVariable(temp))
throw ErreurDeSyntaxe();
}
else
throw ErreurDeSyntaxe();
return temp;
}
bool Algorithme::estNomVariable(String s)
//Précond : aucune
//Résultat: retourne vrai si s représente le nom d'une variable, faux sinon
{
return (s.leNbCaracteres()==1 &&
((s[0]>='a' && s[0]<='z') || (s[0]>='A' && s[0]<='Z')));
}
void Algorithme::nouvelAlgorithme(String code)
//Précond : code doit contenir le code de l'algorithme
//Action : supprime éventuellement l'ancien algorithme,
// et met le contenu de code à sa place
{
if (source!=0)
{
//Suppression de l'ancien algorithme
delete source;
//Suppression des anciens blocs
for (int i=0;i<maxBloc;i++)
if (bl[i]!=0)
{
delete bl[i];
bl[i]=0;
}
}
//Sauvegarde du source
source = new String(code);
//référence dans bl[0]
bl[0] = new Bloc(0,source->leNbCaracteres()-1);
initInterpretation();
}
void Algorithme::initInterpretation()
//Précond : l'agorithme doit être déjà chargé
//Action : fait les initialisations pour débuter l'interprétation
// les variables sont mises à zéro
// les blocs imbriqués sont supprimés (il ne reste que le premier,
// référençant la totalité du code)
// l'index du code est mis au début du code
{
if (source!=0)
{
//Suppression des anciens blocs
for (int i=1;i<maxBloc;i++)
if (bl[i]!=0)
{
delete bl[i];
bl[i]=0;
}
//Suppression des anciennes variables
if (vu !=0) delete vu;
//Suppression des ActionView
tav->supprimeToutesActions();
//Suppression des anciennes piles
delete piMots;
delete piEntiers;
}
//bouléen pour savoir si on est dans une chaine
dansChaine=false;
//référence dans bl[0]
noBloc=0;
if (bl[noBloc]!=0) bl[noBloc]->iCourant=0;
//variables utilisateur
vu = new Variables();
//Piles
piMots = new PileString();
piEntiers = new PileString();
}
void Algorithme::nouvelleListe(ListeEntiers *l)
//Précond : l doit être un pointeur sur une liste d'entiers existante
//Action : initialise le pointeur lEntier avec l, pour référencer la liste d'entiers
{ lEntiers = l; }
void Algorithme::passeCommentaires()
//Précond : aucune
//Action : positionne l'index d'interprétation sur le premier caractère
// qui n'est pas un commentaire
{
if (!bl[noBloc]->dansChaine)
{
bool fini = false;
bool commentaire = false;
char c=(*source)[bl[noBloc]->iCourant];
//Parcours partiel jusqu'à ce qu'on soit en dehors d'un commentaire
while (!fini)
{
switch (c)
{
case '\n':
//Fin de commentaire ?
if (commentaire) fini=true;
break;
case '/':
//Début de commentaire ?
if (bl[noBloc]->iCourant+1<=bl[noBloc]->iFin
&& (*source)[bl[noBloc]->iCourant+1]=='/')
{
//début de commentaire
commentaire=true;
//On passe la seconde barre de fraction
bl[noBloc]->iCourant++;
}
break;
default:
if (!commentaire)
{
fini=true;
}
break;
}//switch
//Si c n'est pas interprétable, incrémente l'index
if (!fini)
{
bl[noBloc]->iCourant++;
c=(*source)[bl[noBloc]->iCourant];
}//if(!fini)
}//while
}//if(dansChaine)
}//passeCommentaires();
char Algorithme::leCaractereSuivant()
//Précond : aucune
//Résultat : retourne le caractères suivant (passe éventuellement les commentaires)
// Si iCourant>=iFin, le caractère retourné a pour code 0
{
char temp;
if (!dansChaine) passeCommentaires();
if (bl[noBloc]->iCourant < bl[noBloc]->iFin)
{
temp=(*source)[bl[noBloc]->iCourant];
bl[noBloc]->iCourant++;
}
else
temp=0;
return temp;
}
String Algorithme::leMotSuivant()
//Précond : aucune
//Résultat: retourne le mot suivant le iCourant du bloc en cours (noBloc)
{
String temp("");
int svICourant = bl[noBloc]->iCourant;
char c=leCaractereSuivant();
//si on est dans une chaine, on prend tous les caractères entre les guillemets
if (dansChaine)
{
while (c!='"')
{
temp+=c;
c=leCaractereSuivant();
}
dansChaine=false;
return temp;
}
else
{
//On passe les séparateurs;
while (c!=0 && String::compareTo(leTypeCaractere(c),"separateur",
String::compareSansCondition)==0)
{
svICourant = bl[noBloc]->iCourant;
c=leCaractereSuivant();
}
if (c!=0) //si on n'est pas au bout du bloc
{
if (c=='"')
{
dansChaine=!dansChaine;
temp+=c;
return temp;
}
else
{
//Extraction du type
String typeMot=leTypeCaractere(c);
if (String::compareTo(typeMot,"bloc",String::compareSansCondition)==0)
{
//Si c'est un type bloc, le mot ne contient qu'un caractère
temp+=c;
return temp;
}
else
{
//Sinon, tous les caractères du même type que typeMot font partie du mot
while (c!=0 && String::compareTo(typeMot,leTypeCaractere(c),String::compareSansCondition)==0)
{
//Tant qu'on ne change pas de type de caractère, c'est le même mot
temp+=c;
svICourant = bl[noBloc]->iCourant;
c=leCaractereSuivant();
}//while
//Restauration de l'index
if (c!=0) bl[noBloc]->iCourant=svICourant;
//on renvoie le mot
return temp;
}//if (String::compareTo(typeMot,"bloc",String::compareSansCondition)==0) else
}//if guillemet else
}
else
{
//fin de bloc
return String("");
}
}
}//leMotSuivant
String Algorithme::leTypeCaractere(char c)
//précond : aucune
//Résultat: retourne 'Separateur' si c est un caractère séparateur (/t/espace/n),
// 'Operateur' si c est un caractère opérateur (+-*/=><!)
// 'Bloc' si c est une marque de bloc ({()};)
// 'Chiffre' si c est un chiffre
// 'Lettre' si c est une lettre
// 'Inconnu' sinon
{
String separateur ("\t\n ");separateur+=13;
String operateur ("+-*/=><!");
String bloc ("{()};");
String temp("");
if (String::pos(c,separateur)!=-1)
temp="separateur";
else
if (String::pos(c,operateur)!=-1)
temp="operateur";
else
if (String::pos(c,bloc)!=-1)
temp="bloc";
else
if (c>='0' && c<='9')
temp="chiffre";
else
if ((c>='a' && c<='z')||(c>='A' && c<='Z'))
temp="lettre";
else
temp="inconnu";
return temp;
}
UINT i=0;
//Parcours partiel du tableau des opérateurs jusqu'à trouver le contenu de s
while (i<nbOper && s!=oper[i]) i++;
if (i!=nbOper)
return i;
else
return 9999;
#undef nbOper
}
void Algorithme::executeInstruction(String s)
//Précond : s doit contenir le nom d'appel d'une instruction
//Résultat: exécute l'instruction si elle existe et s'il y a suffisamemt de paramètres
// sur piEntiers-> Sinon, génère une exception ErreurDeSyntaxe.
{
const UINT nbInst=16;
//définition des instructions
String inst[nbInst];
UINT i=0;
//Ne pas insérer de nouvelle instruction, les rajouter à la suite
// modifier nbInst en conséquence (voir le #define au dessus)
inst[i]="commente";i++;
inst[i]="titre";i++;
inst[i]="echange";i++;
inst[i]="element";i++;
inst[i]="dec";i++;
inst[i]="inc";i++;
inst[i]="max";i++;
inst[i]="min";i++;
inst[i]="si";i++;
inst[i]="tantque";i++;
inst[i]="nbElements";i++;
inst[i]="index";i++;
inst[i]="gauche";i++;
inst[i]="droite";i++;
inst[i]="echangeSiSuperieur";i++;
inst[i]="echangeSiInferieur";i++;
//recherche de l'instruction
i=0;
while (i<nbInst &&/*alors*/ String::compareTo(s,inst[i],String::compareSansCasse))
{
i++;
}
if (i==nbInst)
throw ErreurDeSyntaxe();
else
{
switch (i)
{
case 0: //commente
exCommente();
break;
case 1: //titre
exTitre();
break;
case 2: //echange
exEchange();
break;
case 3: //element
exElement();
break;
case 4: //dec
exDec();
break;
case 5: //inc
exInc();
break;
case 6: //max
exMax();
break;
case 7: //min
exMin();
break;
case 8: //si
exSi();
break;
case 9: //tantque
exTantque();
break;
case 10://nbElements
exNbElements();
break;
case 11://index
exIndex();
break;
case 12://gauche
exGauche();
break;
case 13://droite
exDroite();
break;
case 14://echangeSiSuperieur
exEchangeSiSuperieur();
break;
case 15://echangeSiInferieur
exEchangeSiInferieur();
break;
}//switch
}//if (i==nbInst) else
}
bool Algorithme::priorite(UINT nop1,UINT nop2)
//Précond : nop1 et nop2 doivent être des numéros d'opérateurs tels que définis pour
// leNoOperateur()
//Résultat: retourne vrai si la priorité de nop1 >= priorité de nop2
{
bool temp;
switch (nop1)
{
case 11:// (
temp=false;
break;
case 4: // =
if (nop2==11)
temp=true;
else
temp= false;
break;
case 5: //==
case 6: //!=
case 7: //>
case 8: //>=
case 9: //<
case 10: //<=
if (nop2==11 || nop2==4)
temp = true;
else
temp = false;
break;
case 0: //+
case 1: //-
if (nop2==11 || (nop2>=4 && nop2<=10))
temp = true;
else
temp = false;
break;
case 2: //*
if (nop2==11 || nop2<=1 || (nop2>=4 && nop2<=10))
temp = true;
else
temp = false;
break;
case 3: //divise /
if (nop2==11 || nop2<=2 || (nop2>=4 && nop2<=10))
temp = false;
else
temp = true;
break;
case 9999: //instruction
temp = true;
break;
}//switch
return temp;
}
void Algorithme::affectation()
//Précond : la pile d'entiers doit contenir au moins deux éléments,
// et l'avant-dernier doit être un nom de variable
//Action : affecte au nom de variable contenue dans l'avant dernier élément
// de la pile d'entiers la valeur contenue dans son dernier élément
// Si incorrect, génère un objet ErreurDeSyntaxe
{
if (piEntiers->hauteur()<2)
throw ErreurDeSyntaxe();
else
{
int v=recupValeurPiEntiers();
String s=recupNomVarPiEntiers();
if (s.leNbCaracteres()==1 &&
((s[0]>='a' && s[0]<='z') || (s[0]>='A' && s[0]<='Z')))
{
vu->changeValeur(s[0],v);
creeAction("affecte",2,s,String::intToString(v,6,"0",'-'));
}
else
throw ErreurDeSyntaxe();
}
}
void Algorithme::comparaison(UINT nop)
//Précond : la pile d'entiers doit contenir au moins deux éléments,
// nop doit contenir le numéro d'un comparateur (de 5 à 10)
//Action : compare les deux éléments du sommet de la pile, les dépile,
// et opère une comparaison en fonction de nop.
// Si le résultat de la comparaison est faux, empile un 0 sur la pile d'entiers
// si le résultat de la comparaison est vrai, empile un 1
{
if (piEntiers->hauteur()<2)
throw ErreurDeSyntaxe();
else
{
String e="0";
int v2=recupValeurPiEntiers();
int v1=recupValeurPiEntiers();
switch (nop)
{
case 5: //==
if (v1==v2)
{ e="1";creeAction("egaux"); }
else
{ creeAction("pasegaux"); }
break;
case 6: //!=
if (v1!=v2)
{ e="1";creeAction("differents"); }
else
{ creeAction("pasdifferents"); }
break;
case 7: //>
if (v1>v2)
{ e="1";creeAction("plusgrand"); }
else
{ creeAction("pasplusgrand"); }
break;
case 8: //>=
if (v1>=v2)
{ e="1";creeAction("plusgrandegal"); }
else
{ creeAction("pasplusgrandegal"); }
break;
case 9: //<
if (v1<v2)
{ e="1";creeAction("pluspetit"); }
else
{ creeAction("paspluspetit"); }
break;
case 10: //<=
if (v1<=v2)
{ e="1";creeAction("pluspetitegal"); }
else
{ creeAction("paspluspetitegal"); }
break;
default:
throw ErreurDeSyntaxe();
}//switch
piEntiers->empile(e);
}
}
void Algorithme::instruction()
//Précond : la pile de mots ne doit pas être vide,
// et son sommet doit contenir une instruction
//Action : exécute l'instruction, si elle existe et si les paramêtres sont corrects.
// si la pile est vide, l'instruction n'existe pas
// ou si ses parametres ne sont pas corrects,
// génère une exception ErreurDeSyntaxe
{
if (piMots->hauteur()!=0)
{
String in=piMots->sommet();
piMots->depile();
executeInstruction(in);
}//if (!piMots->vide)
}
void Algorithme::creeAction(String action,UINT nbPar,String p0,
String p1,String p2,String p3,String p4)
//Précond : action doit contenir le nom de l'action que CView doit exécuter,
// nbPar doit contenir le nombre de paramêtres dont il faut tenir compte,
// p0,..p4 doivent contenir les valeurs des paramêtres à passer
{
String param[5];
if (nbPar>0) param[0]=p0;
if (nbPar>1) param[1]=p1;
if (nbPar>2) param[2]=p2;
if (nbPar>3) param[3]=p3;
if (nbPar>4) param[4]=p4;
tav->ajouteAction(action,nbPar,param);
}
void Algorithme::exEchange()
//Précond : la pile d'entiers doit avoir au moins deux éléments, représentant
// les index des éléments de la liste à échanger
//Action : échange les deux éléments de la liste d'entiers
{
if(piEntiers->hauteur()<2)
throw ErreurDeSyntaxe();
else
{
UINT v2=recupValeurPiEntiers();
UINT v1=recupValeurPiEntiers();
creeAction("echange",4, String::intToString(v1),
String::intToString(lEntiers->valeurElement(v1)),
String::intToString(v2,2,"0",'-'),
String::intToString(lEntiers->valeurElement(v2)));
lEntiers->echange(v1,v2);
}
}
void Algorithme::exElement()
//Précond : la pile d'entiers doit contenir à son sommet l'index de l'élément
// de la liste d'entiers dont on veut récupérer la valeur
//Action : empile sur la pile d'entiers la valeur de l'élément dont le numéro
// était au sommet de la pile d'entiers
{
UINT pos=recupValeurPiEntiers();
int v=lEntiers->valeurElement(pos);
piEntiers->empile(String::intToString(v));
creeAction("selectionne",1,String::intToString(pos,6,"0",'-'));
}
void Algorithme::exDec()
//Précond : le sommet de la pile d'entiers doit contenir le nom de la variable
// décrémente la variable dont le nom est au sommet de la pile d'entiers
{
String var=recupNomVarPiEntiers();
int v=vu->laValeur(var[0])-1;
creeAction("affecte",2,var,String::intToString(v,6,"0",'-'));
}
void Algorithme::exInc()
//Précond : le sommet de la pile d'entiers doit contenir le nom de la variable
// incrémente la variable dont le nom est au sommet de la pile d'entiers
{
String var=recupNomVarPiEntiers();
int v=vu->laValeur(var[0])+1;
creeAction("affecte",2,var,String::intToString(v,6,"0",'-'));
}
void Algorithme::exMax()
//Précond : la pile d'entiers doit contenir au moins deux éléments.
//Action : lit les deux éléments de la pile,les dépile et retourne
// 1 si le dernier dépilé est plus grand ou égal au précédent,
// 2 si il est plus petit
{
int v2=recupValeurPiEntiers();
int v1=recupValeurPiEntiers();
int v;
if (v1>=v2)
v=1;
else
v=2;
piEntiers->empile(String::intToString(v));
creeAction("leplusgrand",3,
String::intToString(v1),String::intToString(v2),String::intToString(v));
}
void Algorithme::exMin()
//Précond : la pile d'entiers doit contenir au moins deux éléments.
//Action : lit les deux éléments de la pile,les dépile et retourne
// 1 si le dernier dépilé est plus petit ou égal au précédent,
// 2 si il est plus grand
{
int v2=recupValeurPiEntiers();
int v1=recupValeurPiEntiers();
int v;
if (v1<=v2)
v=1;
else
v=2;
piEntiers->empile(v);
creeAction("lepluspetit",3,
String::intToString(v1),String::intToString(v2),String::intToString(v));
}
void Algorithme::exSi()
//Précond : le sommet de la pile d'entiers doit contenir 0 ou 1
//Action : lit le sommet de la pile d'entiers, et le dépile.
// si il est égal à 1 (vrai), ne fait rien.
// si il est égal à 0, modifie l'index courant du bloc en cours pour
// passer la fin de l'instruction (qui peut être un bloc) sans l'exécuter
{
int test=recupValeurPiEntiers();
if (test==0)
{
chercheFinInstruction();
creeAction("sifaux");
}//if (test==0)
else
{
creeAction("sivrai");
}
}
void Algorithme::exTantque()
//Précond : le sommet de la pile d'entiers doit contenir 0 ou 1
//Action ; lit le sommet de la pile d'entiers, et le dépile.
// Si il est égal à 1 (vrai) :
// - repositionne l'index du bloc courant en début du tantque,
// pour l'exécuter à nouveau par la suite
// - crée un nouveau bloc avec toute la fin de l'instruction tantque
// (qui peut être un bloc d'instructions)
// - incrémente le no du bloc courant
// - rend la main
// le nouveau bloc sera exécuté à l'interprétation suivante,et,
// lorsque il sera terminé, il retournera au bloc ayant lancé le tantque,
// pour le ré-exécuter.
{
int test=recupValeurPiEntiers();
if (test==0)
{
//Si faux, on ne passe pas dans l'instruction
chercheFinInstruction();
creeAction("tantquefaux");
}
else
{
//si vrai, on crée un nouveau bloc, et on repositionne l'index du bloc courant
//en début de tantque
int debut=bl[noBloc]->iCourant;
//récupère le mot suivant pour savoir si c'est un début de bloc
String s=leMotSuivant();
//repositionne l'index d'instruction
bl[noBloc]->iCourant=debut;
//recherche de l'instruction suivante pour déterminer la fin du bloc à créer
chercheFinInstruction();
int fin = bl[noBloc]->iCourant-1;
//Positionne l'index du bloc courant au début du tantque
bl[noBloc]->iCourant=bl[noBloc]->iDebInst;
noBloc++;
bl[noBloc]=new Bloc(debut,fin);
//si le tantQue est suivi d'un bloc, on saute le signe "{" pour
//ne pas recréer un bloc
if (s=="{") s=leMotSuivant();
creeAction("tantquevrai");
}
}
void Algorithme::exNbElements()
//Précond : aucune
//Action : donne le nombre d'éléments de la liste d'entiers
{
UINT v=lEntiers->leNbElements();
piEntiers->empile(String::intToString(v));
creeAction("nbelements",1,String::intToString(v));
}
void Algorithme::exIndex()
//Précond : le sommet de la pile d'entiers doit contenir une expression entière,
// et l'élément situé immédiatement au-dessous doit être le nom d'une variable
//Action : Demande à l'interface la création d'un nouvel index, initialisé
// avec la valeur du haut de la pile des entiers,
// et la variable se trouvant au-dessous dans la pile des entiers
{
int v=recupValeurPiEntiers();
String s=recupNomVarPiEntiers();
vu->changeValeur(s[0],v);
creeAction("index",2,s,String::intToString(v));
}
void Algorithme::exGauche()
//Précond : le sommet de la pile d'entiers doit contenir le nom de la variable
// liée à un index
//Action : décale de une unité vers la gauche l'index lié à la variable dont le
// nom est en haut de la pile (en fait, décrémente la variable de une unité).
// Si la valeur est inférieure à un ou supérieure à nbElements, l'index
// n'est pas affiché.
{
String s = recupNomVarPiEntiers();
int x = vu->laValeur(s[0])-1;
vu->changeValeur(s[0],x);
creeAction("gauche",2,s,String::intToString(x));
}
void Algorithme::exDroite()
//Précond : le sommet de la pile d'entiers doit contenir le nom de la variable
// liée à un index
//Action : décale de une unité vers la droite l'index lié à la variable dont le
// nom est en haut de la pile (en fait, incrémente la variable de une unité).
// Si la valeur est inférieure à un ou supérieure à nbElements, l'index
// n'est pas affiché.
{
String s = recupNomVarPiEntiers();
int x = vu->laValeur(s[0])+1;
vu->changeValeur(s[0],x);
creeAction("droite",2,s,String::intToString(x));
}
void Algorithme::exEchangeSiSuperieur()
//Précond : la pile d'entiers doit contenir deux expressions entières indexant
// chacune un élément de la liste d'entiers.
//Action : si l'avant-dernier élément de la pile indexe un élément de la liste
// d'entiers ayant une valeur plus grande que celui indexé par le dernier,
// les deux valeurs sont échangées dans la liste. Sinon, ne fait rien.
{
UINT v2 = recupValeurPiEntiers();
UINT v1 = recupValeurPiEntiers();
if ((v1>=1 && v1<=lEntiers->leNbElements()) &&
(v2>=1 && v2<=lEntiers->leNbElements()))
{
int e1 = lEntiers->valeurElement(v1);
int e2 = lEntiers->valeurElement(v2);
if (e1>e2)
{
lEntiers->echange(v1,v2);
creeAction("echangesuperieur",4,
String::intToString(v1),String::intToString(e1),
String::intToString(v2),String::intToString(e2));
}
else
{
creeAction("echangepassuperieur",4,
String::intToString(v1),String::intToString(e1),
String::intToString(v2),String::intToString(e2));
}
}
else
throw IndexHorsListe();
}
void Algorithme::exEchangeSiInferieur()
//Précond : la pile d'entiers doit contenir deux expressions entières indexant
// chacune un élément de la liste d'entiers.
//Action : si l'avant-dernier élément de la pile indexe un élément de la liste
// d'entiers ayant une valeur plus petite que celui indexé par le dernier,
// les deux valeurs sont échangées dans la liste. Sinon, ne fait rien.
{
UINT v2 = recupValeurPiEntiers();
UINT v1 = recupValeurPiEntiers();
if ((v1>=1 && v1<=lEntiers->leNbElements()) &&
(v2>=1 && v2<=lEntiers->leNbElements()))
{
int e1 = lEntiers->valeurElement(v1);
int e2 = lEntiers->valeurElement(v2);
if (e1<e2)
{
lEntiers->echange(v1,v2);
creeAction("echangeinferieur",4,
String::intToString(v1),String::intToString(e1),
String::intToString(v2),String::intToString(e2));
}
else
{
creeAction("echangepasinferieur",4,
String::intToString(v1),String::intToString(e1),
String::intToString(v2),String::intToString(e2));
}
}
else
throw IndexHorsListe();
}
void Algorithme::exTitre()
//Précond : laChaine contient la chaine à mettre en titre
//Action : demande l'affichage du titre
{
creeAction("titre",1,laChaine);
}
void Algorithme::exCommente()
//Précond : la chaine à ajouter aux commentaires doit être dans laChaine
//Action : demande l'ajout du commentaire donné dans laChaine
{
creeAction("commente",1,laChaine);
}
void Algorithme::chercheFinInstruction()
//Précond : bl[noBloc]->iCourant doit être sur le premier caractère de l'instruction,
// ou du bloc
//Action : Cherche la fin de l'instruction ou du bloc, en tenant compte des blocs
// imbriqués. A la fin, bl[noBloc]->iCourant est sur le premier caractère suivant
// la fin du bloc ou de l'instruction.
// si le premier mot lu est "{", cherche une fin de bloc. Sinon, cherche
// une fin d'instruction (";")
{
bool fini=false;
String s=leMotSuivant();
int imbric=0;
String fin;
if (s=="{")
fin = "}";
else
fin = ";";
//Parcours partiel des mots jusqu'à rencontrer le caractère contenu dans fin
while (s!="" && imbric>=0)
{
s=leMotSuivant();
if (fin=="}")
{
if (s=="{")
imbric++;
else
{
if (s=="}")
imbric--;
}
}
else
if (s==";")
imbric--;
}//while
}
LiftinG
Messages postés3Date d'inscriptionjeudi 20 février 2003StatutMembreDernière intervention31 juillet 2005 29 avril 2004 à 19:47
.:LiftinG:.
Bon moi j'ai réussi a faire un arbre en fonction d'une fonction mathematique, mais je n'arrive pas a l'évaluer, et puis j'ai un pti souci, :sad) j'ai une *char, mais je ne voudrais recuperer ke le premier caractere. bon je sais ke je peut faire vartxt[0], mais je sais pas pkoi ca me donne de drole de resultat, donc peut on tronquer la chaine, kom sous vb avec substr....bon merci d'avance
cs_alain34270
Messages postés85Date d'inscriptionmardi 11 février 2003StatutMembreDernière intervention18 septembre 2005 31 janv. 2004 à 09:47
j'avais développé un petit interpréteur qui utilisait 2 piles : une pour les expressions, et une pour les opérateurs.
Si je pouvais, je calculais au fur et à mesure, mais si je ne le pouvais pas à cause des priorités, j'empilais les opérateurs et les nombres dans leur pile respective. Je continuais jusqu'à ce que la pile des opérateurs soit vide, et que celle des expression ne contienne plus qu'un élément (le résultat).
Enfin, je te dis ça de mémoire, ça commence à faire un peu de temps, maintenant...
Je m'étais inspiré de la notation polonaise post-fixée pour la méthode d'interprétation ( 2+2 -> 2 2 +)
Je ne sais pas si ça peut t'aider, Je pourrais éventuellement te passer le code (c'était mon projet de fin de dut)