Amusant 
pourrais-tu expliquer un peu ce qui se passe pour que ceux qui n'ont jamais vu de prolog s'y intéressent au lieu de partir en courant ?
Difficile d'expliquer ce code sans expliquer le fonctionnement de prolog…
Pour simplifier, on va dire que prolog fait du pattern-matching sur les variables (tout ce qui commence par une majuscule ou _). L'équivalent d'une fonction dans le monde prolog est un prédicat, mais ici l'usage du prédicat npi/3 ressemble fort à celui d'une fonction récursive.
Lorsqu'il y a plusieurs prédicats de même signature (nom + arité), ils sont testés séquentiellement par un mécanisme de backtracking, ce qui permet de poser un prédicat spécial comme condition de sortie.
Et comme il s'agit de prédicats et qu'il n'y a pas de valeur de retour, il est d'usage d'utiliser une variable d'entrée pour stocker le résultat grace au mécanisme d'unification (voir ci-dessous).
Le concept central de prolog est celui d'unification entre deux termes, qui fonctionne dans les deux sens et donne au langage sa forme déclarative.
Par exemple lorsque j'écris [Head | Tail] = Lst, ça signifie que Lst est obligatoirement une liste d'au moins un élément en tête qui sera lié à Head, le reste de la liste étant lié à Tail.
Si certaines de ces variables sont déjà liées, il faudra que l'égalité soit respectée pour que l'unification réussisse.
Une fois certaines variables unifiées, la liaison de l'une d'elles est répercutée sur les autres. (Par ex. si j'écris [Head | Tail] = Lst, Lst = [1,2,3], alors j'aurais Head = 1 et tail = [2,3]).
Voici mon code commenté, en déroulant les unifications qui étaient implicites sur le premier code :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | npi(Symboles, Stack, Result) :- [Nb | Tail] = Symboles, % unifie Nb au premier élement de Symboles % et Tail au reste de la liste number(Nb), !, % si Nb est un nombre, on continue *obligatoirement * % (sinon, le prochain predicat sera testé) NStack = [Nb | Stack], % on push Nb au sommet se Stack pour former NStack npi(Tail, NStack, Result). % appel récursif, Result sera lié par la suite. npi(Symboles, Stack, Result) :- [Op | Tail] = Symboles, % unifie Op au premier élement de Symboles % et Tail au reste de la liste [V1, V2 | CStack] = Stack, % pop V1 et V2 de Stack, la stack est maintanant CStack Expr =.. [Op, V1, V2], % univ, pour créer l'expression Expr = Op(V1, V2) Val is Expr, % Expr est évaluée et le résultat stocké dans Val Nstack = [Val | CStack], % on push Val sur CStack, la stack devient NStack. npi(Tail, NStack, Result). % appel récursif, Result sera lié par la suite. npi(Symboles, Stack, Result):- % (dernier appel) Symboles = [], % s'il ne reste plus de symboles à lire [Result] = Stack. % Result est lié au seul élément restant dans Stack npi(Symboles, Result) :- % prédicat d'arité 2 fourni à l'utilisateur npi(Symboles, [], Result). |
Au final, à l'usage on passe simplement la liste de symboles à évaluer et une variable libre qui va servir à récupérer le résultat.
Pour le niveau 2, tu pourras utiliser les DCG de Prolog
Clairement, mais les DCG ne sont pas hyper pratiques à utiliser dans le cadre de l'exo. Il faut faire des contorsions pour éviter la left-recursion, du coup la grammaire est peu intuitive. (cf. ce post sur SO pour un exemple).
Bonjour.
Je suis de retour avec le niveau 3, toujours en C++ avec LLVM. Le code étant assez conséquent, je vous mets le lien vers le dépôt github.
Partie 2; OCaml.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | type tree = Tree of tree * op * tree | Value of float and op = float -> float -> float let rec eval = function Tree (l, op, r) -> op (eval l) (eval r) | Value e -> e let to_op = function | '+' -> ( +. ) | '-' -> ( -. ) | '*' -> ( *. ) | '/' -> ( /. ) | '^' -> ( ** ) | _ -> failwith "opérateur inconnu" (* Dans l'ordre, on regarde si l'expression est de la forme : - (expression) (1) - expression op expression (2) - nombre (3) *) let rec analyze expr = let rec iter' = function (* Retourne None si expr n'est pas de la forme (2), retourne un arbre sinon. *) | [] -> None | x::xs -> let result = find_op expr x in if result = None then iter' xs else result in let p = pth expr in (* On teste d'abord (1) *) if p = None then let result = iter' ['+';'-';'*';'/';'^'] in (* Si (1) a échoué, teste (2) (il y a plusieurs opérateurs à tester par ordre de précédence) *) if result = None then number expr (* Si (3) a échoué, ne reste plus que (3) ! *) else result else p and pth expr = try if expr.[0] != '(' || expr.[(String.length expr)-1] != ')' then None else analyze (String.sub expr 1 ((String.length expr)-2)) (* Si expr est de la forme (expr') on analyse récursivement sur expr' *) with Invalid_argument "String.sub" -> None and find_op expr opt = try let rec aux expr opt fol = let i = String.index_from expr fol opt in (* on cherche la première occurrence de opt dans expr à partir de l'indice fol *) let left = String.sub expr 0 i in (* on découpe la chaine à gauche et à droite *) let right = String.sub expr (i+1) ((String.length expr)-(i+1)) in match (analyze left, analyze right) with (* on analyse récursivement sur left et right *) | (None, _) -> aux expr opt (i+1) (* si on a obtenu None pour left ou right, on est peut-être juste entré dans une parenthèse sans le vouloir, donc on teste la prochaine occurrence *) | (_, None) -> aux expr opt (i+1) (* mais si on a réussi à obtenir un arbre des deux côtés, on peut construire le nœud supérieur *) | (Some u, Some v) -> Some (Tree (u, (to_op opt), v)) in aux expr opt 0 with (* Si une des exceptions est levée, en particulier Not_found, expr n'est pas de la forme expr' opt expr' *) Not_found -> None | Invalid_argument "String.index_from" -> None | Invalid_argument "String.sub" -> None and number expr = (* on finit par tester si expr est juste un nombre *) try Some (Value (float_of_string expr)) with Failure "float_of_string" -> None let _ = let remove_blanks = Str.global_replace (Str.regexp " +") "" in (* on enlèvera les espaces dès le début *) let s = read_line () in match analyze (remove_blanks s) with | None -> print_string "Expression invalide." (* on a pas réussi à construire un arbre, l'expression donnée n'est pas valide *) | Some tree -> print_float (eval tree) |
Bon présentement ça gère pas les flottants ou ^, mais c'est faisable.
EDIT: Voilà qui est fait.
C'est une bonne idée d'avoir fait quelque chose d'un peu plus original, et ça nous change des contributions en java/c#/ruby/etc. qui sont toutes pareilles à quelques accolades près
Cela dit, je pense que c'est encore perfectible : je n'ai pas OCaml pour tester sous la main et j'ai lu rapidement, mais j'ai l'impression que tu ne gères pas les priorités. Une solution qui marcherait peut-être pour garder l'idée de que tu fais serais de décomposer une expression en somme de facteurs, chaque facteur étant soit une expression parenthésée, soit un produit de facteurs. Mes cours d'analyse syntaxique sont un peu loin, mais il me semble que pour cette grammaire, une descente récursive comme tu as commencé permettrait bien de parsrer correctement les autres expressions.
Sinon, un point de détail : tu utilises !=, mais tu veux probablement plutôt <>. Le premier n'a pas le même sens que dans les autres langages, c'est l'inégalité physique : les deux objets ne pointent pas à la même adresse (en gros). L'inégalité structurelle (les valeurs sont différentes), c'est <>. Note que l'un implique l'autre, mais on peut avoir deux chaînes identiques dans des emplacements différents.
Edit : entendons-nous bien, c'est un atelier intéressant et un bon exercice, même en java ou en python, et vous avez tous bien raison de l'avoir fait. Mais il n'empêche : ces langages étant très similaires, les solutions basées sur l'algo du premier post se ressemblent beaucoup et n'apportent plus grand chose à la discussion. Ce n'est pas pour autant qu'ils ne sont pas intéressants pour leur créateur, et si ça vous fait plaisir et que ca vous motive de poster votre création, ma foi, pourquoi pas ?
Hum, les priorités sont gérées normalement. Merci pour <>, j'ai pas les bonnes habitudes. 
1 2 | # calc "1 - 2 - 3";; (* calc est une fonction qui utilise ton code *) - : float option = Some 2. |
Attention, - est associatif à gauche
J'ai aussi vu que tu as utilisé let _ = ... pour faire une sorte de « fonction main ». Il vaut mieux utiliser let () = ... pour ça : comme _ peut avoir n'importe quel type, tu risques d'avoir des problèmes si tu oublies des choses que le système de types aurait détecté. Par exemple, let _ = print_float compilera très bien, mais n'affichera rien (il manque un paramètre). Si par hasard ce que tu mets dans cette fonction n'est pas de type unit, tu peux soit utiliser ignore, soit expliciter le type en écrivant let _ : int = .... C'est pas cher et ça rend bien service.
Ah ouais, bien vu.
Du coup j'ai juste modifié un truc : quand on cherche une occurrence de +, * (bon pour ceux là osef), - ou / dans la chaine, on cherche en partant de la fin, mais pour ^, on cherche en partant du début. Ça suffit à régler le problème ?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | type tree = Tree of tree * op * tree | Value of float and op = float -> float -> float type associativity = Left | Right let rec eval = function Tree (l, op, r) -> op (eval l) (eval r) | Value e -> e let to_op = function | '+' -> ( +. ) | '-' -> ( -. ) | '*' -> ( *. ) | '/' -> ( /. ) | '^' -> ( ** ) | _ -> failwith "opérateur inconnu" let op_list = [('+', Left); ('-', Left); ('*', Left); ('/', Left); ('^', Right)] (* Les opérateurs et leurs associativités (par défaut à gauche) *) (* Dans l'ordre, on regarde si l'expression est de la forme : - (expression) (1) - expression op expression (2) - nombre (3) *) let rec analyze expr = let rec iter' = function (* Retourne None si expr n'est pas de la forme (2), retourne un arbre sinon. *) | [] -> None | x::xs -> let result = find_op expr x in if result = None then iter' xs else result in let p = pth expr in (* On teste d'abord (1) *) if p = None then let result = iter' op_list in (* Si (1) a échoué, teste (2) (il y a plusieurs opérateurs à tester par ordre de précédence) *) if result = None then number expr (* Si (3) a échoué, ne reste plus que (3) ! *) else result else p and pth expr = try if expr.[0] != '(' || expr.[(String.length expr)-1] != ')' then None else analyze (String.sub expr 1 ((String.length expr)-2)) (* Si expr est de la forme (expr') on analyse récursivement sur expr' *) with Invalid_argument "String.sub" -> None and find_op expr (opt, a) = try let rec aux expr (opt, a) fol = (* on cherche la première occurrence de opt à partir de l'indice fol si opt est associatif à droite et on cherche la dernière avant fol si opt est associatif à gauche. *) let i = (if a = Right then String.index_from expr fol opt else String.rindex_from expr fol opt) in let left = String.sub expr 0 i in (* on découpe la chaine à gauche et à droite *) let right = String.sub expr (i+1) ((String.length expr)-(i+1)) in match (analyze left, analyze right) with (* on analyse récursivement sur left et right *) | (None, _) -> aux expr (opt,a) (if a = Right then i+1 else i-1) (* si on a obtenu None pour left ou right, on est peut-être juste entré dans une parenthèse sans le vouloir, donc on teste la prochaine occurrence *) | (_, None) -> aux expr (opt,a) (if a = Right then i+1 else i-1) (* mais si on a réussi à obtenir un arbre des deux côtés, on peut construire le nœud supérieur *) | (Some u, Some v) -> Some (Tree (u, (to_op opt), v)) in aux expr (opt,a) (if a = Right then 0 else (String.length expr)-1) with (* Si une des exceptions est levée, en particulier Not_found, expr n'est pas de la forme expr' opt expr' *) Not_found -> None | Invalid_argument "String.index_from" -> None | Invalid_argument "String.sub" -> None and number expr = (* on finit par tester si expr est juste un nombre *) try Some (Value (float_of_string expr)) with Failure "float_of_string" -> None let () = let remove_blanks = Str.global_replace (Str.regexp " +") "" in (* on enlèvera les espaces dès le début *) let s = read_line () in match analyze (remove_blanks s) with | None -> print_string "Expression invalide." (* on a pas réussi à construire un arbre, l'expression donnée n'est pas valide *) | Some tree -> print_float (eval tree) |
Bonjour,
Voici ma participation en C++11. J'ai atteint le niveau 3, sans faire les fonctions définies par l'utilisateur.
Fonctions implémentées : min, max, sqrt, cos, sin, tan, PI. Vous pouvez définir des variables.
Le dépot github parce que le code est long : https://github.com/L3nn0x/calculator.git
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 | {"+", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(stod(args[0]) + stod(args[1])); }}, {"-", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(stod(args[0]) - stod(args[1])); }}, {"*", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(stod(args[0]) * stod(args[1])); }}, {"/", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(stod(args[0]) / stod(args[1])); }}, {"^", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(pow(stod(args[0]), stod(args[1]))); }}, {"=", [] (Environment &env, vector<string> args) -> string { if (args[0] == args[1]) { env.remove(args[0]); return ""; } else env.assign(args[0], args[1]); return args[1]; }}, {"min", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return stod(args[0]) < stod(args[1]) ? args[0] : args[1]; }}, {"max", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return stod(args[0]) > stod(args[1]) ? args[0] : args[1]; }}, {"sqrt", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(sqrt(stod(args[0]))); }}, {"cos", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(cos(stod(args[0]))); }}, {"sin", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(sin(stod(args[0]))); }}, {"tan", [] (Environment &env, vector<string> args) -> string { for (auto &i : args) translate(env, i); return to_string(tan(stod(args[0]))); }}, |
Tant qu'à écrire X fois les mêmes lignes, ce qui serait certes utile pour quelqu'un qui utilise la calculatrice en vrai mais n'apporte pas grand chose pour l'exercice, est-ce que ce ne serait pas intéressant d'avoir un système un peu factorisé pour pouvoir ajouter des fonctions plus facilement ? Je ne connais pas C++ suffisamment pour savoir quelle serait la bonne méthode, mais peut-être qu'une table associant un nom à un pointeur de fonction serait pratique, par exemple.
La table associant un nom à une fonction, c'est déjà ce qu'il fait avec des lambdas. Le problème, c'est que c'est à chaque fois la même fonction.
Juste une macro pour factoriser tout ça serait déjà plus propre. Après les C++iens trouveront peut être quelque chose à faire avec les templates.
En tout cas, si une chose a besoin d'être écrite plusieurs fois, c'est qu'il y a clairement un problème.
Sauf que toutes ses lambdas font exactement la même chose, au nom d'une fonction près.
Il y a des shared_ptr qui ne semblent pas utiles (le shared implique une responsabilité partagée, pas un accès).
Pour le bout de code ultra-dupliqué, pas vraiment besoin d'une macro. Un truc du genre :
1 2 | template<class Functor> string translate_and_do(Environment& e, vector<string> args, Functor f); |
A noter : la copie de vector ici me paraît bizarre.
Je reconnais qu'il y a quelque chose à faire sur ce point, mais j'ai cherché à avoir un truc qui fonctionne avant 
En plus, quand j'ai implémenté ça au début, j'avais juste 5 fonctions : +, -, *, / et ^.
Mais je vais voir ce que je peux faire.
J'ai fait des tas d'améliorations comme des commandes, des paramètres et des variables dans ma calculatrice, ainsi que des fonctions . Mais pas la notation infixe, c'est trop dur à implémenter par soi-même 
(je veux dire, je pourrais copier-coller le code source depuis une source externe, mais ça n'a aucun intérêt).
PS : Pour le code, il est relativement bien organisé à part un énorme problème : tout est dans un fichier :s (my bad…).
Mais pas la notation infixe, c'est trop dur à implémenter par soi-même
Au contraire, c'est tout l'intérêt de l'atelier à mon avis : réécrire X fois la même ligne pour rajouter tout plein de fonctions utilisables, ça ne t'apprend pas grand chose. Par contre, t'attaquer aux problèmes que tu ne sais pas encore résoudre est une occasion d'apprendre de nouvelles choses. Bien sûr, si c'est pour recopier sans réfléchir, ça n'a pas un grand intérêt, mais tu peux commencer par essayer de résoudre le problème toi-même, puis regarder la solution en t'efforçant de comprendre comment elle fonctionne une fois que tu y as passé suffisamment de temps pour voir quelles en sont les difficultés.
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte