(Octobre 2015) Créez une calculatrice

a marqué ce sujet comme résolu.
Banni

C'est plutôt surprenant pour un langage aussi moderne.
Après, on peut relativiser et se dire qu'inclure quelques lignes de codes, toujours identiques, ça ne mange pas de pain.

Emeric

Oui, une fois qu'on la fait, on le copie colle quelque part et c'est bon.

En fait je pense qu'elle n'y est pas car Swift a été pensé pour créer des applis graphiques, pour Mac ou iBidule, donc pas besoin d'une fonction input() qui ne serait utilisable qu'en console. Ça va peut être changer vu que Swift va être portable vers Linux.

poliorcetics

La version 2.0 de Swift, sortie mi-septembre, dispose désormais de la fonction readLine() pour les entrées au clavier. Voir : https://developer.apple.com/library/mac/documentation/Swift/Reference/Swift_StandardLibrary_Functions/#//apple_ref/swift/func/s:FSs8readLineFT12stripNewlineSb_GSqSS_ ou de façon plus concise : http://swiftdoc.org/v2.0/func/readLine/.

+1 -0

Cette réponse a aidé l’auteur du sujet

Bonjour.

Voici mon implémentation du niveau 2 en C++ avec LLVM. En plus des opérateurs de l'énoncé, le moins unaire est supporté.

  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <sstream>
#include <string>

#include <llvm/IR/DerivedTypes.h>
#include <llvm/IR/IRBuilder.h>
#include <llvm/IR/LLVMContext.h>
#include <llvm/IR/Module.h>
#include <llvm/IR/Verifier.h>
#include <llvm/IR/Intrinsics.h>
#include <llvm/ExecutionEngine/ExecutionEngine.h>
#include <llvm/ExecutionEngine/MCJIT.h>
#include <llvm/Support/TargetSelect.h>

namespace Token
{
        enum Type
        {
                eof = -1,
                number = -2
        };
}

class InvalidInput : public std::exception
{};

class Lexer
{
        public:
        Lexer() : line_{}, number_{0.0}, last_{'\0'}, last_token_{Token::eof}
        {}

        Lexer(Lexer const&) = delete;
        Lexer& operator=(Lexer const&) = delete;

        Lexer(Lexer&&) = default;
        Lexer& operator=(Lexer&&) = default;

        ~Lexer() = default;

        void newline(std::string&& line)
        {
                line_ = std::istringstream{std::move(line)};
                last_ = ' ';
        }

        char next()
        {
                if (!is_valid())
                        return Token::eof;

                while (std::isspace(last_))
                        last_ = static_cast<char>(line_.get());

                if (last_ == decltype(line_)::traits_type::eof())
                        return last_token_ = Token::eof;

                if (std::isdigit(last_) || last_ == '.')
                {
                        std::string str_num{};
                        bool decimal{last_ == '.'};
                        do
                        {
                                str_num += last_;
                                last_ = static_cast<char>(line_.get());
                                if (last_ == '.')
                                        decimal = decimal ? throw InvalidInput{} : true;
                        } while (std::isdigit(last_) || last_ == '.');
                        try
                        {
                                number_ = stod(str_num);
                        }
                        catch (std::logic_error const&)
                        {
                                throw InvalidInput{};
                        }
                        return last_token_ = Token::number;
                }
                last_token_ = last_;
                last_ = static_cast<char>(line_.get());
                return last_token_;
        }

        double number() const
        {
                assert(last_token_ == Token::number);
                return number_;
        }

        bool is_valid() const
        {
                return line_.good();
        }

        private:
        std::istringstream line_;
        double number_;
        char last_;
        char last_token_;
};

class ExprTree
{
        public:
        virtual ~ExprTree() = default;

        virtual llvm::Value* codegen(llvm::Module&, llvm::IRBuilder<>&) = 0;
};

class NumberTree : public ExprTree
{
        public:
        NumberTree(double number) : ExprTree{}, number_{number}
        {}

        llvm::Value* codegen(llvm::Module&, llvm::IRBuilder<>&) override
        {
                return llvm::ConstantFP::get(llvm::getGlobalContext(), llvm::APFloat(number_));
        }

        private:
        double number_;
};

class UnaryExprTree : public ExprTree
{
        public:
        UnaryExprTree(char op, std::unique_ptr<ExprTree> st)
                : op_{op}, st_{std::move(st)}
        {}

        llvm::Value* codegen(llvm::Module& module, llvm::IRBuilder<>& builder) override
        {
                auto strep = st_->codegen(module, builder);

                switch (op_)
                {
                        case '-':
                                return builder.CreateFNeg(strep, "neg");
                        default:
                                throw InvalidInput{};
                }
        }

        private:
        char op_;
        std::unique_ptr<ExprTree> st_;
};

class BinaryExprTree : public ExprTree
{
        public:
        using Node = std::unique_ptr<ExprTree>;

        BinaryExprTree(char op, Node lhs, Node rhs)
                : op_{op}, lhs_{std::move(lhs)}, rhs_{std::move(rhs)}
        {}

        llvm::Value* codegen(llvm::Module& module, llvm::IRBuilder<>& builder) override
        {

                auto lrep = lhs_->codegen(module, builder);
                auto rrep = rhs_->codegen(module, builder);

                llvm::Function* pow_fn{nullptr};
                if ((pow_fn = module.getFunction("llvm.pow.f64.f64")) == nullptr)
                {
                        std::vector<llvm::Type*> args_type{llvm::Type::getDoubleTy(llvm::getGlobalContext()),
                                                           llvm::Type::getDoubleTy(llvm::getGlobalContext())};
                        pow_fn = llvm::Intrinsic::getDeclaration(&module, llvm::Intrinsic::pow, args_type);
                }

                switch (op_)
                {
                        case '+':
                                return builder.CreateFAdd(lrep, rrep, "add");
                        case '-':
                                return builder.CreateFSub(lrep, rrep, "sub");
                        case '*':
                                return builder.CreateFMul(lrep, rrep, "mul");
                        case '/':
                                return builder.CreateFDiv(lrep, rrep, "div");
                        case '^':
                                return builder.CreateCall(pow_fn, {lrep, rrep}, "pow");
                        default:
                                throw InvalidInput{};
                }
        }

        private:
        char op_;
        Node lhs_;
        Node rhs_;
};

int operator_precedence(char op)
{
        static std::map<char, int> ops
        {{'+', 10},
         {'-', 10},
         {'*', 20},
         {'/', 20},
         {'^', 30}};

        if (ops.find(op) == std::end(ops))
                return -1;
        return ops[op];
}

enum class Associativity
{
        left,
        right,
        unknown
};

Associativity operator_associativity(char op)
{
        static std::map<char, Associativity> ops
        {{'+', Associativity::left},
         {'-', Associativity::left},
         {'*', Associativity::left},
         {'/', Associativity::left},
         {'^', Associativity::right}};

        if (ops.find(op) == std::end(ops))
                return Associativity::unknown;
        return ops[op];
}

class Parser
{
        public:
        Parser() : lex_{nullptr}, cur_tok_{Token::eof}
        {}

        Parser(Parser const&) = delete;
        Parser& operator=(Parser const&) = delete;

        Parser(Parser&&) = default;
        Parser& operator=(Parser&&) = default;

        ~Parser() = default;

        std::unique_ptr<ExprTree> parse(Lexer& lex)
        {
                lex_ = &lex;
                cur_tok_ = lex_->next();
                auto ast = parse_expr_();
                if (cur_tok_ != Token::eof)
                        throw InvalidInput{};
                return ast;
        }

        private:
        std::unique_ptr<ExprTree> parse_expr_()
        {
                std::unique_ptr<ExprTree> lhs{nullptr};
                if (cur_tok_ == '-')
                {
                        auto un_op = cur_tok_;
                        cur_tok_ = lex_->next();
                        lhs = std::make_unique<UnaryExprTree>(un_op, parse_top_());
                }
                else
                        lhs = parse_top_();
                return parse_binary_rhs_(0, std::move(lhs));
        }

        std::unique_ptr<ExprTree> parse_top_()
        {
                switch (cur_tok_)
                {
                        case Token::number:
                                return parse_number_();
                        case '(':
                                return parse_paren_();
                        default:
                                throw InvalidInput{};
                }
        }

        std::unique_ptr<ExprTree> parse_number_()
        {
                auto res = std::make_unique<NumberTree>(lex_->number());
                cur_tok_ = lex_->next();
                for (auto op : {'+', '-', '*', '/', '^', ')', static_cast<char>(Token::eof)})
                {
                        if (cur_tok_ == op)
                                return std::move(res);
                }
                throw InvalidInput{};
        }

        std::unique_ptr<ExprTree> parse_paren_()
        {
                cur_tok_ = lex_->next();
                auto ex = parse_expr_();
                if (cur_tok_ != ')')
                        throw InvalidInput{};
                cur_tok_ = lex_->next();
                return ex;
        }

        std::unique_ptr<ExprTree> parse_binary_rhs_(int expr_prec, std::unique_ptr<ExprTree> lhs)
        {
                while (1)
                {
                        auto cur_prec = operator_precedence(cur_tok_);
                        if (cur_prec < expr_prec)
                                return lhs;
                        auto bin_op = cur_tok_;
                        cur_tok_ = lex_->next();

                        auto rhs = parse_top_();
                        auto next_op = cur_tok_;
                        auto next_prec = operator_precedence(next_op);
                        while (cur_prec < next_prec ||
                            (operator_associativity(next_op) == Associativity::right && cur_prec == next_prec))
                        {
                                rhs = parse_binary_rhs_(next_prec, std::move(rhs));
                                next_op = cur_tok_;
                                next_prec = operator_precedence(next_op);
                        }

                        lhs = std::make_unique<BinaryExprTree>(bin_op, std::move(lhs), std::move(rhs));
                }
        }

        Lexer* lex_;
        char cur_tok_;
};

