[The-Snake]

Bonsoir tout le monde !

Je dois programmer une calculatrice avec certaines caractéristiques un peu spéciales...

Pour la petite histoire, c'est une calculatrice complète capable de pas mal de chose. Elle doit gérer n'importe quelle base donnée (hexadecimal, binaire, mais aussi une base improvise si on veut : c'est pas vraiment compliqué ça encore), les parentèses, et les opérations + - / * %.

Le truc c'est que c'est une calculette de "nombre infinis". C'est là que ça me pose problème.
On peut certe écrire un nombre aussi grand que l'on veut dans un tableau de char (dans la limite de la mémoire disponible), mais il faut bien faire des calculs quelque part... et pour ces calculs, il faut travailler avec des int, des long, des ce qu'on veut : et ça implique une limite.
(bon, d'accord, on peut très bien réinventer l'addition de nombres stockés en tableau de char assez facilement, la soustraction aussi, mais pour la multiplication et la division ça va être beaucoup plus horrible, et je ne parle même pas du modulo).

De même, est-ce que je peux prendre des paramètres infinis également ? Par exemple, si je fais trois milliards plus quatre milliards, les trois et quatre milliards devront bien être stocké dans un int à un moment (ou autre chose mais c'est pas grâve : l'essentiel c'est qu'à un moment pour faire le calcul ils devront être dans une variable limitée).
Par conséquent est-il seulement envisageable de gérer des paramètres potentiellement infinis ?

Pour le moment, je n'ai qu'une idée de base : bosser avec des tableaux de chars et un arbre binaire.
Mais je ne vois pas comment manipuler des nombres potentiellements infinis.

Avez-vous une idée de comment ce genre de prouesse peut être réalisé ?

[WiebeN]

même une addition de 2 nombres de 1000 chiffres, si tu les stockes en char* au niveau mémoire c'est pas si énorme... Après oui c'est sur c'est du boulot pour la multiplication etc... Mais bon, au final la multiplication, l'addition et tout on a appris à faire ça en primaire, ce qui montre que le raisonnement est pas si compliqué!

Techniquement je peux pas te donner plus de détails car je ne me suis jamais vraiment penché sur le problème, juste une fois j'ai fait l'addition de deux nombres passé en char* pour une épreuve de NC, et c'était assez rapide à faire !

[The-Snake]

Dans le principe oui, dans le code pas tant que ça.
Surtout pour la division et le modulo... parce qu'au final en travaillant avec des chars, on doit bosser chiffre par chiffre (ou alors je me plante sur toute la ligne ?).

Pour une addition de tableau de char je veux bien croire que ce soit pas trop compliqué. On peut faire ça simplement, additionnant chaque chiffre entre eux avec une ptite bidouille à côté pour les retenues (étant donné que le nombre doit potentiellement être infini je vois pas vraiment d'autres façon de s'y prendre). Pour la soustraction plus ou moins la même chose dans l'autre sens,
La multipilcation c'est déjà autre chose. Et la division et le modulo sont une histoire beaucoup plus inquiétante.

Ca m'inquiète. Je dois donc vraimenrt faire des opérations directement sur des tableaux de char...

[WiebeN]

Oui, il faut travailler avec des char je vois pas d'autre solution... L'addition pas super dur (si ça peut aider je peux peut-être retrouver ma fonction qui le fait mais c'était en php), la soustraction un petit peu plus complexe. Après la multiplication, finalement pas si dur une fois que l'addition est faite.

Je t'invite à poser toi même une petite multiplication pour voir le raisonnement, ex: 

     780
  x   58
  -------
   6240
 39000
-------
45240

La deuxième partie déjà, suffit de réutiliser ta fonction d'addition. Après pour la première, il me semble que tu peux tout à fait utiliser des type int pour chacune des multiplications sans oublier de gérer les retenues, puis tu te débrouilles pour le convertir en char ensuite.
 La division sympathique aussi... en tout cas une fois division et soustraction faites, le modulo c'est du gâteau

Pour avoir 65%8 il suffit de faire 65-(65/8) (en considérant que ta division donne seulement la partie entière du résultat !)

Bonne chance 

[The-Snake]

Finalement c'est vrai que le problème ne réside pas tellement là dedans. Cinq fonctions se chargeront vite fait de cette partie du programme.

Maintenant je me pose surtout des questions sur mon arbre binaire... je ne comprend pas vraiment comment on en créer un.

Je suppose bien qu'il me faudra une structure du genre
struct s_btree
{
  char *data;
  struct s_btree  next_left;
  struct s_btree  next_right;
};

Mais je ne sais pas vraiment comment le créer... comment différencier les opérateurs des nombres, etc...
J'ai vu un peu de documentation sur le net mais c'est énoncé de façon très très complexe (en plus de me laisser en plan sur certains problèmes, par exemple je dois gérer des expressions du type : +--+-31*--+42+32--6+---4, l'utilisateur pouvant à loisir improviser des bases et des opérateurs (on peut utiliser un 'z' à la place du '+' par exemple, mais ça c'est une autre histoire du problème autrement plus facile à résoudre).

J'aimerais savoir comment construire un arbre qui permettra à ma fonction résolvant le calcul de respecter les priorités, les parenthèses, etc...
Je ne vois vraiment pas comment construire l'arbre binaire, je n'arrive pas à concevoir, je me demandais si vous pouviez me donner des pistes.

Par exemple, me représenter l'arbre binaire qui servirait à résoudre l'équation suivante : 36 + 21 * (42 - 3) ?
Je n'arrive vraiment pas à voir comment sera constitué l'arbre binaire de ce programme, et c'est assez bloquant pour coder tout le reste.

[eldergob]

Ça doit donner quelque chose comme ça:
    +
  /   \
36     *
     /    \
   21      -
         /    \
        42    3

[The-Snake]

Effectivement o_o ça déchire.

Je vais faire boulet mais je me demande encore...
Si la priorité était sur le premier élément : 36 * 21 + (42 - 3) ce serait une toute autre forme non ?

         +
     /        \
    -         *
  /    \     /   \
42   3  36  21

Par exemple. Ca rend la réalisation du code qui crée l'arbre (le parser c'est ça ?) extrêmement compliqué. Il faut vraiment comprendre l'expression avant de la retranscrire, et ça... je me sens franchement pas capable de coder ça après 4 semaines de C...
En fait il faudrait créer les dernières branches (36 * 21 et 42 - 3) en tout dernier et remonter l'arbre petit à petit jusqu'à la dernière opération qui sera la première executée dans notre fonction de résolution récursive.

Que fait le parser...
Il tombe sur l'expression 36 * 21 + 12 * (42 - 56).
Il va lire 36 * 21, et créer un élément 36, un élément 21, et un élément * qui les unis.
Il va lire +, que va-t-il faire ?
Il va lire 12 * (42 - 56). Il va créer un élément 42, un 56, et des éléments 12 et - unis par le *.
Et le plus sera l'élément réunissant les deux parties de l'expression.
Non, en terme de code je ne vois vraiment pas comment réaliser ça... pour des expressions plus complexe ça devient du suicide de s'attaquer à ça.

Je me heurte également au problème des opérations avec les bases les plus louches imaginables...
Comment on pourrait se démerder pour faire les opérations dans des bases non numériques (et même numérique, à partir du moment ou on sort de la base 10, on ne peut plus se fier à nos additions et compagnie en C).
Par exemple, si je bosse sur une base du genre 0è-['"é&=à@ (10 chiffres différents, mais rien numériques) je n'ai pas d'autre choix que de convertir le chiffre en base 10.
Donner des valeurs entre 1 et 255 aux chars (ce qui empêche d'utiliser des bases de plus de 255 nombres donc on est pas si infini que ça) et ensuite calculer sous cette forme en utilisant les opérations normales et la longueur de la base ?

On m'a également dit par rapport à la construction de l'arbre de chercher du côté de la grammaire arithmétique... mais sur Google ça se borne à des problèmes dans le programme des écoliers (et un type qui fait du flex) !

[Glovmap]

Oh, un problème epitechien
Pour ma part, puisque j’avais échoué a résoudre via un arbre binaire (problème dans la gestion des unaires avant parenthèses), j’aurai tendance a te déconseillé cette méthode. Et te conseillerais de plutôt de tourner vers la RPN (ou notation polonaise inverse) puis de faire mumuse avec les pointeurs sur chaines de char.
Pour ce qui est de la multiplication, ya une video sur l’intra en prog élémentaire qui devrait bien t’aider.
Pour ce qui est de la division (et du modulo, puisque c’est la même chose au final), soit tu choisi une méthode hardcore a implanter, mais ayant une excellente complexité, ou bien tu te rabats sur ta classe de CM1 et ce que l’on appelle en algorithmique, la méthode de la potence.

[The-Snake]

Bien vu je suis pas le seul ici alors !

Je viens de m'enfiler une après-midi de code pour essayer de résoudre via un arbre binaire, mais je vais googler pour la RPN alors.
En somme, je dois réorganiser l'expression en mettant les opérateurs à part : un type m'a dit qu'il avait fait comme ça mais j'avais abaondonné cette piste. Maintenant je vois que j'avais seulement pas du tout compris le principe : c'est vachement intelligent comme concept o_o !
On a 5*(4+7+3), ça donne d'un côté 4 7 3 et de l'autre + + 5* ! Et ça se résout en faisant 4 + 7, le résultat + 3, le résultat *5. C'est ça ?

Ce doit être assez compliqué à mettre en œuvre tout de même, ça me pose toujours le problème de détecter les premières opérations à résoudre.

Je viens de voir la vidéo sur l'intra, j'ai mieux compris le concept (ça m'a vraiment fait revenir en primaire, j'avais complètement oublié qu'on faisait comme ça à l'époque : maintenant j'ai retrouvé toutes les opérations et j'ai bientôt fini).
Pour la division j'ai commencé par la méthode de la potence en effet (ça nous rajeunit pas...). J'ai du mal à voir comment on pourrait résoudre autrement o_o !

[sirk390]

Je te conseille d'utiliser une pile en faisant du 'shift reduce'.

Tu implemente d'abbord un "scanner" qui te renvoie les tokens un par un dans l'ordre (1 token = 1nombre ou 1 operateur ou 1 parenthese)

Ensuite, pour le "parser" tu emplile les tokens un par un (=shift) en regardant à chaque fois si tu peut faire un 'reduce'  à partir des X elements du haut de la pile.
par exemple tu aura comme règles de 'reduce'
N '+' M  =>   +
                /  \
               N   M
Ici, les 3 elements du haut de la pile sont remplacés par 1 seul arbre contenant l'operation +.

Pour les parentheses la règle de 'reduce' serait:
'(' N ')'   =>   N

Pour gérér la précédence des operateurs (entre l'addition et la multiplication), il faut aussi aller regarder le token qui n'est pas encore sur la pile avant de faire le 'reduce'.

E.g. Si la pile contient:

4, '+', 5 et que le token suivant est '*' il ne faut pas encore faire le 'reduce' mais plutot faire un autre shift (car * > +).

A la fin de l'algo tu va te retrouver avec un seul element dans la pile qui contiendra un arbre que tu pourra parcourrir pour trouver la réponse (comme ceux dans les message précédants).


Voila, j'espère que ca pourra t'aider. Ce n'est pas très détaillé et il peut meme y avoir des détails erronnés, mais ca devrait te donner une idée de comment un vrai parseur fonctionne.
Je ne pense pas que la notation polonaise inversée va t'aider beaucoup car cela demande de changer l'input du programme...
Mais c'est vrai que ce sont les expressions les plus simples à parser.

Je suis un acien d'Epita et j'avais résolu ce problème comme ca.

 

[The-Snake]

Si on doit construire une pile contenant les nombres, opérateurs et parenthèses dans l'ordre, en quoi est-ce différent de la chaîne donnée au départ ?

Je saisis pas bien la chose. C'est un peu comme ça que je voyais le parser à la base, mais j'ai jamais compris comment réaliser ça au niveau du code.

On lit la chaîne, et quand on peut faire une opération on la fait.
Et si on peut pas la faire, on la met sur une pile en attendant que les autres opérations à faire pour qu'elle devienne réalisables soient réalisés. En gros, le parser fait une sorte de factorisation.
Mais au niveau du code... comment concevoir cette pile ? Ou stocker les résultats et comment lier les parties de l'expression résolues et les parties qui ne le sont pas ?

EDIT
J'ai pensé aussi à résoudre directement depuis la pile.
Je construit une pile à partir de structures contenant des nombres, des opérateurs, ou des parenthèses, et je parcours ma chaîne en résolvant ce qui peut être résolut, jusqu'à ce qu'il n'y ait plus qu'un élément à ma pile.

En gros, après avoir crée ma pile j'ai ces éléments :

-12 + 4 * 56 + 13 * (12 +  5 * 3) / 46

Et je résous en parcourant la pile : en gros au fur et à mesure ma chaîne deviendra :
-12 + 4 * 56 + 13 * (12 +  5 * 3) / 46
-12 + 224 + 13 * (12 + 15) / 46
212 + 13 * (27) / 46
212 + 13 * 27 / 46
212 + 8
220
Plus qu'un seul élément à la plie (dans la structure, les variables previous et next sont toutes deux égales à zéro), on a notre grand gagnant.

Ca devrait être possible non ?

[sirk390]

A mon avis tu n'as pas compris ce qu'est une pile.
Cherche un peu sur le web.

[The-Snake]

J'ai passé l'après-midi avec mon binôme à chercher sur internet.

Finalement on a laissé tombé et opté pour une solution inatendue qui n'utilise qu'une liste chaînée... mais qui *devrait* marcher (on le saura quand j'aurais adapté le code des opérations pour modifier la façon dont ça supporte les bases.
C'est la solution la plus conne à laquelle j'ai pu penser, mais elle est pas difficile à réaliser même avec la norme, et elle gère tout les cas que j'ai pû imaginer.
Je me contente de créer à partir de la chaîne une liste chaîné contenant nombres, opérateurs et parenthèses, et je boucle jusqu'à ce que toutes les opérations soient résolus : quand il ne reste plus qu'un élément dans ma liste chaînée, le calcul est terminé et je renvois le résultat.

Ca suit ce shéma :
A + B * C + D
A + B *, on touche pas
B * C : on calcule, ça donne N, on modifie le pointeur sur next de A vers N et le pointeur sur next de N pointera sur D : on fait alors un free de B et C, et voilà !
A la suite, le programme rencontrera donc N + D, calculera alors R le résultat de N + D, et à la prochaine boucle calculera A + R. Ne restera plus qu'un élément : la boucle cessera de tourner.

Pour les parenthèses, je me contente de calculer tout ce qu'il y a à l'intérieur des parenthèses, et quand tout les calculs à l'intérieur sont finis, j'ai donc par exemple (15)*(12). Une fonction "clean" nettoie à la fin de chaque boucle et se débarasse des parenthèses superflues.

On aura peut-être pas le programme le plus rapide, mais on aura le plus simplement pensé.
De toute façon, l'important c'est que ça marche et que ça marche bien.

Ca me tracasse quand même de ne pas avoir pu coder "comme tout le monde" avec un arbre binaire... et de pas saisir le concept des piles. Je suppose qu'une pile est censé me permettre de mettre des opérations en attente (résoudre les opérations que je peux résoudre, mettre les autres dans la pile, quelque chose comme ça ?), mais comment réaliser ça, Dieu le sait.

[jashy]

Epitech quand tu nous tiens
bon courage pour la bistro!!!
les listes chainees et les arbres sont l'avenir 

[mogg41]

Un petit lien qui pourrait te servir: http://www.epitech-lyon.fr/wiki/index.php5/Calcul_par_arbre_binaire

J'espère qu'il n'arrive pas trop  tard.

EDIT: Et par là même occasion http://www.epitech-lyon.fr/wiki/index.php5/Methodes_de_multiplication