source: cpp/frams/genetics/fL/fL_matheval.h @ 1006

Last change on this file since 1006 was 797, checked in by Maciej Komosinski, 6 years ago

A more complete implementation of fB, fH, fL

File size: 9.3 KB
Line 
1// This file is a part of Framsticks SDK.  http://www.framsticks.com/
2// Copyright (C) 1999-2018  Maciej Komosinski and Szymon Ulatowski.
3// See LICENSE.txt for details.
4
5#ifndef _FL_MATHEVAL_H_
6#define _FL_MATHEVAL_H_
7
8#include <string>
9#include <unordered_map>
10#include <list>
11#include <vector>
12
13#define VARIABLEPREFIX '$'
14
15#define MATH_MUT_DELETION   0
16#define MATH_MUT_CHANGEVAL  1
17#define MATH_MUT_CHANGEOPER 2
18#define MATH_MUT_INSERTION  3
19#define MATH_MUT_COUNT      4
20
21#define MAX_MUT_FORMULA_SIZE 7
22#define XOVER_MAX_MIGRATED_RULES 3
23
24/** @name Available operators for MathEvaluation */
25//@{
26double madd(double left, double right); ///<add
27double msub(double left, double right); ///<subtract
28double mmul(double left, double right); ///<multiply
29double mand(double left, double right); ///<and
30double mor(double left, double right); ///<or
31double mgreater(double left, double right); ///<greater than
32double mless(double left, double right); ///<less than
33double mequal(double left, double right); ///<equal to
34double mnotequal(double left, double right); ///<not equal to
35double meqless(double left, double right); ///<less or equal
36double meqgreater(double left, double right); ///<greater or equal
37//@}
38
39/**
40 * Class for performing simple mathematical parsing and evaluations of expressions
41 * stored in strings. At first, the class object converts given string into list
42 * of objects that can be described as Reverse Polish Notation, or suffix notation.
43 * From this notation object can efficiently perform calculations for different
44 * values of variables, without re-tokenizing of a string.
45 */
46class MathEvaluation
47{
48        /// determines to whih class token belongs
49        enum TokenType {
50                NUMBER, ///<Number token
51                PARENTHESIS, ///<Parenthesis token
52                OPERATOR,  ///<Operator token
53                VARIABLE ///<Variable token
54        };
55        /// associativity of operator
56        enum Associativity {
57                RIGHT,
58                LEFT
59        };
60        /// determines if parenthesis is opening of closing
61        enum ParenthesisType {
62                OPEN,
63                CLOSE
64        };
65
66        /**
67         * Simplest token of MathEvaluation Reverse Polish Notation. Every class used
68         * in RPN notation should inherit from this class.
69         */
70        class Token
71        {
72        public:
73                TokenType type; ///<type of token
74                /**
75                 * Method is used during converting list of token objects into infix
76                 * notation. Every class should implement this method and provide useful
77                 * and valid information for infix notation.
78                 * @return stringified token
79                 */
80                virtual std::string toString() = 0;
81                Token(TokenType type) : type(type) {}
82                virtual ~Token() {}
83        };
84
85        /**
86         * Describes all numbers available in object infix notation.
87         */
88        class Number : public Token
89        {
90        public:
91                double value; ///<value of stored number
92                Number(double value) : Token(TokenType::NUMBER), value(value)
93                { }
94                ~Number() {}
95                std::string toString();
96                /**
97                 * Copies value field from given source.
98                 * @param src other Number object
99                 */
100                void operator=(const Number& src);
101        };
102
103        /**
104         * Special type of Number object, which holds external variables, represented
105         * as $id, where id is a number.
106         */
107        class Variable : public Number
108        {
109        public:
110                int id; ///<id of Variable object. Object is accessed via $id
111                Variable(int id) : Number(0), id(id)
112                {
113                        type = TokenType::VARIABLE;
114                }
115                ~Variable() {}
116                std::string toString();
117        };
118
119        /**
120         * Class describing operator in RPN objects. It holds informations about
121         * precedence, associativity and symbol of the operator. Operator can have 1
122         * or 2 characters, not more or less. Operator requires function that takes
123         * two doubles and returns double value -- the result of this function is the
124         * result of operator execution.
125         */
126        class Operator : public Token
127        {
128                double(*operation)(double left, double right); ///<field holding pointer to operator function
129        public:
130                int precedence; ///<precedence of the operator
131                Associativity assoc; ///<associativity of the operator
132                std::string opname; ///<symbol of the operator, can have 1 or 2 characters
133
134                /**
135                 * Uses method pointed by 'operation' pointer to return operator result
136                 * for a given numbers.
137                 * @param left number on the left side of the operator
138                 * @param right number on the right side of the operator
139                 * @return operator result
140                 */
141                double execute(double left, double right);
142
143                Operator(double(*operation)(double left, double right), int precedence,
144                        Associativity assoc, std::string opname) :
145                        Token(TokenType::OPERATOR),
146                        operation(operation),
147                        precedence(precedence),
148                        assoc(assoc),
149                        opname(opname)
150                { }
151                ~Operator() {}
152                std::string toString();
153        };
154
155        /**
156         * Class represents parenthesis token. Parenthesis are considered only during
157         * creation of RPN notation - the notation itself does not contain any
158         * parenthesis, because the order of calculation is determined directly by
159         * operators and numbers order.
160         */
161        class Parenthesis : public Token
162        {
163        public:
164                ParenthesisType ptype; ///<determines if parenthesis is open or closed
165                Parenthesis(ParenthesisType ptype) :
166                        Token(TokenType::PARENTHESIS),
167                        ptype(ptype)
168                { }
169                ~Parenthesis() { }
170                std::string toString();
171        };
172
173        /**
174         * Clears postfix objects stored in MathEvaluation object.
175         */
176        void clearPostfix();
177
178        /**
179         * Registers operators available in MathEvaluation object. Default operators
180         * are +, -, *, &, |, >, <, >=, <=, =, ~, where ~ is inequality.
181         * Registered operators can have maximally two characters, otherwise they are
182         * ignored.
183         */
184        void registerOperators();
185
186        std::string originalexpression;
187        std::unordered_map<std::string, Operator *> operators; ///<map containing available operators for MathEvaluation
188        std::list<Token *> postfixlist; ///<list with tokens ordered as postfix (RPN) notation of the given string
189        int varcount; ///<amount of variables declared for this MathEvaluation object
190        std::vector<Variable *> vars; ///<vector of variables, default values are 0
191        Variable *t; ///<additional t variable, that can act as time for evaluation
192        std::vector<std::string> operatorstrings; ///<list of registered operators
193        int arithmeticoperatorscount; ///<count of arithmetic operators
194        int comparisonoperatorscount;
195public:
196
197        /**
198         * Default constructor. It registers operators for MathEvaluation and prepares
199         * vector of variables.
200         */
201        MathEvaluation(int varcount);
202
203        /**
204         * Destructor is responsible for clearing all objects in postfix, all operator
205         * objects and all variables.
206         */
207        ~MathEvaluation();
208
209        /**
210         * Converts string to std::list of tokens in postfix order that can be later
211         * evaluated. Detailed description of algorithm can be found in source of
212         * method.
213         * @param expression infix mathematical expression
214         * @return 0 if conversion is successful, or -1 if an error occurred
215         */
216        int convertString(std::string expression);
217
218        /**
219         * Evaluates expression stored in postfix list. It takes into account changes
220         * made by modifyVariable method. This method should be called if the only
221         * thing changed in expression are variable values - it saves time because
222         * it uses objects created during convertString or evaluate method.
223         * @param res reference to the variable, in which result will be stored
224         * @return 0 if evaluation went successful, or -1 if an error occurred
225         */
226        int evaluateRPN(double &res);
227
228        /**
229         * Performs convertString and evaluateRPN methods respectively. It holds
230         * objects created by convertString method.
231         * @param expression infix mathematical expression
232         * @param result reference to the variable, in which result will be stored
233         * @return 0 if evaluation went successful, otherwise it returns the error of previous functions
234         */
235        int evaluate(std::string expression, double &result);
236
237        /**
238         * Sets variable with index i with value val.
239         * @param i id of variable, -1 if changed variable should be variable 't' (time)
240         * @param val new value
241         */
242        void modifyVariable(int i, double val);
243
244        /**
245         * Registers new operator for MathEvaluation object.
246         * @param operation function that needs to be called during evaluation
247         * @param precedence precedence of operator
248         * @param assoc associativity of the operator
249         * @param opsymbol symbol of the operator
250         */
251        void registerOperator(double(*operation)(double left, double right), int precedence, MathEvaluation::Associativity assoc, std::string opsymbol);
252
253        /**
254         * Converts stored RPN list to infix string.
255         * @param result reference to variable that will hold the result
256         * @return 0 if method went successful, or -1 if an error occurred
257         */
258        int RPNToInfix(std::string &result);
259
260        /**
261         * Mutates formula.
262         * @param logical if true, method uses logical operators only
263         * @param usetime if true, method may use time variable during mutation
264         * @param 0 if mutation could be performed, -1 if postfixlist is empty
265         */
266        int mutate(bool logical, bool usetime);
267
268        /**
269         * Mutates formula so it creates conjuctive of comparisons.
270         */
271        void mutateConditional();
272
273        /**
274         * Mutates number by using random value or one of variables.
275         * @param currval current value of number
276         * @param usetime if true, then time variable may be used
277         */
278        void mutateValueOrVariable(Number *&currval, bool usetime);
279
280        /**
281         * Returns formula in RPN notation
282         * @param RPN notation string
283         */
284        std::string getStringifiedRPN();
285
286        /**
287         * Returns random operator available in object.
288         * @param type 0 for all operators, 1 for arithmetic only, 2 for logical only
289         * @return pointer to random operator
290         */
291        Operator* getRandomOperator(int type);
292};
293
294#endif // _FL_MATHEVAL_H_
Note: See TracBrowser for help on using the repository browser.