int main()
{
        llvm::InitializeNativeTarget();
        llvm::InitializeNativeTargetAsmParser();
        llvm::InitializeNativeTargetAsmPrinter();

        Lexer lex{};
        Parser p{};
        std::ostringstream out{};
        std::string in{};
        std::cout << "Use Ctrl^C to exit.\n";
        while (1)
        {
                try
                {
                        auto module = std::make_unique<llvm::Module>("Calc", llvm::getGlobalContext());
                        llvm::IRBuilder<> builder{llvm::getGlobalContext()};
                        std::cout << "> ";
                        std::getline(std::cin, in);
                        lex.newline(std::move(in));
                        auto ast = p.parse(lex);
                        auto calc_type = llvm::FunctionType::get(llvm::Type::getDoubleTy(llvm::getGlobalContext()), {}, false);
                        auto calc_main = llvm::Function::Create(calc_type, llvm::Function::InternalLinkage, "cmain", module.get());

                        auto block = llvm::BasicBlock::Create(llvm::getGlobalContext(), "entry", calc_main);
                        builder.SetInsertPoint(block);
                        builder.CreateRet(ast->codegen(*module, builder));
                        llvm::verifyFunction(*calc_main);

                        std::unique_ptr<llvm::ExecutionEngine> engine{llvm::EngineBuilder{std::move(module)}.create()};
                        engine->finalizeObject();

                        auto tmp = engine->getPointerToFunction(calc_main);
                        auto cmain = reinterpret_cast<double(*)()>(reinterpret_cast<intptr_t>(tmp));
                        std::cout << cmain() << '\n';
                }
                catch (InvalidInput const&)
                {
                        std::cout << "Invalid input.\n";
                }
        }
}

Édité par Praetonus

Mon Github | Pony : Un langage à acteurs sûr et performant

+1 -0

mais ici, tu voudrais qu'il réponde « attention, tu as oublié de vérifier que le pop avait bien réussi ».

C'est l'idée.

Et c'est tout le problème : un compilateur, aussi évolué soit-il, ne peut pas deviner quelle était ton intention.

Est-ce que tu voudrais vraiment d'une écriture tab[index] qui te renvoie un Option<T> que tu es obligé de déconstruire à chaque utilisation ?

Pourquoi pas. Je suis sérieux, c'est là une question de cohérence. Soit on fait confiance au développeur et on considère que s'il demande une connerie, le programme fait une connerie, soit le langage est stricte et ne laisse pas passer des conneries. Là, on est dans un entre deux. Dans l'idée, ça signifierait que tout élément extrait d'un itérable est une Option. C'est générique, simple (même si lourd) et cohérent, donc oui, je préférerais.

Comme je le reconnais, la sûreté, ça se justifie. Laisser des contournements aussi immédiats me semble contradictoire.

Attention à ne pas croire non plus que, parce qu'il ne t'avertit pas qu'il pourrait y avoir un problème, on est dans le cas du C. Je ne connais pas suffisamment Rust pour en être sûr, mais étant donné ce que j'en ai vu, je suis à peu près convaincu que si tu exécutes un programme qui contient ce genre d'erreur, tu vas manger une exception. En C, pour peu que le tableau soit juxtaposé en mémoire avec des données qui appartiennent aussi à ton programme, il va silencieusement continuer à s'exécuter en accédant à ces données (au lieu de ton tableau) comme si de rien n'était… Et paf, ça fait des buffer overflows. Donc non, si tu demandes une connerie, le programme ne va pas « faire une connerie », du moins pas dans le sens où ça se passerait en C ou en C++. Il va s'arrêter en te disant « non, désolé, ça n'est pas valide ». Encore une fois, on aime bien que ce genre de vérification soit fait au maximum à la compilation : avoir la garantie qu'un programme qui compile est correct est un peu le Graal des systèmes de type. Mais c'est un sujet difficile, qui, en plus du fait qu'on veut accessoirement un système de types utilisable, flirte avec l'indécidabilité, ce qui n'arrange rien.

Donc, le type Option ici n'est pas là pour t'assurer que ton programme ne va pas lire des valeurs absurdes. Il est là pour t'assurer que tu as pris en compte, d'une façon ou d'une autre, la possibilité que le pop ait échoué (parce que le tableau était vide). Finalement, c'est une question de cas d'usages : en règle générale, quand tu demandes à accéder à l'élément d'indice i d'un tableau, tu t'attends à ce qu'il y ait bien une case i dans le tableau. Si jamais ça ne marche pas, ça va lever une exception, que tu pourras éventuellement récupérer pour gérer ce cas. Mais on s'attend en règle générale à ce que ça marche. À l'inverse, dans le cas général où on travaille avec des piles, on peut raisonnablement supposer que le cas où la pile est vide est un cas normal d'utilisation, qui ne correspond pas à une erreur, y compris quand on essaye de faire un pop. Par exemple, si tu te sers de ta pile pour faire un backtracking, ça indiquera qu'il n'y a plus de possibilité de revenir en arrière, et que le problème n'a pas de solution. Comme ce n'est pas à proprement parler un cas d'erreur exceptionnel mais un cas possible, qu'il faut donc traiter, on fait apparaître cette possibilité dans le type de la fonction. Le typeur s'assure ainsi que tu vas prévoir ce cas.

Voilà donc un élément de réponse pour expliquer la différence de comportement entre ces deux fonctions. C'est toujours une histoire de compromis : bien sûr, idéalement, on voudrait que le traitement correct des exceptions soit entièrement vérifié par le typeur. Mais le mieux est l'ennemi du bien : si ton système de type inclut dans le type de chaque fonction la possibilité qu'elle échoue avec un Out_of_memory, tu n'es pas vraiment plus avancé. Encore une fois, par rapport au C, tu gagnes déjà un avantage énorme en faisant échouer un programme incorrect plutôt qu'en le faisant continuer à s'exécuter dans un état incohérent.

L'autre problème dont tu ne parles pas et qui m'a bien frustré, c'est la doc. La doc de pop dit

Removes the last element from a vector and returns it, or None if it is empty.

Je croyais en lisant ça qu'il retournant soit un élément du vecteur, soit None (comme fait python pour certaines fonctions, par exemple). Sauf qu'en fait, il retourne un truc qu'il faudra évaluer. J'ai complètement mésinterprété la doc, mais avec mon bagage, c'était couru d'avance.

Pour le coup, la faute est entièrement de ton côté, comme tu le remarques. Une documentation n'est ni un document formel (au sens mathématique) qui décrit de façon précise le comportement des fonctions, ni un tutoriel qui explique ce comportement en des termes accessibles à n'importe quel débutant. Il faut un minimum de bagage pour pouvoir la lire, et en l'occurrence, tu ne peux pas comprendre ce que fait cette fonction sans connaître le type Option. Ce n'est pas le rôle de la documentation de pop de te l'expliquer. Si tu veux continuer à découvrir le langage (ce que je t'encourage à faire, parce que la curiosité n'est jamais un défaut en programmation), je te conseille plutôt de prendre un document destiné à l'apprentissage, ou au moins à lire la documentation de façon honnête et approfondie : si une fonction renvoie un type que tu ne connais pas, va lire la documentation de ce type avant de te plaindre qu'il n'a pas le comportement que tu supposais sans aucune information. Rust n'a a priori aucune raison de se comporter comme Python, et c'est une mauvaise idée de supposer que c'est forcément le cas quand tu n'es pas allé vérifier.

C'est le but : offrir un langage de programmation système avec un système de types censé qui apporte une sûreté très largement absente du C++ ou du C. Il se trouve qu'effectivement, ces systèmes de types ont été à l'origine développés sur une base de langages fonctionnels.

Donc je fais pleinement partie du public cible du langage. J'ai dit le contraire plus haut, donc je vais un peu développer. Mon usage typique, c'est d'envoyer une simulation qui va tourner pendant 3 jours. Si ça plante, je dois tout recommencer. Le langage doit donc aider à la fiabilité tout en étant rapide. S'il aide à la parallélisation, c'est gagné, je prends. ^^ Sauf que. Sauf que mes profs/collègues trouvent que l'excellente doc de numpy est horriblement compliqué et qu'on ne trouve jamais ce qu'on cherche dedans. On m'a parlé de Rust comme d'un truc qui a pour but de remplacer le C++. Mais comment diables voulez-vous que je propose ça à mes collègues ? Théoriquement, c'est génial, mais la marche à franchir est dantesque. La doc, en ne mettant pas le système de vérification dans les exemples, le compilateur en sortant des messages long et pas super clairs n'aident en rien.

Je redis aussi ce que j'ai dit plus haut : avoir un programme sécurisé, ce n'est pas gratuit. Les gens ont souvent la fausse impression, en venant de langages non-sûrs comme Python ou Javascript, que les langages typés sont « casse-couilles » ou pénibles à utiliser, et que l'apport en sécurité serait en réalité quelque chose de pénible : « en Python, j'ai soit un int soit None, je n'ai pas besoin de récupérer l'entier depuis un type Option ». La réalité, c'est qu'un langage sûr, ce n'est pas un langage qui sécurise tes programmes tout seul, c'est un langage qui t'empêche d'écrire des programmes non-sûrs. Mais quand on est habitué à écrire, en Python, des programmes qui ne sont pas corrects parce que c'est facile et rapide et que le compilateur laisse faire, forcément, quand un langage typé refuse, c'est assez vexant. Si tes collègues ne sont pas prêts à reconnaître qu'un programme typé est sensiblement aussi complexe dans les deux langages, et que la seule différence est que les programmes simples et cassés ne seront pas acceptés en Rust, effectivement, ça aura du mal à passer.

Aparté : je ne suis pas informaticien. Mes collègues non plus. Ce n'est pas le cœur de métier, même si c'est massivement utilisé. Quand je dis que mes collègues sont mauvais en programmation, c'est un constat et non une critique : il va falloir faire avec ce niveau en informatique. Quand aux jeunes que j'ai côtoyer, c'est kif-kif.

Soyons honnêtes : s'il existe des études spécialisées dans l'informatique, ce n'est pas pour rien. Programmer n'est pas quelque chose de très compliqué, mais écrire des programmes complexes et corrects demande un travail d'apprentissage réel, qu'il s'agisse de méthodes pour ne pas écrire trop de bêtises dans des langages permissifs ou de l'utilisation pertinente du système de types expressif d'un langage plus strict. Si tes collègues ne sont pas prêts à sauter le pas, il n'existe pas de solution miracle pour que leurs programmes marchent.

