|
|
Auteur
|
Message
|
1
|
|
|
|
bonjour, je suis étudiant et j'ai un projet a faire, il faut que je programme une calculatrice:
en gros je doit faire une fonction qui évalue des expression arithmétique ac les opérateurs +-*/ et les parentheses. en rentrant une expression de ce type :(2+3)*2 ma fonction doit me donner le résultat. et je dois utiliser une pile pour les opérateurs et les opérandes.comme je suis un débutant en programmation, je suis un peu perdu...
Si on pouvait me donner des indication pour la demarche a suivre, ca serait cool, parce que je sais trop par ou commencer la. merci
|
|
|
|
|
quel language?
une calculette ca ne va pas etre enormement difficile pour les opperation de base vu que les opérateurs sont deja existants...
|
|
|
|
|
|
le programme est a faire en C...
|
|
|
|
|
Puisque je suppose que tu n'as pas le droit d'utiliser des outils comme lex et yacc (lexeurs/parseurs en C), commence simplement par faire un petit bout de code qui lit ta chaine de caractères et la transforme en tokens. Si tu as du mal, commence par faire une machine à état qui fait ça.
Une fois que tu as fait ça, tu peux commencer la programmation de ta calculette.
L'idée est assez simple: c'est d'utiliser ta pile pour stocker les opérations de faible priorité, et pour regroupper tes expressions prenthésées.
Tu places chaque token dans ta pile au fur et à mesure:
Lorsque tu rencontres un opérateur prioritaire (* ou /), tu regardes si le token suivant est un nombre. Si oui, tu évalues l'opération et tu remplace les éléments de l'opération par leur résultat dans ta pile.
Lorsque tu rencontres une parenthèse fermante, tu remontes ta pile en évaluant les opérations jusqu'à ce que tu rencontres une parenthèse ouvrante. Là, tu regardes si l'opérateur restant dans ta pile (s'il y en a un) est un opérateur prioritaire. Si oui, tu évalues l'opération. Tu remplaces tout ce que tu as utilisé dans ta pile par le résultat.
A chaque instant, tu n'as dans ta pile que:
- des opérandes,
- des parenthèses ouvrantes,
- des opérateurs + et -,
- éventuellement des opérateurs * ou / avant une parenthèse ouvrante (et uniquement avant une parenthèse ouvrante).
J'espère que ça répond à ta question et que je ne me suis pas planté ;-). D'ailleurs c'est plus une réponse algorithmique qu'une réponse en C...
|
|
|
|
|
wouhhh.... ca m'a l'air bien compliqué tout ca, je commence a me demander si je vais arriver a le faire ce projet.... 
ouais, je voudrais savoir c quoi en fait un token?
- cette fonction qui transforme ma chaine de caractère en token, c'est pour différencier les opérateurs et les opérandes?
|
|
|
|
|
Un token, c'est juste un truc abstrait qui représente un élément de ton expression. Dans notre cas, les opérateurs, les parenthèses et les opérandes sont des tokens.
A ne pas confondre avec des caractères: les opérandes sont constituées de plusieurs caractères. C'est pour ça que j'ai parlé de token. Ne te laisse pas impressionner par ce genre de termes, c'est très simple en fait.
Désolé de t'avoir effrayé, c'était pas le but.
Pour répondre à ta question, cette fonction transforme la chaine de caractères:
(23 + 17) * 456
en
Token ( de type parenthèse ouvrante,
Token 43 de type "nombre",
Token + de type opérateur +,
Token 17 de type nombre,
Token ) de type parenthèse fermante,
Token * de type opérateur *,
Token 456 de type "nombre".
En C un token peut être représenté par une structure du genre:
#define OPEN_PAR 1
#define CLOSE_PAR 2
#define NUMBER 3
#define OPERATOR_PLUS 4
#define OPERATOR_MINUS 5
#define OPERATOR_MUL 6
#define OPERATOR_DIV 7
struct Token {
int type; // Type de token
char* chaine; // Le char* correspondant
int data; // Les données éventuelles (pour un entier, ce sera la valeur du nombre... à remplacer par double si tu veux des nombres à virgule...)
};
PS: c'est un peu prise de tête, mais c'est pas compliqué du tout. Ne t'inquiètes pas, tu y arriveras.
-->Message édité par Sylvain31 le 05/01/2006 12:52:51<--
|
|
|
|
|
oui, merci pour l'explication pour les tokens.
Donc si j'ai bien compris, apres avoir définis une structure pour les tokens, je doit écrire une fonction pour convertir ma chaine de caractère en token. (c'est bien une fonction que je dois ecrire?)
mais la, je vois vraiment pas comment faire pour la coder...
je sais pas si je l'ai dit, mais je débute en programmation.
PS:petite précision, je dois ecrier un programme qui évalue les expression aritmétique sur un seul chiffre décimal, ce qui , j pense facilite un peu les choses.
|
|
|
|
|
Effectivement, ça facilite: plus besoin de tokens... juste des caractères.
Donc tu n'as plus besoin de fonction lexeur.
Analyser une chaine de caractères est un truc très simple. Une chaine de caractères c'est une suite de char, dont le premier est à une adresse mémoire spécifiée par un char*, et dont le dernier a la valeur 0.
Donc, pour analyser chaque caractère de ta chaine, tu fais un truc du genre:
char* machaine = "(2+3*4)*4";
char* caractère;
for (caractère = machaine ; caractère++ ; *caractère != 0)
{
switch (*caractère) {
case '(': // Traitement pour parenthèses ouvrantes...
break;
case '+': // Traitement pour +...
...
default: // Traitement pour le reste...
break;
}
}
Pour les détails, faut relire l'algorithme du dessus...
Bon courage.
|
|
|
|
|
ah oui d'accord. Je vais essayer de voir tout ca et essayer d'avancer.
Ben je te remercie beaucoup pour les aides que tu m'a deja fournit.
|
|
|
|
|
|
N'hésites pas si t'as besoin...
|
|
|
|
|
donc si j'ai bien compris,
je parcours ma chaine caractère:
-si le caractère est un chiffre, un +, un -, ( et *ou/ devant (, alors j'empile.
-si j'ai *ou/ je regarde le caractere suivant, si c'est un chiffre, j'effectue l'opération.
-si j'ai une ) j'évalue en remontant jusqu'a la parenthèse ouvrante.
Mais pour évaluer en remontant, je dois faire comment? utiliser de la récursivité? évaluer en remontant et en faisant l'opération a chaque fois que je rencontre un caractère?
|
|
|
|
|
Il faut que tu utilises une pile. (comme décrit dans ton énnoncé).
Par exemple: (2 + 3*2) * 4
PUSH signifie qu'on pousse une valeur dans la pile. POP signifie qu'on retire une valeur dans la pile.
On trouve '('. PUSH '('.
On trouve '2'. PUSH '2'.
On trouve '+'. PUSH '+'.
On trouve '3'. PUSH '3'.
On trouve '*'. On regarde après: on trouve 2. Il faut évaluer.
POP -> on trouve 3
On évalue 3*2 = 6 -> PUSH 6
On trouve ')': remonter jusqu'à '('.
POP -> on trouve 6
POP -> On trouve +
POP -> On trouve 2
On évalue 2+6 = 8
POP -> On trouve '('. Evaluation de la parenthèse terminée. On pousse son résultat:
PUSH 8
Puis on continue la lecture de la chaine.
On trouve '*': le caractère d'après est 4: on évalue:
POP -> On trouve 8
On évalue 4*8 = 32.
Aucun caractère restant: on vérifie que la pile est bien vide (sinon syntax error).
(2 + 3*2) * 4 = 32
C'est tout simple.
|
|
|
|
|
oui, d'accord.
L'évaluation je l'integre donc a ma fonction d'analyse de la chaine?
La fonction qui analyse ma chaine de caractère c le main() du programme?
En admettant que j'ai défini une fonction PUSH et POP:
je reprend l'exemple de la multiplication suivant d'un caractere qui est un nombre:
en code ca devrait donner quelque chose qui ressemble a ca?
case '*':
c=caractere++; //ca je sais pas si le compilateur l'accepte...
if (c==NOMBRE)
PUSH(POP() * c);
else if ...
PS:comme je débute, j'écrit peut etre des horreurs, je m'en excuse a l'avance.
|
|
|
|
|
C'est un peu plus compliqué que ça. Déjà, organise ton code avec des fonctions (faut prendre de bonnes habitudes et faut structurer ton code, même en C).
Tu vas devoir te faire une fonction du genre:
bool isNumber(char c);
int toNumber(char c);
void push(int c);
int pop();
#DEFINE PLUSOPERATOR -1
#DEFINE MINUSOPERATOR -2
#DEFINE MULOPERATOR -3
#DEFINE DIVOPERATOR -4
#DEFINE OPENPAR -5
#DEFINE CLOSEPAR -6
#DEFINE NOELEMENTINSTACK -7
Ensuite, tu vas avoir plusieurs fonctions du genre:
parse() -> analyse la chaine de caractères.
int evalParenthesis() -> Evalue tout ce qu'il y a dans la pile jusqu'à la parenthèse ouvrante. Si aucune prenthèse ouvrante -> erreur. Retourne ne résultat de l'évaluation
Au niveau variables, tu as:
char* expression; // L'expression d'origine.
char* current; // Le pointeur vers le caractère en cours d'analyse.
int currentValue; // Une valeur en mémoire.
Ta fonction parse:
PUSH(OPENPAR); // On commence par ajouter une parenthèse ouvrante... Permet de regroupper toute l'expression à l'intérieur de parenthèses.
for (current = expression; *current != 0; current++) { // On parcours la chaine
char c = *current;
if (isNumber(c)) { // Si c'est un simple nombre, on l'empile
PUSH(toNumber(c));
}
else {
switch(c) { // Si c'est un opérateur simple non prioritaire, on l'empile
case '(':
PUSH(OPENPAR); break;
case '+':
PUSH(PLUSOPERATOR); break;
case '-':
PUSH(MINUSOPERATOR); break;
case '*': // S'il est prioritaire, on tente d'évaluer
if (isNumber(current[1])) {
int val1 = POP();
int val2;
if (val1 < 0) // opérateur ?
erreur();
current++;
val2 = toNumber(*current);
val1 = val1 * val2;
PUSH(val1);
}
else { // Sinon, on l'empile
if (current[1] != '(')
erreur();
PUSH(MULOPERATOR);
}
break;
case '/':
if (isNumber(current[1])) {
int val1 = POP();
int val2;
if (val1 < 0) // opérateur ?
erreur();
current++;
val2 = toNumber(*current);
val1 = val1 / val2;
PUSH(val1);
}
else {
if (current[1] != '(')
erreur();
PUSH(DIVOPERATOR);
}
break;
case ')': { // Si c'est une parenthèse fermante, on évalue
int val1 = evalParenthesis();
int operator = POP();
// Puis on vérifie s'il y a un opérateur prioritaire avant
if (operator == NOELEMENTINSTACK) {
PUSH(val1);
}
else if (operator == MULOPERATOR) { // Si oui, on l'évalue
int val2 = POP();
if (val2 < 0)
error();
val1 = val2 * val1;
PUSH(val1);
}
else if (operator == DIVOPERATOR) {
int val2 = POP();
if (val2 < 0)
error();
val1 = val2 / val1;
PUSH(val1);
}
else { // sinon, on remet tout en place dans la pile
PUSH(operator);
PUSH(val1);
}
}
break;
default: erreur(); break;
}
}
}
// A la fin, on évalue tout jusqu'à la parenthèse ouvrante qu'on a ajouté.
// nb: tester aussi s'il reste quelque chose dans la pile à la fin. Si oui, erreur...
return evalParenthesis();
La fonction evalParenthesis évalue les opérateurs présents dans la pile. Je rappelle que les seuls opérateurs présents dans la pile, entre deux parenthèses ne peuvent être que des + et des -, (les * et / ont déja été évalués, ou alors ils sont placés juste avant la parenthèse ouvrante). L'algo est alors ssez simple. L'idée, c'est de partir de 0, et d'ajouter ou soustraire à ce nombre l'ensemble des nombres présents dans la pile en fonction de l'opérateur placé devant.
Ta fonction evalParenthesis:
int currentvalue = 0;
int currentoperator = PLUSOPERATOR;
int stackValue;
int nbElements; // Compteur d'éléments entre les parenthèses. Erreur si aucun.
while ((stackValue = POP()) != NOELEMENTINSTACK) { // On remonte la pile
int val = 0;
if (stackValue = OPENPAR) { // Si parenthèse ouvrante, on a fini de remonter
break;
}
if (stackValue < 0) // Si c'est un opérateur, erreur. Ce doit être un nombre
erreur();
nbElements++;
val = stackValue;
currentoperator = stackValue;
if (currentoperator > 0) // Si c'est un nombre, erreur. Ce doit être un opéreur
erreur();
if (currentoperator == OPENPAR) { // Si parenthèse ouvrante, on a fini.
currentValue += val; // On ajoute le dernier nombre.
break;
}
switch(currentoperator) { // Evaluation: il ne peut y avoir que des opérateurs non prioritaires (+ et -)
case PLUSOPERATOR:
currentValue += val;
break;
case MINUSOPERATOR:
currentValue -= val;
break;
default:
erreur();
break;
}
}
if (stackValue != OPENPAR)
erreur();
return currentvalue;
Ca devrait aller mieux maintenant non ?
|
|
|
|
|
|
ah ok, ben je vais regarder. en fait moi j'avais fait, depuis hier, une fonction push, une fonction pop, et le reste l'analyse de la chaine, ds le main...mais je m'en sortai pas. je vasi revoir tout ca. merci.
|
|
|
|
|
ouais,ca y est, j'arrive a compiler mon programme! mais à l'éxecution, j'ai une erreur de segmentation... de quoi ca peut venir? les pointeurs?
|
|
|
|
|
Très probablement.
Dans ce genre de situations, soit tu as un debugger et tu peux excécuter ton code en pas à pas pour savoir ce qui se passe, soit tu mets des printf un peu partout pour voir ou ça pète.
|
|
|
|
|
|
c'est une erreur qui vient du main? ou bien elle peut etre dans n'importe laquelle des mes fonctions..
|
|
|
|
|
|
Met des printf un peu partout, et dès que tu as ton erreur, tu verras sur lequel de tes printf le programme c'est arrêté.
|
|
|
|
|
ouais, j'ai vu ou ca s'arrete, grace au print f, c'est dans ma fonction parse qu'il y a un problème. je met un bout de mon code, c le début de ma fonction parse, si jamais tu vois ce que ca peut etre...
parse()
{
PUSH(OPENPAR); // On commence par ajouter une parenthèse ouvrante... Permet de regroupper toute l'expression à l'intérieur de parenthèses.
-----------l'erreur se trouve entre cette ligne-----------------
for (current = expression; *current != 0; current++) {
char c = *current;
-----------et celle-ci-----------------------------------------
if (isdigit(c)) { // Si c'est un simple nombre, on l'empile
PUSH((int)(c));
............
.....
..
.
|
|
|
|
|
|
je me posai une question la, il me faut une fonction malloc pour affecter de la mémoire dynamique pour l'expression de ma chaine de caractère?
|
|
|
|
|
Il faut vérifier le contenu de la variable expression. Cette vartiable est-elle correctement initialisée ? (faire un printf de cette variable avant d'entrer dans la boucle).
Faire aussi un printf("%s\n", current) à chaque boucle.
Vérifier que les PUSH et POP ne font pas de débordement de buffer.
Le code a l'air correct, donc le pétage vient d'ailleurs. (même s'il se produit ici). Vérifier qu'il n'y a pas un current++ ailleurs...
Bref, faut fouiller...
|
|
|
|
|
ouais, je n'ai pas réussi à trouver l'erreur a temps, c'était pour hier.
Je pense que je m'y remettrai le mois prochain, les exams approchent...
Ent tout cas je te remercie beaucoup pour toute l'aide que tu m'as donné.
|
|
|
|
|
Pas de pb 
|
|
|
1
|
|
|
|
