Écrivez un programme qui lit une expression mathématique simple, et affiche le résultat de son évaluation.
Une expression est une chaîne de caractères sans espaces, qui est soit un nombre entier (qui peut être négatif), soit une chaîne contenant une parenthèse ouvrante, une expression, un opérateur, une expression, puis une parenthèse fermante.
Cinq valeurs sont possibles pour le caractère opérateur :
L'addition : '+'.
La soustraction : '-'.
La multiplication : '*'.
La division entière : '/'.
Le modulo : '%'.
Votre programme doit impérativement utiliser une fonction récursive, et non une boucle..
Limites de temps et de mémoire (C++)
Temps : 0,25 s sur une machine à 1 GHz.
Mémoire : 1 000 ko.
Contraintes
On vous garantit que chaque valeur manipulée, que ce soit une valeur fournie dans l'entrée, ou un résultat de l'évaluation d'une sous-expression, tient dans une variable de type int en C (entier 32 bits signé).
L'expression peut contenir jusqu'à 1 million de caractères, il n'est donc pas possible de la stocker entièrement en mémoire.
Exemples
Exemple 1
entrée :
42
sortie :
42
Exemple 2
entrée :
(3+4)
sortie :
7
Exemple 3
entrée :
(((3+4)*3)-(5/2))
sortie :
19
Commentaires
Indice : Pour vous simplifier le travail, notez que lorsque vous exécutez scanf("%d", &nombreLu), la fonction retourne 1 si un nombre a pu être lu, et 0 sinon (l'entrée n'est pas un nombre). Vous pouvez alors retenter de lire l'entrée en utilisant scanf("%c", &carLu).
j'ai fait ce code qui passe tous les tests sauf 1 du fait du dépassement de la capacité mémoire, mais normal vu la contrainte.
#include <iostream>
#include <stack>
#include <string>
int evaluateExpression(std::string expr, int &i);
int main()
{
std::string expr;
getline(std::cin, expr);
int i = 0;
std::cout << evaluateExpression(expr, i) << '\n';
return 0;
}
int evaluateExpression(std::string expr, int &i)
{
std::stack<int> numbers;
std::stack<char> operations;
for (; i < (int) expr.length(); i++)
{
if (expr [i] == ' ')
continue;
if (isdigit(expr [i]))
{
int num = 0;
while (i < (int) expr.length() && isdigit(expr [i]))
{
num = num * 10 + (expr [i] - '0');
i++;
}
i--;
numbers.push(num);
}
else if (expr [i] == '(')
{
int subExprResult = evaluateExpression(expr, ++i);
numbers.push(subExprResult);
}
else if (expr [i] == ')')
{
break;
}
else
{
while (!operations.empty() && operations.top() != '(')
{
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
char op = operations.top();
operations.pop();
int result = 0;
switch (op)
{
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num1 / num2;
break;
case '%':
result = num1 % num2;
break;
}
numbers.push(result);
}
operations.push(expr [i]);
}
}
while (!operations.empty())
{
int num2 = numbers.top();
numbers.pop();
int num1 = numbers.top();
numbers.pop();
char op = operations.top();
operations.pop();
int result = 0;
switch (op)
{
case '+':
result = num1 + num2;
break;
case '-':
result = num1 - num2;
break;
case '*':
result = num1 * num2;
break;
case '/':
result = num1 / num2;
break;
case '%':
result = num1 % num2;
break;
}
numbers.push(result);
}
return numbers.top();
}
Une idée serait de lire l'entrée caractère par caractère avec getchar() peut etre mais je coince là dessus
Bonjour, Merci d'indiquer un titre de sujet en rapport avec votre problématique.
Le message qui suit est une réponse automatique activée par un membre de l'équipe de modération. Les réponses automatiques leur permettent d'éviter d'avoir à répéter de nombreuses fois la même chose, ce qui leur fait gagner du temps et leur permet de s'occuper des sujets qui méritent plus d'attention. Nous sommes néanmoins ouverts et si vous avez une question ou une remarque, n'hésitez pas à contacter la personne en question par Message Privé. Pour plus d'informations, nous vous invitons à lire les règles générales du forum
Mauvais titre
Le titre est un élément important qui ne doit pas être négligé. N'oubliez pas cette règle simple : le titre idéal résume la question que vous allez poser en une petite phrase. Il doit permettre aux visiteurs de se repérer facilement dans le forum visité et d'identifier le sujet à sa seule lecture.
Vous pouvez utiliser divers préfixes comme [Erreur], [MySQL], [Compatibilité], etc... Aussi, pensez à consulter les règles propres à chaque forum (visibles dans les topics épinglés en haut des sections).
De plus, choisir un bon titre permet de rendre plus faciles les recherches des autres membres.
Les titres de type "besoin d'aide" ou "problème" ne sont pas tolérés.
Merci de modifier votre titre. Pour cela, éditez le premier message de votre sujet.
(titre originel : Besoin d'aide sur un exercice de France IOI)
Je ne suis pas tout à fait sûr. Mais la string en paramètre est passée par copie. Moi je la passerais par référence constante, surtout si tu l'appelles récursivement, elle va être copiée un paquet de fois, et sur une chaine d'un million de caractères... Mais bon le compilateur optimise peut-être ça tout seul. À essayer pour voir.
int evaluateExpression(std::string const& expr, int &i);
Mais en fait si l'expression contient 1 million de caractères, comme je la copie une première fois, sans faire des calculs je dépasse déjà la capacité autorisée.
une possibilité serait lire l'entrée du terminal caractère par caractère
Je ne peux pas y accéder, il faut valider les précédents... En tout cas un million de caractères, cela représente 1Mo, c'est rien du tout en mémoire. Et pas besoin de la copier. Comment cette chaîne de caractère est-elle récupérée ?
Ca veux dire que tu as une boucle potentiellement infinie. Pourquoi n'as tu pas écris une boucle for ?
parce que ça sert à rien les données d'entrée sont parfaites, je sais ce que je fais, merci. C'est moins sécurisé dans l'absolu, mais plus lisible. En plus ta remarque ne répond absolument pas au problème du PO.
Duncan4031 a écrit:
Test 6
Erreur
Votre programme a échoué à la suite d'un accès mémoire en dehors des zones réservées, ou d'un dépassement de la limite de mémoire.
0 %
- Edité par Duncan4031 il y a 41 minutes
Désolé j'avais mal compris. Mon approche n'est pas la bonne, il faut lire le flux chiffre par chiffre et caractère par caractere au fur et à mesure dans une fonction récursive avec la fonction scanf, comme précisé dans l'indice.
Le code est censé être écrit en C++ ? Pourquoi l'énoncé parle de scanf() ?Alors, pourquoi ne pas utiliser getchar() dans ce cas?
Je reproduis l'énoncé:
> Limites de temps et de mémoire (C++)
Donc on est en C++ ?
> dans une variable de type int en C (entier 32 bits signé). L'expression peut contenir jusqu'à 1 million de caractères, Pourquoi mentionner "C" si on est en C++ ? > il n'est donc pas possible de la stocker entièrement en mémoire. Donc, il est dit qu'on ne peut pas tout lire d'un coup.
On ne parle pas de la priorité des opérateurs. Je ne vois pas pourquoi on aurait besoin de deux switch dans ce cas.
- Edité par PierrotLeFou 1 février 2023 à 2:19:07
Le Tout est souvent plus grand que la somme de ses parties.
Le code est censé être écrit en C++ ? Pourquoi l'énoncé parle de scanf() ?
C'est malheureusement (ou pas) classique pour ce genre de site. Le but est d'avoir un résultat, quelque soit la qualité du code. Il n'y a aucune vérification faite sur le code, juste les résultats selon différentes valeurs d'entrées. Ca pourrait même être du C, tant que ca compile avec un compilateur C++.
Pour ça que si le but est d'apprendre le C++, je déconseille ce genre de site. C'est juste de la competitive programming, ca peut être amusant et ça permet de pratiquer l'algo, mais c'est bof pour l'apprentissage correcte d'un langage.
PierrotLeFou a écrit:
Donc, il est dit qu'on ne peut pas tout lire d'un coup.
A mon avis, c'est la raison de l'échec du test de mémoire. Ils ont probablement mis un grosse chaine pour tester si elle est stockée en mémoire.
Donc il faut virer le "std::string expr;".
En pratique, comme tu prends un string et un index i, il suffit juste de réorganiser le code pour prendre un char.
Pour le "while(1)", on s'en fout en fait, la condition d'arrêt sera le scanf qui retourne plus de caractère.
Puisqu'il y a ambigüité sur le langage à utiliser, je l'ai fait en C, pas en C++, à moins que ce soit du C+- ... Et ça compile bien en C++
L'équivalent de getchar() en C++ est std::cin.get(). Les comportements semblent identiques. Je suppose que tous les opérateurs ont la même priorité et que les expressions n'ont pas d'erreur de syntaxe ou de sémantique. - #include <stdio.h> #include <string.h> #include <ctype.h>
int expression(void);
int main(void) { printf("%d\n", expression()); }
int expression() { int acc = 0; int num; char op = '\0'; char c = getchar(); while(c != '\n' && c != ')') { if(strchr("+-*/%", c) != NULL) { op = c; c=getchar(); } else { if(c == '(') { num = expression(); c = getchar(); } else { num = 0; while(isdigit(c)) { num = num * 10 + c - '0'; c = getchar(); } } switch (op) { case '\0': acc = num; break; case '+': acc += num; break; case '-': acc -= num; break; case '*': acc *= num; break; case '/': acc /= num; break; case '%': acc %= num; break; } } } return acc; }
- Edité par PierrotLeFou 1 février 2023 à 6:33:50
Le Tout est souvent plus grand que la somme de ses parties.
le site est intéressant car il permet de réfléchir sur les algorithmes. Et associé au cours de zeste de savoir ça permet je trouve de bien avancé.
Le C++ est mal utilisé et la plupart des solutions sont du C saupoudrées de C++. Sachant qu'en plus leur compilateur est resté au C++11.
Pour répondre à @PierrotLeFou oui tu es sensé donner une réponse en C++.
Mais comme souvent les conseils donnés sont assez pourris et ne portent que sur un langage, le correcteur de l'exercice ne prenant pas la peine de différencier le C du C++.
Edit : Bravo @PierrotLeFou ton programme passe tous les tests,
parce que ça sert à rien les données d'entrée sont parfaites, je sais ce que je fais, merci. C'est moins sécurisé dans l'absolu, mais plus lisible. En plus ta remarque ne répond absolument pas au problème du PO.
Tu sais ce que tu fait, par contre l'OP et autres lecteurs, j'ai des doutes. et s'ils prennent modèle sur toi ===> Catastrophe assurée.
On se doit d'apporter une valeur pédagogique, présenter une solution c'est bien, présenter une solution correcte c'est mieux.
parce que ça sert à rien les données d'entrée sont parfaites, je sais ce que je fais, merci. C'est moins sécurisé dans l'absolu, mais plus lisible. En plus ta remarque ne répond absolument pas au problème du PO.
Tu sais ce que tu fait, par contre l'OP et autres lecteurs, j'ai des doutes. et s'ils prennent modèle sur toi ===> Catastrophe assurée.
On se doit d'apporter une valeur pédagogique, présenter une solution c'est bien, présenter une solution correcte c'est mieux.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Discord NaN. Mon site.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.