Aparté bis : l'un des trois points mis en avant par Rust est le "concurency". S'il aide vraiment à la parallélisation, les opportunités d'un point de vue simulations sont vraiment importantes. D'où une plus grande frustration encore. J'hésite vraiment entre inutilisable pour moi et super utile. Et je n'exclue pas que ce soit les deux. :-°

Comme dit plus haut, je ne connais pas suffisamment Rust pour me lancer sur la question. Je peux toutefois hasarder une réponse : il me semble que Rust utilise des types représentant des permissions pour une fonction d'utiliser une variable (mutable). Si la permission sur une variable est unique, ça garantit que deux fonctions ne peuvent pas simultanément accéder à la même variable mutable : on évite ainsi tous les problèmes de race condition, encore une fois grâce au système de types. Peut-être est-ce pour ça qu'on parle d'un langage adapté pour la concurrence. Est-ce que pour autant c'est une caractéristique facile à utiliser ? Je ne sais pas.

+0 -0

Cette réponse a aidé l’auteur du sujet

J'aime beaucoup ce défi, bien progressif, qui fait découvrir des algorithmes et techniques très utilisés et pourtant peu connus de beaucoup de développeurs.

Du coup je me suis lancé dedans, en Java, vous trouverez mon avancée dans ce dépôt GitHub, les commits correspondant aux niveaux de l'énoncé. Pour l'instant il n'y a que le niveau 1 mais avec la gestion des erreurs. Comme celle-ci est assez pénible pour peu de valeur ajoutée, je vous mets ici le code de la version sans celle-ci. Et comme apparemment dans ces défis il est de bon ton de programmer dans une langue exotique, le code est en coréen (mais affiche du français) :

 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
package info.kisai.zds.calculator;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.function.BiFunction;

/**
 * Created by spacefox on 04/10/15.
 */
public class 역폴란드표기법계산기 {

    private static final Map<String, BiFunction<Double, Double, Double>> 운영자 = new HashMap<>();
    static {
        운영자.put("+", (운1, 운2) -> 운1 + 운2);
        운영자.put("-", (운1, 운2) -> 운1 - 운2);
        운영자.put("*", (운1, 운2) -> 운1 * 운2);
        운영자.put("/", (운1, 운2) -> 운1 / 운2);
        운영자.put("^", (운1, 운2) -> Math.pow(운1, 운2));
    }

    private Deque<Double> 스택 = new LinkedList<>();

    public double 평가(String 입력) {
        스택.clear();
        String[] 요소 = 입력.split(" ");
        for (String  : 요소) {
            if (운영자.containsKey()) {
                double 운1 = 스택.pop();
                double 운2 = 스택.pop();
                스택.push(운영자.get().apply(운2, 운1));
            } else {
                스택.push(Double.parseDouble());
            }
        }
        return 스택.pop();
    }
}

 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
package info.kisai.zds.calculator;

import java.util.Scanner;

public class 명령줄인터페이스 {

    private 역폴란드표기법계산기 계산기 = new 역폴란드표기법계산기();

    private void 표시() {
        Scanner 스캐너 = new Scanner(System.in);
        String 입력;
        System.out.println("Calculatrice en notation polonaise inversée");
        System.out.println("Tapez « q » pour quitter");
        while (true) {
            입력 = 스캐너.nextLine();
            if ("q".equalsIgnoreCase(입력)) {
                System.out.println("Au revoir !");
                return;
            }
            System.out.println(계산기.평가(입력));
        }
    }

    public static void main(String... args) {
        new 명령줄인터페이스().표시();
    }
}

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Bon d'accord, je vous la fait aussi en anglais :

Le calculateur :

 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
package info.kisai.zds.calculator;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.function.BiFunction;

/**
 * Created by spacefox on 04/10/15.
 */
public class RPNCalculator {

    private static final Map<String, BiFunction<Double, Double, Double>> OPERATORS = new HashMap<>();
    static {
        OPERATORS.put("+", (o1, o2) -> o1 + o2);
        OPERATORS.put("-", (o1, o2) -> o1 - o2);
        OPERATORS.put("*", (o1, o2) -> o1 * o2);
        OPERATORS.put("/", (o1, o2) -> o1 / o2);
        OPERATORS.put("^", (o1, o2) -> Math.pow(o1, o2));
    }

    private Deque<Double> stack = new LinkedList<>();

    public double eval(String in) {
        stack.clear();
        String[] elements = in.split(" ");
        for (String e : elements) {
            if (OPERATORS.containsKey(e)) {
                double o1 = stack.pop();
                double o2 = stack.pop();
                stack.push(OPERATORS.get(e).apply(o2, o1));
            } else {
                stack.push(Double.parseDouble(e));
            }
        }
        return stack.pop();
    }
}

L'interface pour l'utiliser :

 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
package info.kisai.zds.calculator;

import java.util.Scanner;

public class CLI {

    private RPNCalculator calculator = new RPNCalculator();

    private void show() {
        Scanner scanner = new Scanner(System.in);
        String in;
        System.out.println("Calculatrice en notation polonaise inversée");
        System.out.println("Tapez « q » pour quitter");
        while (true) {
            in = scanner.nextLine();
            if ("q".equalsIgnoreCase(in)) {
                System.out.println("Au revoir !");
                return;
            }
            System.out.println(calculator.eval(in));
        }
    }

    public static void main(String... args) {
        new CLI().show();
    }
}

Édité par SpaceFox

Ce qui est rigolo, c'est que les opérations sont du code OCaml valide : on écrit let x = start push 1 push 2 add finish, et ça affecte 3 à x dans le programme OCaml. Je vous mets quelques exemples avec le code, et si vous avez des questions, n'hésitez pas. J'aimerais aussi regarder ce que ça donne avec une pile typée qui peut contenir des valeurs de type différents, par exemple des entiers et des booléens, probablement avec quelques GADT. Peut-être que si ça plaît aux foules, ce serait aussi amusant d'en profiter pour essayer un langage avec des types dépendants, comme Coq ou Idris, pour prouver des choses du genre pop . dup = id.

Eusèbe

Je n'ai rien sous la main pour essayer mais ça a l'air intéressant. Est-ce que tu as commencé à faire quelque chose dans ce sens ?

Je suppose qu'avec des GADT seulement, tu peux écrire des programmes comparables à tes x et y dont les types sont vérifiés par OCaml à la compilation. Ça revient à utiliser le système de types du langage hôte pour définir un DSL statiquement typé (par opposition à ton langage actuel qui est faiblement (ou "dynamiquement", blablabla) typé). C'est l'idée ?

Je ne suis pas sûr qu'il y ait beaucoup de choses intéressantes à faire avec des preuves, sinon. Ça a l'air d'être essentiellement des rewrites sur des propriétés assez simples. Bien sûr je peux me tromper.

+0 -0

Cette réponse a aidé l’auteur du sujet

[Maxi HS]

Berdes, je me doutait qu'il fallait faire un truc comme ça (même si j'aurai été incapable de le faire), mais ce n'est pas ce qu'encourage la doc. Et mes connaissance en Rust ou en fonctionnel ne me permettaient pas de deviner.

Le plus simple pour débutter n'est pas la doc, mais the book. La doc est une doc technique, et donc en effet pas évidente à lire pour débuter. Le livre part d'un niveau plus bas et introduit bien les concepts.

Donc je fais pleinement partie du public cible du langage. J'ai dit le contraire plus haut, donc je vais un peu développer. Mon usage typique, c'est d'envoyer une simulation qui va tourner pendant 3 jours. Si ça plante, je dois tout recommencer. Le langage doit donc aider à la fiabilité tout en étant rapide. S'il aide à la parallélisation, c'est gagné, je prends. ^^

Moi aussi =) Et je trouve Rust plutôt adapté pour faire des simulations : ce bout de code (en exclu ZdS!) est beaucoup plus clair que le code équivalent C++, et plus facile à maintenir que la version Julia (oui, ça fait deux fois que je le re-écris…).

Sauf que. Sauf que mes profs/collègues trouvent que l'excellente doc de numpy est horriblement compliqué et qu'on ne trouve jamais ce qu'on cherche dedans. On m'a parlé de Rust comme d'un truc qui a pour but de remplacer le C++. Mais comment diables voulez-vous que je propose ça à mes collègues ? Théoriquement, c'est génial, mais la marche à franchir est dantesque.

La marche est en effet très grande, d'autant qu'il manque encore un peu de ressources pour grand débutant/scientifiques qui n'ont pas 3 ans pour bidouiller leur code. En plus il y a des bouts fonctionnels dedans, ce qui n'aide pas pour des gens habitués au Fortran 77 … Il faut ré-apprendre à penser la programmation et c'est douloureux.

La doc, en ne mettant pas le système de vérification dans les exemples, le compilateur en sortant des messages long et pas super clairs n'aident en rien.

Au contraire, je trouve les message du compilateur très utiles, une fois que l'on a compris le fonctionnement du langage : les traits, le borrow checker, …

[/Maxi HS]

J'ai repris ton code @Gabbro, pour le transformer en quelque chose de plus rustique.

 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
use std::io;

fn main() {
    let mut pile: Vec<f64> = Vec::new(); //> Seule annotation de type nécessaire

    let mut entree = String::new();
    io::stdin().read_line(&mut entree)
        .ok()
        .expect("Failed to read line");
    println!("You guessed: {}", entree);
    //entree contient la chaine non formatté.

    //> entree.split_whitespace() est directment un itérateur
    for element in entree.split_whitespace() {
        match element {
            "+" => {
                let nombre = pile.pop().expect("Empty pile!");
                let nombre2 = pile.pop().expect("Empty pile!");
                pile.push(nombre + nombre2);
            },
            "-" => {
                let nombre = pile.pop().expect("Empty pile!");
                let nombre2 = pile.pop().expect("Empty pile!");
                pile.push(-nombre + nombre2);
            },
            "*" => {
                let nombre = pile.pop().expect("Empty pile!");
                let nombre2 = pile.pop().expect("Empty pile!");
                pile.push(nombre*nombre2);
            },
            "/" => {
                let nombre = pile.pop().expect("Empty pile!");
                let nombre2 = pile.pop().expect("Empty pile!");
                pile.push(1./nombre*nombre2);
            },
            "^" => {
                let nombre = pile.pop().expect("Empty pile!");
                let nombre2 = pile.pop().expect("Empty pile!");
                pile.push(nombre2.powf(nombre));
            },
            _ => {
            //C'est alors un nombre.
                let nombre = element.trim().parse().ok().expect("Please type a number!");
                pile.push(nombre);
            }
        }
    }
    println!("Resutlat : {}", pile[0])
}

