1. Accueil
  2. Tous les snippets
  3. Snippets C / C++ / C++.NET
  4. Evaluation d'une chaîne de caractères avec un arbre binaire

Evaluation d'une chaîne de caractères avec un arbre binaire

Soyez le premier à donner votre avis sur cette source.

Snippet vu 7 646 fois - Téléchargée 19 fois

Commenter

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

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;

			s=copy('(');
			d=new arbre(a+1);


    			
  • a='(';a[r]=')';

			reste(&a[r+1]);
			return;
		}else throw Erreur("Parenthèses","'(' sans ')'");
	}
	if(*a=='-')
	{
		if(a[1]=='-')//--
		{
			s=copy("--");
			d=new arbre(a+2);
			return;
		}
		else//-
		{
			s=copy('-');
			d=new arbre(a+1);
			return;
		}
	}
	if(*a=='+')
	{
		if(a[1]=='+')//++
		{
			s=copy("++");
			d=new arbre(a+2);
			return;
		}
		else//+
		{
			s=copy('+');
			d=new arbre(a+1);
			return;
		}
	}
	if(*a=='!')//!
	{
		s=copy('!');
		d=new arbre(a+1);
		return;
	}
	if(*a=='~')//~
	{
		s=copy('~');
		d=new arbre(a+1);
		return;
	}
	if(getop(a,"printf")==0)
	{
		s=copy("printf");
		d=new arbre(a+strlen(s));
		return;
	}
	if(((*a>='A')&&(*a<='Z'))||((*a>='a')&&(*a<='z')))//gestion des variable de a à z et de A à Z
	{//la variable a est différente de A
		int r=getop(a,'=');
		if(r>0)
		{
			s=copy("? =");*s=*a;
			d=new arbre(&a[r+1]);
			return;
		}
		else
		{
			s=copy(*a);
			return;
		}
	}
	if((*a>'0')&&(*a<='9'))
	{
		s=copy(a);
		return;
	}
	reste(a);
}

myint arbre::val()
{
	if(!strcmp(s,";")){g->val();return d->val();}
	if(!strcmp(s,"+"))return g->val()+d->val();
	if(!strcmp(s,"-"))return g->val()-d->val();
	if(!strcmp(s,"*"))return g->val()*d->val();
	if(!strcmp(s,"/"))return g->val()/d->val();
	if(!strcmp(s,"%"))return g->val()%d->val();
	if(!strcmp(s,">>"))return g->val()>>d->val();
	if(!strcmp(s,"<<"))return g->val()<<d->val();
	if(!strcmp(s,">="))return g->val()>=d->val();
	if(!strcmp(s,"<="))return g->val()<=d->val();
	if(!strcmp(s,"&&"))return g->val()&&d->val();
	if(!strcmp(s,"||"))return g->val()||d->val();
	if(!strcmp(s,"=="))return g->val()==d->val();
	if(!strcmp(s,"!="))return g->val()!=d->val();
	if(!strcmp(s,">"))return g->val()>d->val();
	if(!strcmp(s,"<"))return g->val()<d->val();
	if(!strcmp(s,"&"))return g->val()&d->val();
	if(!strcmp(s,"|"))return g->val()|d->val();
	if(!strcmp(s,"^"))return g->val()^d->val();
	if(!strcmp(s,"("))return d->val();
	if(!strcmp(s,"-"))return -d->val();
	if(!strcmp(s,"+"))return d->val();
	if(!strcmp(s,"--"))return d->val()-1;
	if(!strcmp(s,"++"))return d->val()+1;
	if(!strcmp(s,"!"))return !d->val();
	if(!strcmp(s,"~"))return ~d->val();
	if(!strcmp(s,"printf"))return printf("\n%lld",d->val());
	if((*s>='0')&&(*s<='9')){char*a=s;myint r=0LL;while((*a>='0')&&(*a<='9'))r = r*10LL + *a++ - 48;return r;}
	if(((*s>='A')&&(*s<='Z'))||((*s>='a')&&(*s<='z')))
	{
		if(s[1]){myint r=d->val();affecte(*s,r);return r;}
		else return variable(*s); 
	}
	printf("\nErreur : %s non traité\n",s);
	return 0;
}

void terminaison(void)
{//comme son non l'indique, met fin au programme
	Delete(arb);
	printf("Exception non gérée");
	exit(1);
}

int main(int argc,char*argv[])
{
	std::set_terminate(terminaison);//exception non gérée (met fin au programme)
	if(argc==2)//si un seul argument en ligne de commande pour éviter 2+3 -1 au lieu de "2+3 -1"
	{	
		try
		{
			arb=new arbre(argv[1]);
			arb->aff();
			printf("\n= %lld",arb->val());
		}
		catch(Erreur&e){printf(e.what());}
		catch(...){}
		Delete(arb);
	}
	else
	{
		printf("evalue.exe \"2*3 + 7*8 + (5 - 1)\"\n");
		printf("Signes possibles : + ++ - -- * / % > < & | ^ = ! ~ >> >= << <= && || == != ; printf 0-9 A-Z a-z\"\nExemple : evalue.exe \"a=2;3*a\"");
	}
	return 0;
}

A voir également

Ajouter un commentaire Commentaire
alfrai Messages postés 69 Date d'inscription mardi 11 avril 2006 Statut Membre Dernière intervention 23 juillet 2013
6 janv. 2013 à 17:01
Merci pour la source.
Je débute en C et je voudrais savoir comment utiliser votre code ?
S'inscrire maintenant

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.

Du même auteur (pabbati)