Evaluation d'une chaîne de caractères avec un arbre binaire
Contenu du snippet
La chaîne de caractères est "parsée" dans un arbre binaire
L'arbre est affiché, puis évalué (avec des nombres entiers)
Ce programme peut évoluer
L'arbre est affiché, puis évalué (avec des nombres entiers)
Ce programme peut évoluer
Source / Exemple :
#include <string.h>
#include <stdio.h>
#include <exception>
#include <cstdlib>
//typedef __int64 myint;
typedef long long int myint;
myint var[52];//stockage des variables de A à Z et de a à z
class arbre;//un arbre binaire
arbre*arb=NULL;
template<typename Type> void Delete(Type &d){if(d)delete d;d=NULL;}
//gestion de notre système d'erreur
class Erreur:public std::exception
{
private:const char*s;const char*c;
public:Erreur(const char*c,const char*s):c(c),s(s){}
const char*what(void)const throw(){printf("Erreur : (%s) -> ",c);return s;}
};
//on "ôte" les "espaces" en début et en fin de chaîne
char*espace(char*a)
{
while(*a==' ')a++;// on ôte les espaces en début de chaîne
return a;
}
//ce qui n'a pas été traité dans une chaîne
void reste(char*a)
{//s'il reste une chaîne impossible à traiter
a=espace(a);
if(*a)throw Erreur("Reste",a);
}
int getop(char*a,char op)
{//retourne la place du caractère op dans a
int i,r;
for(r=i=0;a[i];i++)
{
if(a[i]=='"')//on saute les chaînes
{
while(a[++i]&&(a[i]!='"'))
{
if((a[i]=='\\')&&(a[i+1]=='"'))i++;
}
}
if(a[i]=='(')r++;
if(a[i]==')')r--;//uniquement en dehors des parenthèses
if((r==0)&&(a[i]==op)&&(a[i+1]!=op))//un seul caractère et non 2 de suite
{
if((i>0)&&(a[i-1])==op)continue;//et non 2 de suite (avec celui d'avant)
return i;
}
}
return r?-i-2:-1;//retourne -1 si non trouvé et < -1 si les '(' ne correspondent pas aux ')'
}
int getop(char*a,const char*op)
{//retourne la place de op dans a
int i,r;
for(r=i=0;a[i];i++)
{
if(a[i]=='"')//on saute les chaînes
{
while(a[++i]&&(a[i]!='"'))
{
if((a[i]=='\\')&&(a[i+1]=='"'))i++;
}
}
if(a[i]=='(')r++;
if(a[i]==')')r--;//uniquement en dehors des parenthèses
if((r==0)&&(a[i]==*op))//le premier caractère est trouvé
{
int m;
for(m=1;op[m];m++)//on regarde la suite
{
if(a[i+m]!=op[m]){m=0;break;}//les chaînes ne sont pas identiques
}
if(m)return i;//les chaînes sont identiques
}
}
return -1;//retourne -1 si non trouvé
}
void affecte(char c, myint r)//uniquement de A à Z et de a à z
{//affectation de r à la variable
if(c>='a')var[c-'a'+26]=r;
else var[c-'A']=r;
}
myint variable(char c)//uniquement de A à Z et de a à z
{//retourne la variable stockée (0 si non initialisé)
return c>='a'?var[c-'a'+26]:var[c-'A'];
}
class arbre
{
char*s;//stockage d'une chaîne
arbre*g,*d;//pointeurs gauche et droite
public:
~arbre(){Delete(s);Delete(g);Delete(d);}
arbre(char*x);
myint val();
void aff(){if(g)g->aff();if(s)printf(" %s",s);if(d)d->aff();}
};
char*copy(const char*x)
{
return strcpy(new char[1+strlen(x)],x);
}
char*copy(char x)
{
char*z=new char[2];*z=x;z[1]=0;return z;
}
arbre::arbre(char*a)
{
s=NULL;g=d=NULL;
a=espace(a);
char op[]=";+-*/%";
for(int n=0;n<strlen(op);n++)
{
int r=getop(a,op[n]);
if(r>0)
{
a[r]=0;
s=copy(op[n]);
g=new arbre(a);
d=new arbre(&a[r+1]);
a[r]=op[n];
return;
}
}
const char*ops[]={">>","<<",">=","<=","&&","||","==","!="};
for(int n=0;n<7;n++)
{
int r=getop(a,ops[n]);
if(r>0)
{
a[r]=0;
s=copy(ops[n]);
g=new arbre(a);
d=new arbre(&a[r+2]);
a[r]=*ops[n];
return;
}
}
char o[]="><&|^";
for(int n=0;n<strlen(o);n++)
{
int r=getop(a,o[n]);
if(r>0)
{
a[r]=0;
s=copy(o[n]);
g=new arbre(a);
d=new arbre(&a[r+1]);
a[r]=o[n];
return;
}
}
if(*a=='(')//gestion des parenthèses
{
int r=getop(a,')');
if(r>0)
{
- a=a[r]==0;
- a='(';a[r]=')';
A voir également
- Evaluation d'une chaîne de caractères avec un arbre binaire
- Parcourir une chaine de caractère en python ✓ - Forum Python
- Extraction d'une partie d'une chaine dans une chaine - Forum Python
- Chaine de caractère ✓ - Forum Python
- Calculer la hauteur d'un arbre ✓ - Forum C / C++ / C++.NET
- Trouver toutes les positions d'une lettre dans une chaine - Forum Python
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.