Et avec des fonctions et des types personnalisés :

 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
75
76
use std::io;

/// Operators and Numbers constitue an Expr
enum Expr {
    Plus,
    Minus,
    Times,
    Divide,
    Pow,
    Num(f64)
}

/// Parsing a string to get the corresponding Expr. Panic on failure
impl<'a> From<&'a str> for Expr {
    fn from(op: &'a str) -> Expr {
        match op {
            "+" => Expr::Plus,
            "-" => Expr::Minus,
            "*" => Expr::Times,
            "/" => Expr::Divide,
            "^" => Expr::Pow,
            val => {
                if let Ok(number) = val.trim().parse() {
                    Expr::Num(number)
                } else {
                    panic!("Could not parse {}", val);
                }
            }
        }
    }
}

/// Do the computation, panic on failure
fn compute(entry: &str) -> f64 {
    let mut stack: Vec<f64> = Vec::new();
    for token in entry.split_whitespace() {
        match Expr::from(token) {
            Expr::Plus => {
                let a = stack.pop().expect("Empty stack!");
                let b = stack.pop().expect("Empty stack!");
                stack.push(a + b);
            },
            Expr::Minus => {
                let a = stack.pop().expect("Empty stack!");
                let b = stack.pop().expect("Empty stack!");
                stack.push(-a + b);
            },
            Expr::Times => {
                let a = stack.pop().expect("Empty stack!");
                let b = stack.pop().expect("Empty stack!");
                stack.push(a*b);
            },
            Expr::Divide => {
                let a = stack.pop().expect("Empty stack!");
                let b = stack.pop().expect("Empty stack!");
                stack.push(b/a);
            },
            Expr::Pow => {
                let a = stack.pop().expect("Empty stack!");
                let b = stack.pop().expect("Empty stack!");
                stack.push(b.powf(a));
            },
            Expr::Num(number) => {
                stack.push(number);
            }
        }
    }
    assert!(stack.len() == 1);
    stack[0]
}

fn main() {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).ok().expect("Failed to read line");
    println!(" = {}", compute(&buffer));
}

Mon Github — Tuto Homebrew — Article Julia

+1 -0

Merci Luthaf. Fort heureusement, je ne fais pas de Fortran 77 (mais je connais effectivement plusieurs personnes qui codent encore avec aujourd'hui). Je regarderai précisément ton code quand j'aurai du temps pour (demain, il y a le Nobel de physique, je vais encore être un peu occupé :D ). Faudra que je revois Rust posément, et sans l'idée de faire concrètement un truc avec assez vite. Un peu comme si je faisais du Eiffel ou du Prolog. :) Mais effectivement, ça peut être intéressant, c'est juste nettement plus dure que ce que je pensais.

Il y a bien des façons de passer à l’acte. Se taire en est une. Attribué à Jean-Bertrand Pontalis

+0 -0

Cette réponse a aidé l’auteur du sujet

Voilà une version un peu plus typée que la précédente. Ce qu'il y a en plus :

  • Un GADT au lieu du type liste usuel d'OCaml
  • Le type obtenu est alors celui d'une pile hétérogène : un des exemples mélange booléens et entiers.
  • Grâce au GADT, certains cas de filtrage qui menaient à une exception dans le code précédent sont maintenant inutile. En plus du typage précis de la contenance de la liste, on a une information sur sa taille : plus précisément, il est immédiat de savoir si elle est vide (bottom stack) ou non (par exemple, si elle contient un entier en premier élément, (int * ...) stack). On a alors une vérification statique des programmes du petit langage à pile : un programme comme start push 1 pop pop finish sera rejeté dès la compilation, au lieu de lever une exception à l'exécution, parce que le pop n'est pas accepté depuis une pile vide.
  • Avec la liste hétérogène viennent des fonctions qui ont besoin, en haut de la pile, de valeurs d'un type particulier. Par exemple add veut deux entiers, and deux booléens, et gt dépile deux entiers mais empile un booléen. Le typage fort permet encore une fois de vérifier la correction de programmes comportant ces opérations à la compilation : un des exemples fournis est refusé à cause d'une telle erreur de type.
  • Le combinateur ( >> ) permet de définir de nouvelles opérations à partir d'opérations existant déjà. Il correspond moralement à une exécution successive de deux opérations. À titre d'exemple, l'opération id = dup >> pop duplique l'élément en tête de pile et dépile ce doublon, c'est donc la fonction identité (sur des piles à au moins un élément). Son implémentation est rigolote, parce qu'elle fait apparaître encore plus clairement le mécanisme des continuations.

    Je suppose qu'avec des GADT seulement, tu peux écrire des programmes comparables à tes x et y dont les types sont vérifiés par OCaml à la compilation. Ça revient à utiliser le système de types du langage hôte pour définir un DSL statiquement typé (par opposition à ton langage actuel qui est faiblement (ou "dynamiquement", blablabla) typé). C'est l'idée ?

C'est en partie l'idée. Avec les GADT, je dispose d'un typage plus expressif, qui me permet de refuser statiquement une classe de programmes qui, auparavant, auraient été acceptés : je pense aux programmes qui font des choses incorrectes en fonction de la taille de la pile, par exemple un pop sur une pile vide ou un programme qui ne termine pas sur une pile ne contenant qu'un élément. Mais il me permet aussi d'écrire des programmes que je ne pouvais pas écrire avec le code précédent, et je pense à ceux qui mélangent dans la pile des entiers et des booléens, grâce au type « liste hétérogène ». Ceci dit, ça aurait été aussi possible d'écrire ce genre de programmes sans GADT, probablement de plusieurs façons différente. Par exemple, avec un type elem = Bool of bool | Int of int, on aurait un typage dynamique, mais avec l'inconvénient supplémentaire qu'on est obligé de rajouter un constructeur pour chaque type de donnée qu'on veut mettre dans la pile. Je pense qu'il est aussi possible d'écrire les listes hétérogènes sans GADT, de façon un peu moins agréable à utiliser peut-être, en utilisant des couples. Le fait que je n'aie eu besoin d'écrire aucun type pour que l'inférence fonctionne me conforte dans cette idée que je n'avais peut-être pas besoin des GADT pour ça.

 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
type bottom

type _ stack =
  | Nil : bottom stack
  | Cons : 'a * 'b stack -> ('a * 'b) stack

let start k =
  k Nil

let push stack n k =
  k @@ Cons (n, stack)

let pop (Cons (_, xs)) k =
  k xs

let dup (Cons (x, xs)) k =
  k @@ Cons (x, Cons (x, xs))

let f_op ( <+> ) (Cons (x, Cons (y, zs))) k =
  k @@ Cons (y <+> x, zs)

let add stack = f_op ( + ) stack
let sub stack = f_op ( - ) stack
let mul stack = f_op ( * ) stack
let div stack = f_op ( / ) stack

let band stack = f_op ( && ) stack
let bor stack = f_op ( || ) stack

let gt stack = f_op ( > ) stack

let ifthenelse (Cons (b, Cons (x, Cons (y, zs)))) k =
  if b
  then k @@ Cons (x, zs)
  else k @@ Cons (y, zs)

let finish (Cons (x, Nil)) =
  x

let ( >> ) op1 op2 stack k =
  op1 stack (fun stack -> op2 stack k)

let id =
  dup >> pop

let x = start push 1 push 2 add push 3 dup pop add id finish

(* val x : int = 6 *)

let y =
  start
    push 9
    push 9
    add
    push 5
    push 4
    push 98
    mul
    div
    sub
    finish

(* val y : int = 18 *)

let z = (* if (3 > 0) && true then 1 else 2 *)
  start
    push 1
    push 2
    push true
    push 3
    push 0
    gt
    band
    ifthenelse
    finish

(* val z : int = 2 *)

(*
let _ =
  start
    push 1
    push true
    add
    finish

[...]
Type int is not compatible with type bool
*)

(*
let _ = start finish

[...]
Type 'a * bottom is not compatible with type bottom                                                                *)

Édité par Eusèbe

+0 -0

Cette réponse a aidé l’auteur du sujet

Le truc de Eusèbe en OCaml m'a bien fait marrer. Et puisque mon seul but dans la vie, c'est de montrer à quel point le Haskell est supérieur au OCaml, j'ai étendu l'idée de manière assez énorme puisque l'on peut écrire simplement1 quelque chose comme 1 2 (+) 3 (*). Le compilateur vérifiera alors le typage de l'expression, ce qui consiste, entre autre, à vérifier qu'il y a le bon nombre d'opérandes et d'opérateurs.

Enfin, ça c'est dans le monde des bisounours quand tout marche bien et que je suis un Dieu du Haskell. Dans la réalité véritable du monde réel, c'est bien moins beau. En effet, le typage est réalisé à l'aide d'un vecteur à taille statique (la taille est indiqué dans le type du vecteur) et la vérification se fait à l'aide d'instances de class récursives. Pour aider le compilateur à choisir la bonne instance à utiliser, il est cependant nécessaire de typer explicitement la fonction d'évaluation. Pour éviter ce genre de chose, on utilise habituellement des dépendances de types au niveau de la déclaration de classe. Cependant, il n'en existe pas ici.

Enfin, ça c'est ce que j'en ai conclu de mes expériences. Si quelqu'un arrive à trouver un moyen de ne pas avoir besoin de mettre autant d'informations de typage, je suis preneur.

Du coup, comme vous pouvez le voir à la fin, il faut indiquer explicitement le type de go pour que le compilateur accepte le programme. Le bon côté des choses, c'est que notre calculatrice est parfaitement générique : on peut manipuler des entiers avec les opérateurs associés, mais aussi des chaînes de caractères (toujours avec les opérateurs qui vont bien), des ensembles, …

Il serait probablement possible d'étendre la calculatrice pour permettre l'empilement d'éléments de différents types (en ayant donc une pile de type, toujours avec des class récursives), mais je me suis déjà assez tordu la tête pour arriver au résultat actuel. Ça sera pour une autre fois (si j'ai le temps).

 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
{-# Language FlexibleContexts, FlexibleInstances, MultiParamTypeClasses, GADTs, UndecidableInstances #-}

data Zero
data Succ n

type Bop a = a -> a -> a
type Uop a = a -> a

data Vec a n where
  Nil :: Vec a Zero
  Cons :: a -> Vec a n -> Vec a (Succ n)

class NPI a n r where
  go :: Vec a n -> r

instance NPI a (Succ Zero) a where
  go (Cons n Nil) = n

instance NPI a (Succ n) r => NPI a n (a -> r) where
  go v n = go $ Cons n v

instance NPI a n r => NPI a n (Uop a -> r) where
  go (Cons a v) op = go $ Cons (op a) v

instance NPI a n r => NPI a (Succ n) (Bop a -> r) where
  go (Cons a (Cons b v)) op = go $ Cons (op a b) v

main :: IO ()
main = do
  print a -- 9
  print b -- "Hello world!"
  print c -- 5.43656365691809
  where a = (go :: Vec Int Zero -> Int -> Int -> Bop Int -> Int -> Bop Int -> Int) Nil
          1 2 (+) 3 (*)
        b = (go :: Vec String Zero -> String -> String -> Bop String -> String) Nil
          "world!" "Hello " (++) -- le premier opérande est au sommet de la pile
        c = (go :: Vec Double Zero -> Double -> Uop Double -> Double -> Bop Double -> Double) Nil
          1 exp 2 (*)

Edit : je viens de voir le message précédent d'Eusèbe. Faudra que je vois si ce que j'ai fait ne peut pas se faire beaucoup plus simplement avec des GADTs (tout en évitant les mots-clés type push et en permettant toujours d'utiliser naturellement toutes les fonctions déjà existantes).


  1. sous réserve d'acceptation des CGU :-° , cf. la suite du message 

Édité par Berdes

+0 -0

Avec les GADT, je dispose d'un typage plus expressif, qui me permet de refuser statiquement une classe de programmes qui, auparavant, auraient été acceptés : je pense aux programmes qui font des choses incorrectes en fonction de la taille de la pile, par exemple un pop sur une pile vide ou un programme qui ne termine pas sur une pile ne contenant qu'un élément.

Comme quoi, ça fait du bien d'avoir des vraies garanties de sûreté.

mon seul but dans la vie, c'est de montrer à quel point le Haskell est supérieur au OCaml (…) Du coup, comme vous pouvez le voir à la fin, il faut indiquer explicitement le type de go pour que le compilateur accepte le programme.

Berdes

rofl.

Mais c'est rigolo quand même. Fais-nous signe si tu as mieux.

+3 -0

Cette réponse a aidé l’auteur du sujet

Yop !

Je me suis amusé à faire l'étape 1 en méta-programmation C++. Du coup, ça nous fait une calculatrice en notation polonaise inverse compilte-time (je rajouterais bien des static_assert pour rendre les erreurs de typage lisibles mais ce serait beaucoup trop simple à débugger donc il en est hors de question).

Bref, #HatersGonnaHate :

 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
//#include <iostream>
#include <cstddef>

template<class Current, std::size_t SIZE, class SubStack>
class stack{
  template<class T> using super_type          = stack<T, SIZE+1, stack>;
  template<class T, class Sub> using sub_type = stack<T, SIZE-1, Sub>;

public:
  template<class T, class SubSub>
  constexpr stack(Current value, sub_type<T,SubSub> s) : value(value), sub(s){}

  template<class T>
  constexpr auto push(T value) const{ return super_type<T>{ value, *this }; }
  constexpr auto top() const{ return value; }
  constexpr auto pop() const{ return sub; }

private:
  Current value;
  SubStack sub;
};

using empty_stack = stack<void,0,void>;

template<> class stack<void,0,void>{
  template<class T> using super_type = stack<T, 1, empty_stack>;
public:
  template<class T>
  constexpr auto push(T value) const{ return super_type<T>{ value, *this }; }
};

enum class OP{ ADD, SUB, MUL, DIV };

template<class ...Args>
constexpr auto eval(auto const s, auto d, Args ...args){
  return eval(s.push(d), args...);
}

template<class ...Args>
constexpr auto eval(auto const s, OP o, Args ...args){
  auto const d1 = s.top();
  auto const d2 = s.pop().top();

  auto new_s = s.pop().pop();
  switch(o){
  case OP::ADD: return eval(new_s.push(d2+d1), args...);
  case OP::SUB: return eval(new_s.push(d2-d1), args...);
  case OP::MUL: return eval(new_s.push(d2*d1), args...);
  case OP::DIV: return eval(new_s.push(d2/d1), args...);
  }
}

template<class T>
constexpr auto eval(stack<T, 1, empty_stack> const s){
  return s.top();
}

int main(){
  auto result = eval(empty_stack{}, 3, 4, OP::DIV, 2.5, OP::ADD);
  //std::cout<<result<<std::endl;

  auto other = eval(empty_stack{}, 9, 9, OP::ADD, 5, 4, 98, OP::MUL, OP::DIV, OP::SUB);
  //std::cout<<other<<std::endl;

  return result+other;
}

(Note : la constexpr eval contenant un switch, il faut avoir un compilo récent pour pouvoir compiler ce code. Sur un compilo plus vieux, il suffit a priori de virer le constexpr sur les deux premières eval pour pouvoir compiler).

(EDIT : quelques modifs pour assurer plus de choses au typage et pour la lecture).

Édité par Ksass`Peuk

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein [Tutoriel Frama-C WP]

+0 -0

En fait je pense qu'elle n'y est pas car Swift a été pensé pour créer des applis graphiques, pour Mac ou iBidule, donc pas besoin d'une fonction input() qui ne serait utilisable qu'en console. Ça va peut être changer vu que Swift va être portable vers Linux.

poliorcetics

La version 2.0 de Swift, sortie mi-septembre, dispose désormais de la fonction readLine() pour les entrées au clavier. Voir : https://developer.apple.com/library/mac/documentation/Swift/Reference/Swift_StandardLibrary_Functions/#//apple_ref/swift/func/s:FSs8readLineFT12stripNewlineSb_GSqSS_ ou de façon plus concise : http://swiftdoc.org/v2.0/func/readLine/.

quark67

Merci pour cette fonction, je ne la connaissais pas ! :)

Mais, après test, j'ai fait le choix de ne pas l'utiliser car elle ne permet pas ce que permet celle que j'utilise actuellement, c'est à dire un message pré-saisi qui s'affiche sans avoir besoin d'un print à l'extérieur de la fonction.

Qu’est ce qu’une fanfiction ? | Python & Swift | Léger Apple-Addict sur les bords.

+0 -0

Cette réponse a aidé l’auteur du sujet

Voici un code en TeX pour la notation NPI. Les macros du package apnum sont utilisées pour le calcul.

 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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
\input apnum % macros de calcul pour tex
\catcode`\_11
\edef\op_list{\detokenize{+-*/^}}
\def\cslet#1{\expandafter\let\csname#1\endcsname}
\def\gob_tok#1{}
\def\exec_first#1#2{#1}
\def\exec_second#1#2{#2}
\def\exp_arg#1#2{\expandafter#1\expandafter{#2}}
\def\push_stack#1{\edef\npi_stack{#1 \npi_stack}}
\def\pop_stack{\expandafter\pop_stack_a\npi_stack\relax}
\def\pop_stack_a#1 #2\relax#3{\def#3{#1}\def\npi_stack{#2}}
\def\if_empty#1{%
    \if\relax\detokenize{#1}\relax\expandafter\exec_first
    \else\expandafter\exec_second
    \fi
}
\def\ifstart#1#2{%
    \def\if_start##1#2##2\_nil{\if_empty{##1}}%
    \if_empty{#2}
        \exec_first
        {\if_start#1\relax#2\_nil}%
}
\def\if_number#1{%
    \ifstart{#1}-
        {\exp_arg\if_number{\gob_tok#1}%
        }
        {\if_empty{#1}%
            \exec_second
            {\afterassignment\if_number_a \count255 0#1\relax}%
        }%
}
\def\if_number_a#1\relax{%
    \if_empty{#1}
        \exec_first
        {\ifstart{#1}.
            {\afterassignment\if_number_b \count255 0\gob_tok#1\relax}
            \exec_second
        }%
}
\def\if_number_b#1\relax{\if_empty{#1}}
\def\if_operateur#1{%
    \expandafter\if_empty\expandafter{\gob_tok#1}
        {\exp_arg\if_operateur_a{\detokenize{#1}}}%
        {errsessage{Erreur}}%
}
\def\if_operateur_a#1{%
    \def\if_operateur_b##1#1##2\_nil{\if_empty{##2}\exec_second\exec_first}%
    \expandafter\if_operateur_b\op_list#1\_nil
}
\def\npi#1{%
    \begingroup
    \cslet+\PLUS \cslet-\MINUS \cslet*\MUL \cslet/\DIV \cslet^\POW
    \let\npi_stack\empty
    \edef\npi_list{\romannumeral-`\?#1}%
    \exp_arg\if_empty\npi_list
        {\errmessage{List empty!}}
        {\edef\npi_list{\detokenize\expandafter{\npi_list} \noexpand\parse_stop\space}%
        \expandafter\parse_list\npi_list
        }%
}
\def\parse_stop{\parse_stop}
\def\parse_list#1 {%
    \ifx\parse_stop#1%
        \expandafter\print_stack\expandafter\endgroup
    \else
        \if_number{#1}
            {\push_stack{#1}%
            }
            {\if_operateur{#1}
                {\pop_stack\numB\pop_stack\numA
                \csname#1\endcsname\numA\numB
                \exp_arg\push_stack\OUT
                }
                {\errmessage{Erreur}}
            }%
        \expandafter\parse_list
    \fi
}
\def\print_stack{\expandafter\printstack_a\npi_stack\_nil}
\def\printstack_a#1 #2\_nil{%
    \if_empty{#2}
        {#1}
        {\errmessage{Pile non unaire : \npi_stack}}%
}
\catcode`\_12
\npi{3 2 ^ 4 6 + *}% " 3^2 * (4 + 6)" donne 90

\npi{10 7 / 2 ^}% "(10 / 7) ^2" donne 2.0408163265306122448734693877551020408164

\npi{5 4 / 7 16 / - 2 3 ^ / 84.5 *}% "(5/4 - 7/16)/(2^3)*84.5" donne 8.58203125
\bye
+8 -0

Cette réponse a aidé l’auteur du sujet

Voici maintenant le niveau 2, toujours en TeX et avec les macros du package apnum.

La macro \infix admet le - unaire et ignore les espaces dans l'expression. Le code de la macro \parse_infix_expr est commenté, j'ai fait un effort !

Voici l'affichage que l'on peut voir dans le pdf ou le dvi généré :

1
2
3
4
5
6
7
3 2 ˆ 4 6 + * = 90
10 7 / 2 ˆ = 2.0408163265306122448734693877551020408164
5 4 / 7 16 / - 2 3 ˆ / 84.5 * = 8.58203125
2*(3-4)+5ˆ-1 = -1.8
10-(9-(8-7))*2 = -6
-3.14-5.4*-6.5+2.3ˆ4 = 59.9441
0.123-.456*(0.0007-1.111)ˆ2 = -.43914133704

Et le code :

  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
\input apnum % macros de calcul pour tex
\edef\restorecatcode{\catcode\number`\_=\number\catcode`\_\relax}
\catcode`\_11
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% Macros auxiliaires %%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcount\_integer
\edef\op_list{\detokenize{ +:2L -:2L *:3L /:3L ^:4R}}% liste des opérateurs
\def\let_cs#1{\expandafter\let\csname#1\endcsname}
\def\gob_tok#1{}
\def\return_firsttok#1#2\return_firsttok{#1}
\def\exec_first#1#2{#1}
\def\exec_second#1#2{#2}
\def\exp_arg#1#2{\expandafter#1\expandafter{#2}}
\def\swap_arg#1#2{#2{#1}}
\def\exp_second#1#2{\exp_arg\swap_arg{#2}{#1}}
\def\exp_twoargs#1#2#3{\exp_second{\exp_arg#1{#2}}{#3}}
\def\push_onstack#1{\edef\_stack{#1 \_stack}}
\def\pop_fromstack#1{%
  \def\pop_fromstack_a##1 ##2\pop_fromstack_a{\def#1{##1}\def\_stack{##2}}%
  \expandafter\pop_fromstack_a\_stack\pop_fromstack_a
}
\def\peek_fromstack#1{%
  \def\peek_fromstack_a##1 ##2\peek_fromstack_a{\def#1{##1}}%
  \expandafter\peek_fromstack_a\_stack\peek_fromstack_a
}
\def\push_onqueue#1{\edef\infix_out_queue{\infix_out_queue#1 }}
\def\if_empty#1{%
  \if\relax\detokenize{#1}\relax
      \expandafter\exec_first
  \else
      \expandafter\exec_second
  \fi
}
\def\ifstring_start#1#2{% la chaine #1 commence-t-elle par le motif #2 ?
  \def\ifstring_start_a##1#2##2\ifstring_start_a{\if_empty{##1}}%
  \ifstring_start_a#1\relax#2\ifstring_start_a%
}
\def\ifstring_contains#1#2{% la chaine #1 contient-elle le motif #2 ?
  \def\ifstring_contains_a##1#2##2\ifstring_contains_a{\if_empty{##2}\exec_second\exec_first}%
  \ifstring_contains_a#1\relax#2\ifstring_contains_a
}
\def\if_op#1{\exp_twoargs\ifstring_contains\op_list{\detokenize{ #1:}}}
\def\parse_stop{\parse_stop}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%% Macros de nombres  %%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% ------ macro \read_digits -------
\def\read_digits#1#2#3{% lit le max de chiffres dans #1, les met dans la macro #2 et met ce qui reste dans la macro #3
  \let#2\empty \def#3{#1}%
  \if_empty{#1}
      {%
      }
      {% si argument non vide
          \let\collect_digits\empty% collecteur vide
          \read_digits_a#1\parse_stop#3% parser #1
          \let#2\collect_digits% #2:=collecteur
      }%
}
\def\read_digits_a#1{% lit un caractère
  \ifx\parse_stop#1\expandafter\exec_first\else\expandafter\exec_second\fi
      {% fin atteinte ?
          \collect_remaining\parse_stop% ne rien récupérer comme reste
      }
      {% si la fin n'est pas atteinte
          \ifstring_contains{0123456789}{#1}% et si le caractère est un chiffre
              {%
                  \edef\collect_digits{\collect_digits#1}% l'ajouter au collecteur
                  \read_digits_a% lire le caractère suivant
              }
              {% si le caractère n'est pas un chiffre,
                  \collect_remaining#1% récupérer ce qui reste (en rajoutant #1 qui a déjà été lu)
              }%
      }%
}
\def\collect_remaining#1\parse_stop#2{\def#2{#1}}

% ------ macro \read_number -------
% lit un <nombre> au début de #1
%    un <nombre entier>  est <- optionnel><chiffres>
%    un <nombre décimal> est <- optionnel><chiffres optionnels><. optionnel><chiffres optionnels>
%    sous réserve que
%        1) si le séparateur décimal "." est présent, il ait des <chiffres optionnels> au moins d'un coté
%        2) le <signe - optionnel> n'est permis que si le booléen \if_possible_negative est vrai
% le nombre au début de #1 est renvoyé dans la macro #2 et ce qui reste dans la macro #3
% #2 sera vide si #1 ne commence pas par des caractères pouvant former un <nombre>
\newif\if_nointpart
\def\read_number#1#2#3{%
  \def\setmacro_if_fail{\let#2\empty\def#3{#1}}% renvoie vide et #1 (si échec)
  \setmacro_if_fail
  \_nointpartfalse
  \ifstring_start{#1}-
      {% si #1 commence par "-"
          \if_possible_negative\expandafter\exec_first\else\expandafter\exec_second\fi
              {% et un négatif est autorisé
                  \def#2{-}\edef#3{\gob_tok#1}%
                  \exp_arg\read_number_intpart#3#2#3% on poursuit et on lit la partie entière
              }
              {%
              }%
      }
      {%
          \read_number_intpart{#1}#2#3%
      }%
}
\def\read_number_intpart#1#2#3{% #1 est purgé d'un éventuel <- optionnel>
  \ifstring_start{#1}.
      {% pas de partie décimale avant le "." ?
          \_nointparttrue% s'en souvenir...
          \read_number_intpart{0#1}#2#3% et recommencer avec 0 en début de #1
      }
      {%
          \read_digits{#1}\digits_collected\_remaining% lire des chiffres au début de #1
          \exp_arg\if_empty\digits_collected
              {% aucun chiffre lu ?
                  \setmacro_if_fail% macro renvoyée nulle, on s'arrête ici
              }
              {% des chiffres lus ?
                  \edef#2{#2\digits_collected}% les rajouter à la macro renvoyée
                  \exp_arg\read_number_decpart\_remaining#2#3% on poursuit avec ce qui reste pour lire la partie décimale
              }%
      }%
}
\def\read_number_decpart#1#2#3{% on a lu la partie entière dans #1
  \ifstring_start{#1}.
      {% un "." au début : il y a une partie décimale
          \exp_arg\read_digits{\gob_tok#1}\digits_collected\_remaining% manger le "." et lire des chiffres au début de #1
          \exp_arg\if_empty\digits_collected
              {% si aucun chiffre dans la partie décimale
                  \if_nointpart% et qu'il n'y en avait aucun dans la partie entière
                      \setmacro_if_fail% on renvoie vide -> nombre non légal
                  \else% SUCCES : #1 commence par un <nombre>
                      \edef#2{#2.0}% si partie entière : rajouter un "0" en partie décimale
                      \edef#3{\gob_tok#1}% reste : #1 sans le .
                  \fi
              }
              {% si des chiffres sont en partie décimale. SUCCES : #1 commence par un <nombre>
                  \edef#2{#2.\digits_collected}% les rajouter dans la macro
                  \let#3\_remaining
              }%
      }
      {% pas de partie décimale, on s'arrête mais SUCCES : #1 commence par un <nombre>
          \def#3{#1}% reste
      }%
}
\def\if_number#1{%
  \begingroup
      \_possible_negativetrue
      \read_number{#1}\__\_remaining
      \expandafter
  \endgroup
  \expandafter\if_empty\expandafter{\_remaining}%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  Macro \npi  %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\npi{%
  \def\print_input{\detokenize\expandafter{\npi_list} = }%
  \npi_a
}
\def\npi_a#1{%
  \begingroup
      \let_cs+\PLUS \let_cs-\MINUS \let_cs*\MUL \let_cs/\DIV \let_cs^\POW
      \let\_stack\empty
      \edef\npi_list{\romannumeral-`\?#1}%
      \exp_arg\if_empty\npi_list
          {%
              \errmessage{Liste d'instructions vide!}%
          }
          {%
              \print_input% à commenter pour n'avoir que le résultat à l'affichage
              \edef\npi_list{\detokenize\expandafter{\npi_list} \noexpand\parse_stop\space}%
              \expandafter\parse_list\npi_list
          }%
}
\def\parse_list#1 {%
  \ifx\parse_stop#1\expandafter\exec_first\else\expandafter\exec_second\fi
      {%
          \print_stack\endgroup
      }
      {%
          \if_number{#1}
              {%
                  \push_onstack{#1}%
              }
              {%
                  \if_op{#1}
                      {%
                          \pop_fromstack\numB
                          \pop_fromstack\numA
                          \csname#1\endcsname\numA\numB
                          \push_onstack\OUT
                      }
                      {%
                          \errmessage{Erreur de syntaxe dans "#1"}%
                      }%
              }%
          \parse_list
      }%
}
\def\print_stack{\expandafter\print_stack_a\_stack\print_stack_a}
\def\print_stack_a#1 #2\print_stack_a{%
  \if_empty{#2}
      {%
          #1%
      }
      {%
          \errmessage{Pile non unaire : \_stack}%
      }%
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%% Macro \infix %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newif\if_possible_negative
\newif\if_start_withnumber
\def\tokenize_infix_expr{%
  \exp_arg\if_empty\infix_expr
      {%
      }
      {% s'il reste des caractères à tokéniser
      \exp_arg\read_number\infix_expr\return_number\infix_expr% lire un <nombre> au début de \infix_expr
      \exp_arg\if_empty\return_number% si aucun nombre n'est lu
          {% ajouter le 1er caractère+" " à l'expression tokénisée
              \edef\infix_expr_tokenized{\infix_expr_tokenized\expandafter\return_firsttok\infix_expr\return_firsttok\space}%
              \edef\infix_expr{\expandafter\gob_tok\infix_expr}% et le supprimer de ce qui reste à lire
              \_possible_negativetrue% autoriser un négatif
          }
          {% si un nombre est lu, l'ajouter +" " à l'expression tokénisée
              \edef\infix_expr_tokenized{\infix_expr_tokenized\return_number\space}%
              \_possible_negativefalse% interdire un négatif après un nombre
          }%
      \tokenize_infix_expr% continuer la tokénisation
      }%
}
\newif\iftopstack_isop
\def\test_item#1{% teste l'item #1
  \if_op{#1}% si l'item est un opérateur
      {%
          \topstack_isoptrue
          \test_op{#1}\top_op_priority\top_op_associativity
      }
      {%
      }%
}
\def\test_op#1#2#3{%
  \def\test_op_a##1 #1:##2##3##4\test_op_a{\def#2{##2}\def#3{##3}}%
  \expandafter\test_op_a\op_list\test_op_a
}
\def\test_topstack#1{%
  \topstack_isopfalse
  \exp_arg\if_empty{#1}
      {%
      }
      {%
          \peek_fromstack\item_topstack
          \exp_arg\test_item\item_topstack
      }%
}
\def\remove_lastspace#1{%
  \def\remove_lastspace_a##1 \remove_lastspace_a{\def#1{##1}}%
  \expandafter\remove_lastspace_a#1\remove_lastspace_a
}
\def\infix{%
  \begingroup
      \catcode 32 9 % espace ignoré
      \infix_a
}
\def\infix_a#1{% espaces ignorés
  \endgroup
  \if_empty{#1}
      {%
          \errmessage{Expression vide !}%
      }
      {%
      }%
  \let\infix_out_queue\empty
  \let\_stack\empty
  \edef\infix_expr{\detokenize{#1}}%
  \infix_expr\space= % à commenter pour n'avoir que le résultat à l'affichage
  \let\infix_expr_tokenized\empty
  \_possible_negativetrue% en début d'expression infixe : nombre négatif permis
  \tokenize_infix_expr% tokénizer l'expresion infixe
  \edef\infix_expr_tokenized{\infix_expr_tokenized\relax\space}% rajouter un \relax+espace à la fin
  \edef\open_paren{\string(}\edef\close_paren{\string)}%
  \expandafter\parse_infix_expr\infix_expr_tokenized
}
\def\parse_infix_expr#1 {% lit un token
  \ifx#1\relax\expandafter\exec_first\else\expandafter\exec_second\fi
      {% s'il n'y a plus de tokens à lire
          \loop% tant que
              \unless\ifx\_stack\empty% la pile d'op n'est pas vide...
                  \pop_fromstack\top_itemstack% dépiler l'élément du haut de pile
                  \ifx\top_itemstack\open_paren\errmessage{Mauvais appariement entre ( et )}\fi
                  \push_onqueue\top_itemstack% et le mettre sur la file de sortie
          \repeat
          \remove_lastspace\infix_out_queue% enlève l'espace de fin
          \let\print_input\empty% neutralise l'affichage de l'entrée npi
          \exp_arg\npi_a\infix_out_queue% évalue la queue de sortie, en notation npi
      }
      {% tant qu'on n'est pas à la fin de l'expression infixe tokénizée
      \if_number{#1}
          {% si le token #1 est un nombre
          \push_onqueue{#1}% le mettre sur la queue de sortie
          }
          {% si le token n'est pas un nombre
              \if_op{#1}
                  {% si le token est un opérateur op1
                      \loop%  BOUCLER
                          \_integer=0 % entier qui fera ou pas continuer la boucle (pour l'instant 0, càd : non)
                          \test_topstack\_stack% teste le sommet de la pile infixe
                          \iftopstack_isop% s'il y a un opérateur op2, \top_op_priority et \top_op_associativity sont affectées
                              \test_op{#1}\current_op_priority\current_op_associativity% trouve la priorité et associativité de op1
                              \advance\_integer% augmenter \_integer de 1 si 
                                  \numexpr\if L\current_op_associativity1\else0\fi% asso(op1)==L
                                          *% et
                                          \ifnum\current_op_priority>\top_op_priority\space0\else1\fi% prio(op1)<=prio(op2)
                                          +% ou
                                          \if R\current_op_associativity1\else0\fi% asso(op1)==R
                                          *% et
                                          \ifnum\current_op_priority<\top_op_priority\space1\else0\fi% prio(op1)<prio(op2)
                                  \relax
                          \fi
                          \ifnum\_integer>0 % exécuter le corps de la boucle (et répéter plus loin) tant que \_integer>0
                              \pop_fromstack\stacked_op% dépiler op2
                              \push_onqueue\stacked_op% l'enfiler sur file de sortie
                      \repeat% FIN BOUCLE
                      \push_onstack{#1}% empiler op1 sur la pile d'op
                  }
                  {% si le token n'est pas un opérateur
                      \def\current_token{#1}%
                      \ifx\current_token\open_paren\expandafter\exec_first\else\expandafter\exec_second\fi
                          {% si le token lu est une parenthèse ouvrante
                              \push_onstack{#1}% empiler "(" sur la pile d'op
                          }
                          {% si le token n'est pas "("
                              \ifx\current_token\close_paren\expandafter\exec_first\else\expandafter\exec_second\fi
                                  {% si le token lu est ")"
                                      \loop% Répéter...
                                          \ifx\_stack\empty\errmessage{Mauvais appariement entre ( et )}\fi
                                          \peek_fromstack\top_itemstack% prendre l'item en haut de la pile
                                          \unless\ifx\top_itemstack\open_paren% si ce n'est pas "("
                                              \pop_fromstack\top_itemstack% dépiler l'élément du haut de pile
                                              \push_onqueue\top_itemstack% et le mettre sur la file de sortie
                                      \repeat
                                      \pop_fromstack\top_itemstack% dépiler l'élément du haut de pile, qui est "("
                                  }
                                  {%
                                      \errmessage{Erreur de syntaxe dans "#1"}%
                                  }%
                          }%
                  }%
              }%
          \parse_infix_expr% lire le token suivant
      }%
}

\restorecatcode% fin préambule
\npi{3 2 ^ 4 6 + *}% "3^2 * (4 + 6)" donne 90

\npi{10 7 / 2 ^}% "(10 / 7) ^2" donne 2.0408163265306122448734693877551020408164

\npi{5 4 / 7 16 / - 2 3 ^ / 84.5 *}% "(5/4 - 7/16)/(2^3)*84.5" donne 8.58203125

\infix{2*(3-4)+5^-1}% donne -1.8

\infix{10- (9- (8-7) ) *2}% donne -6

\infix{-3.14 - 5.4*-6.5 + 2.3^4}% donne 59.941

\infix{0.123-.456*(0.0007-1.111)^2}% donne -.43914133704
\bye

Edit : ré-écriture de la macro \read_number qui faisait n'importe quoi et était trop limitée.

Édité par ct

+2 -0

Cette réponse a aidé l’auteur du sujet

Un exemple du niveau 2 toujours en C.

  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
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <string.h>

#define MAX_ENTRY 255

#define setToken(_token, _type, s_type, _value)\
    _token.type = _type;\
    _token.data_val.s_type = _value;

double add(double a, double b)
{
    return a+b;
}

double sub(double a, double b)
{
    return b-a;
}

double time(double a, double b)
{
    return a*b;
}

double div_(double a, double b)
{
    return b/a;
}

enum {NONE = 0, OPERATOR, NUMBER};
enum {A_NONE = 0, A_LEFT, A_RIGHT};

struct Operators
{
    char op;
    int precedence;
    int associativity;
    double (*callback)(double, double);
} operators[]=
{
    {'+', 2, A_LEFT, add},
    {'-', 2, A_LEFT, sub},
    {'*', 3, A_LEFT, time},
    {'/', 3, A_LEFT, div_},
    {'^', 4, A_RIGHT, pow}
};

typedef struct pile
{
    char op;
    struct pile *prev;
} Pile;

typedef struct result_pile
{
    double data;
    struct result_pile *prev;
} Result_pile;

union Data_type
{
    int op;
    double data;
};

typedef struct Token
{
    int type;
    union Data_type data_val;
} Token;

typedef struct File
{
    Token token;
    struct File *next;
} File;

void pile_push(Pile **pile, char op)
{
    Pile *tmp = malloc(sizeof(*tmp));

    if(!tmp) exit(EXIT_FAILURE);

    tmp->op = op;
    tmp->prev = *pile;

    *pile = tmp;
}

char pile_pop(Pile **pile)
{
    if(*pile == NULL)
        return -1;

    Pile *tmp = (*pile)->prev;
    char op = (*pile)->op;

    free(*pile), *pile = NULL;
    *pile = tmp;

    return op;
}

int pile_size(Pile *pile)
{
    Pile *tmp = pile;
    int size = 0;

    while(tmp)
    {
        size++;
        tmp = tmp->prev;
    }

    return size;
}

void rpile_push(Result_pile **pile, double data)
{
    Result_pile *tmp = malloc(sizeof(*tmp));

    if(!tmp) exit(EXIT_FAILURE);

    tmp->data = data;
    tmp->prev = *pile;

    *pile = tmp;
}

double rpile_pop(Result_pile **pile)
{
    if(*pile == NULL)
        return -1;

    Result_pile *tmp = (*pile)->prev;
    double data = (*pile)->data;

    free(*pile), *pile = NULL;
    *pile = tmp;

    return data;
}

void file_enqueue(File **file, Token token)
{
    File *tmp = malloc(sizeof(*tmp));

    if(!tmp) exit(EXIT_FAILURE);

    tmp->token = token;
    tmp->next = NULL;

    if(!*file) *file = tmp;

    else
    {
        File *tmp2 = *file;
        while(tmp2->next)
        {
            tmp2 = tmp2->next;
        }
        tmp2->next = tmp;
    }
}

Token file_dequeue(File **file)
{
    Token token;

    if(!*file) exit(EXIT_FAILURE);
    File *tmp = (*file)->next;
    token = (*file)->token;

    free(*file), *file = NULL;
    *file = tmp;

    return token;
}

int getOperatorID(char operator_)
{
    for(int i = 0; i < 5; i++)
    {
        if(operator_ == operators[i].op)
            return i;
    }
    return -1;
}

unsigned int isAnOperator(char c)
{
    return (c == '*' || c == '-' || c == '/' || c == '+' || c == '^');
}

unsigned int isFloat(char c)
{
    return (isdigit(c) || c == '.');
}

void eval_expr(char *str, File **f, Pile **p)
{
    char buffer[MAX_ENTRY] = "";
    Token token;

    int numberSaved = 0;
    int op_queued = 0;
    int p_size = 0;

    for(unsigned i = 0, j = 0; str[i] != '\0'; i++)
    {
        if(isAnOperator(str[i]))
        {
            p_size = pile_size(*p);

            while(p_size--)
            {
                char p_op = pile_pop(p);
                int p_opId = getOperatorID(p_op);
                int s_opId = getOperatorID(str[i]);

                if((operators[s_opId].associativity == A_LEFT &&
                        operators[s_opId].precedence <= operators[p_opId].precedence) ||
                        (operators[s_opId].associativity == A_RIGHT &&
                         operators[s_opId].precedence < operators[p_opId].precedence))
                {
                    setToken(token, OPERATOR, op, p_opId);
                    file_enqueue(f, token);
                    op_queued = 1;
                }

                if(!op_queued) pile_push(p, p_op);

                op_queued = 0;
            }
            pile_push(p, str[i]);
        }
        else if(str[i] == '(')
        {
            pile_push(p, str[i]);
        }
        else if(str[i] == ')')
        {
            char p_op;
            while((p_op = pile_pop(p)) != '(')
            {
                if(isAnOperator(p_op))
                {
                    setToken(token, OPERATOR, op, getOperatorID(p_op));
                    file_enqueue(f, token);
                }
            }
        }

        else if(isFloat(str[i]))
        {
            buffer[j] = str[i];
            j++;
            numberSaved = 0;
        }

        else if(isblank(str[i]) || (i == strlen(str) - 1))
        {
            if(!numberSaved && j > 0)
            {
                setToken(token, NUMBER, data, atof(buffer));
                file_enqueue(f, token);
                memset(buffer, '\0', j);
                j = 0;
                numberSaved = 1;
            }
        }
    }

    p_size = pile_size(*p);
    while(p_size--)
    {
        char p_op = pile_pop(p);
        if(isAnOperator(p_op))
        {
            setToken(token, OPERATOR, op, getOperatorID(p_op));
            file_enqueue(f, token);
        }
    }

}

void print_file(File *f)
{
    File *tmp = f;

    while(tmp != NULL)
    {
        if(tmp->token.type == OPERATOR)
        {
            printf("%c ", operators[tmp->token.data_val.op].op);
        }
        else if(tmp->token.type == NUMBER)
        {
            printf("%f ", tmp->token.data_val.data);
        }
        else puts("dafuq!");

        tmp = tmp->next;
    }
}

double eval_file(File **f)
{
    double a, b;
    double result;
    Result_pile *r_pile = NULL;
    Token token;

    while(*f != NULL)
    {
        token = file_dequeue(f);
        if(token.type == OPERATOR)
        {
            a = rpile_pop(&r_pile);
            b = rpile_pop(&r_pile);
            result = operators[token.data_val.op].callback(a,b);
            rpile_push(&r_pile, result);
        }
        else if(token.type == NUMBER)
        {
            rpile_push(&r_pile, token.data_val.data);
        }
    }

   return r_pile->data;
}

int main(void)
{
    Pile *p_pile = NULL;
    File *p_file = NULL;

    char entry[MAX_ENTRY] = "";
    //double result = 0;

    fgets(entry, sizeof(entry), stdin);
    eval_expr(entry, &p_file, &p_pile);

    puts("\nEn Notation Polonaise Inverse: ");
    print_file(p_file);

    printf("\n\nResultat = %f\n", eval_file(&p_file));

    return 0;
}

+1 -0

Cette réponse a aidé l’auteur du sujet

Hop, le niveau 2 se trouve ici : https://github.com/SpaceFox/calculator/tree/Niveau2/src/info/kisai/zds/calculator

Je vous mets la fonction de tokenisation, qui fonctionne mais que je trouve trop compliquée :

 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
    private List<Token> tokenize(String in) {

        StringBuilder buffer = new StringBuilder();
        List<Token> out = new LinkedList<>();
        char[] chars = in.toCharArray();

        Type previousType = null, type;
        boolean isSpaceChar;
        for (char c : chars) {

            type = null;
            isSpaceChar = Character.isSpaceChar(c);
            if (Token.TYPE_DISCRIMINANTS.containsKey(c)) {
                type = Token.TYPE_DISCRIMINANTS.get(c);
            } else if (!isSpaceChar) {
                type = Type.FUNCTION;
            }
            if (previousType == Type.NEGATIVE_OR_OPERATOR) {
                final Token lastToken = out.get(out.size() - 1);
                // Supposition : on a pas 2 nombres à la suite. Permet d'interpréter les formes comme "1-1".
                if (type != Type.NUMBER || (lastToken != null && lastToken.getType() == Type.NUMBER)) {
                    out.add(new Token(Type.OPERATOR, "-"));
                    buffer = new StringBuilder();
                }
            }
            if (    previousType != null
                &&  previousType != Type.NEGATIVE_OR_OPERATOR
                && (isSpaceChar || type != previousType)
            ) {
                out.add(new Token(previousType, buffer.toString()));
                buffer = new StringBuilder();
            }
            previousType = type;
            if (!isSpaceChar) {
                buffer.append(c);
            }
        }
        out.add(new Token(previousType, buffer.toString()));
        return out;
    }

Et la fonction de transformation en notation RPN :

 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
    private String shuntingYard(String in) throws ParenthesisMismatchException {

        List<Token> tokens = tokenize(in);

        final Queue<Token> queue = new LinkedList<>();
        final Deque<Token> stack = new LinkedList<>();

        for (Token token : tokens) {
            switch (token.getType()) {
                case NUMBER:
                    queue.add(token);
                    break;
                case FUNCTION:
                    stack.push(token);
                    break;
                case FUNCTION_ARG_SEPARATOR:
                    while (stack.getFirst().getType() != Type.OPEN_PARENTHESIS) {
                        queue.add(stack.pop());
                    }
                    break;
                case OPERATOR:
                    final Operator o1 = RPNCalculator.OPERATORS.get(token.getValue());
                    Operator o2 = stack.isEmpty() ? null : RPNCalculator.OPERATORS.get(stack.getFirst().getValue());
                    while ( o2 != null
                        &&  (   (o1.isLeftAssociative()   && o1.getPrecedence() <= o2.getPrecedence())
                            ||  (!o1.isLeftAssociative()  && o1.getPrecedence() < o2.getPrecedence())
                        )
                    ) {
                        queue.add(stack.pop());
                        o2 = stack.isEmpty() ? null : RPNCalculator.OPERATORS.get(stack.getFirst().getValue());
                    }
                    stack.push(token);
                    break;
                case OPEN_PARENTHESIS:
                    stack.push(token);
                    break;
                case CLOSE_PARENTHESIS:
                    while (stack.getFirst().getType() != Type.OPEN_PARENTHESIS) {
                        queue.add(stack.pop());
                    }
                    stack.pop();
                    if (stack.getFirst().getType() == Type.FUNCTION) {
                        queue.add(stack.pop());
                    }
                    break;
            }
        }
        while (!stack.isEmpty()) {
            if (stack.getFirst().getType() == Type.OPEN_PARENTHESIS) {
                throw new ParenthesisMismatchException(in);
            }
            queue.add(stack.pop());
        }

        // On pourrait directement construire le buffer sans utiliser la queue, mais c'est plus simple à déboguer
        StringBuilder buffer = new StringBuilder();
        for (Token token : queue) {
            buffer.append(token.getValue()).append(" ");
        }

        return buffer.toString();
    }

Notez que si ces 2 méthodes gèrent les fonctions, ce n'est pas encore le cas du moteur de calcul RPN.

Cette réponse a aidé l’auteur du sujet

Juste pour le fun, le niveau 1 en SWI-Prolog :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
npi([Nb | Tl], Stack, R) :-
    number(Nb), !,
    npi(Tl, [Nb | Stack], R).
npi([Op | Tl], [A, B | Stack], R) :-
    Expr =.. [Op, B, A],
    Val is Expr,
    npi(Tl, [Val | Stack], R).
npi([], [R], R).

npi(L, R) :- npi(L, [], R).

Ensuite, au shell :

1
2
3
4
5
?- npi([1,2,+,4,*,3,+], R).
R = 15.

?- npi([1,2,3,+,*], R).
R = 5.
+4 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

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