Subversion Repositories Scribus

Rev

Rev 8495 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
4078 fschmid 1
  Function parser for C++  v2.8 by Warp.
2
  =====================================
161 Franz 3
 
4
  Optimization code contributed by Bisqwit (http://iki.fi/bisqwit/)
5
 
6
 
7
  The usage license of this library is located at the end of this text file.
8
 
9
 
10
 
4078 fschmid 11
  What's new in v2.8
12
  ------------------
13
  - Put the compile-time options to a separate file fpconfig.hh.
14
  - Added comparison operators "!=", "<=" and ">=".
15
  - Added an epsilon value to the comparison operators (its value can be
16
    changed in fpconfig.hh or it can be completely disabled there).
17
  - Added unary not operator "!".
18
  - Now user-defined functions can take 0 parameters.
19
  - Added a maximum recursion level to the "eval()" function (definable in
20
    (fpconfig.hh). Now "eval()" should never cause an infinite recursion.
21
    (Note however, that it may still be relevant to disable it completely
22
    because it is possible to write functions which take enormous amounts
23
    of time to evaluate even when the maximum recursion level is not reached.)
24
  - Separated the optimizer code to its own file (makes developement easier).
161 Franz 25
 
26
 
27
 
28
=============================================================================
29
  - Preface
30
=============================================================================
31
 
32
  Often people need to ask some mathematical expression from the user and
33
then evaluate values for that expression. The simplest example is a program
34
which draws the graphic of a user-defined function on screen.
35
 
36
  This library adds C-style function string parsing to the program. This
37
means that you can evaluate the string "sqrt(1-x^2+y^2)" with given values
38
of 'x' and 'y'.
39
 
40
  The library is intended to be very fast. It byte-compiles the function
41
string at parse time and interpretes this byte-code at evaluation time.
42
The evaluation is straightforward and no recursions are done (uses stack
43
arithmetic).
44
  Empirical tests show that it indeed is very fast (specially compared to
45
libraries which evaluate functions by just interpreting the raw function
46
string).
47
 
48
  The library is made in ISO C++ and requires a standard-conforming C++
49
compiler.
50
 
51
 
52
=============================================================================
53
  - Usage
54
=============================================================================
55
 
4078 fschmid 56
  To use the FunctionParser class, you have to include "fparser.hh" in
57
your source code files which use the FunctionParser class.
161 Franz 58
 
4078 fschmid 59
  When compiling, you have to compile fparser.cc and fpoptimizer.cc and
60
link them to the main program. In some developement environments it's
61
enough to add those two files to your current project.
161 Franz 62
 
4078 fschmid 63
  If you are not going to use the optimizer (ie. you have commented out
64
SUPPORT_OPTIMIZER in fpconfig.hh), you can leave the latter file out.
161 Franz 65
 
66
 
4078 fschmid 67
  * Configuring the compilation:
68
    ---------------------------
69
 
70
    There is a set of precompiler options in the fpconfig.hh file
71
  which can be used for setting certain features on or off:
72
 
161 Franz 73
  NO_ASINH : (Default on)
74
       By default the library does not support the asinh(), acosh()
75
       and atanh() functions because they are not part of the ISO C++
76
       standard. If your compiler supports them and you want the
4078 fschmid 77
       parser to support them as well, comment out this line.
161 Franz 78
 
79
  DISABLE_EVAL : (Default off)
4078 fschmid 80
       Even though the maximum recursion level of the eval() function
81
       is limited, it is still possible to write functions which never
82
       reach this maximum recursion level but take enormous amounts of
83
       time to evaluate (this can be undesirable eg. in web server-side
84
       applications).
85
       Uncommenting this line will disable the eval() function completely,
86
       thus removing the danger of exploitation.
161 Franz 87
 
4078 fschmid 88
       Note that you can also disable eval() by specifying the
89
       DISABLE_EVAL precompiler constant in your compiler (eg.
90
       with -DDISABLE_EVAL in gcc).
91
 
92
  EVAL_MAX_REC_LEVEL : (Default 1000)
93
       Sets the maximum recursion level allowed for eval().
94
 
161 Franz 95
  SUPPORT_OPTIMIZER : (Default on)
96
       If you are not going to use the Optimize() method, you can comment
97
       this line out to speed-up the compilation of fparser.cc a bit, as
98
       well as making the binary a bit smaller. (Optimize() can still be
99
       called, but it will not do anything.)
100
 
4078 fschmid 101
       You can also disable the optimizer by specifying the
102
       NO_SUPPORT_OPTIMIZER precompiler constant in your compiler
103
       (eg. with -DNO_SUPPORT_OPTIMIZER in gcc).
161 Franz 104
 
4078 fschmid 105
  FP_EPSILON : (Default 1e-14)
106
       Epsilon value used in comparison operators.
107
       If this line is commented out, then no epsilon will be used.
108
 
109
 
161 Franz 110
  * Copying and assignment:
111
    ----------------------
112
 
113
    The class implements a safe copy constructor and assignment operator.
114
 
115
    It uses the copy-on-write technique for efficiency. This means that
116
  when copying or assigning a FunctionParser instance, the internal data
117
  (which in some cases can be quite lengthy) is not immediately copied
118
  but only when the contents of the copy (or the original) are changed.
119
    This means that copying/assigning is a very fast operation, and if
120
  the copies are never modified then actual data copying never happens
121
  either.
122
 
123
    The Eval() and EvalError() methods of the copy can be called without
124
  the internal data being copied.
125
    Calling Parse(), Optimize() or the user-defined constant/function adding
126
  methods will cause a deep-copy.
127
 
128
    (C++ basics: The copy constructor is called when a new FunctionParser
129
     instance is initialized with another, ie. like:
130
 
131
       FunctionParser fp2 = fp1; // or: FunctionParser fp2(fp1);
132
 
133
     or when a function takes a FunctionParser instance as parameter, eg:
134
 
135
       void foo(FunctionParser p) // takes an instance of FunctionParser
136
       { ... }
137
 
138
     The assignment operator is called when a FunctionParser instance is
139
     assigned to another, like "fp2 = fp1;".)
140
 
141
 
142
  * Short descriptions of FunctionParser methods:
143
    --------------------------------------------
144
 
145
int Parse(const std::string& Function, const std::string& Vars,
146
          bool useDegrees = false);
147
 
148
    Parses the given function and compiles it to internal format.
149
    Return value is -1 if successful, else the index value to the location
150
    of the error.
151
 
152
 
153
const char* ErrorMsg(void) const;
154
 
155
    Returns an error message corresponding to the error in Parse(), or 0 if
156
    no such error occurred.
157
 
158
 
159
ParseErrorType GetParseErrorType() const;
160
 
161
    Returns the type of parsing error which occurred. Possible return types
162
    are described in the long description.
163
 
164
 
165
double Eval(const double* Vars);
166
 
167
    Evaluates the function given to Parse().
168
 
169
 
170
int EvalError(void) const;
171
 
172
    Returns 0 if no error happened in the previous call to Eval(), else an
173
    error code >0.
174
 
175
 
176
void Optimize();
177
 
178
    Tries to optimize the bytecode for faster evaluation.
179
 
180
 
181
bool AddConstant(const std::string& name, double value);
182
 
183
    Add a constant to the parser. Returns false if the name of the constant
184
    is invalid, else true.
185
 
186
 
187
bool AddFunction(const std::string& name,
188
                 double (*functionPtr)(const double*),
189
                 unsigned paramsAmount);
190
 
191
    Add a user-defined function to the parser (as a function pointer).
192
    Returns false if the name of the function is invalid, else true.
193
 
194
 
195
bool AddFunction(const std::string& name, FunctionParser&);
196
 
197
    Add a user-defined function to the parser (as a FunctionParser instance).
198
    Returns false if the name of the function is invalid, else true.
199
 
200
 
201
 
202
  * Long descriptions of FunctionParser methods:
203
    -------------------------------------------
204
 
205
---------------------------------------------------------------------------
206
int Parse(const std::string& Function, const std::string& Vars,
207
          bool useDegrees = false);
208
---------------------------------------------------------------------------
209
 
210
      Parses the given function (and compiles it to internal format).
211
    Destroys previous function. Following calls to Eval() will evaluate
212
    the given function.
213
      The strings given as parameters are not needed anymore after parsing.
214
 
215
    Parameters:
216
      Function  : String containing the function to parse.
217
      Vars      : String containing the variable names, separated by commas.
218
                  Eg. "x,y", "VarX,VarY,VarZ,n" or "x1,x2,x3,x4,__VAR__".
219
      useDegrees: (Optional.) Whether to use degrees or radians in
220
                  trigonometric functions. (Default: radians)
221
 
222
    Variables can have any size and they are case sensitive (ie. "var",
223
    "VAR" and "Var" are *different* variable names). Letters, digits and
224
    underscores can be used in variable names, but the name of a variable
225
    can't begin with a digit. Each variable name can appear only once in
4078 fschmid 226
    the 'Vars' string. Function names are not legal variable names.
161 Franz 227
 
228
    Using longer variable names causes no overhead whatsoever to the Eval()
229
    method, so it's completely safe to use variable names of any size.
230
 
231
    The third, optional parameter specifies whether angles should be
232
    interpreted as radians or degrees in trigonometrical functions.
233
    If not specified, the default value is radians.
234
 
235
    Return values:
236
    -On success the function returns -1.
237
    -On error the function returns an index to where the error was found
238
     (0 is the first character, 1 the second, etc). If the error was not
239
     a parsing error returns an index to the end of the string + 1.
240
 
241
    Example: parser.Parse("3*x+y", "x,y");
242
 
243
 
244
---------------------------------------------------------------------------
245
const char* ErrorMsg(void) const;
246
---------------------------------------------------------------------------
247
 
248
    Returns a pointer to an error message string corresponding to the error
249
    caused by Parse() (you can use this to print the proper error message to
250
    the user). If no such error has occurred, returns 0.
251
 
252
 
253
---------------------------------------------------------------------------
254
ParseErrorType GetParseErrorType() const;
255
---------------------------------------------------------------------------
256
 
257
    Returns the type of parse error which occurred.
258
 
259
    This method can be used to get the error type if ErrorMsg() is not
260
    enough for printing the error message. In other words, this can be
261
    used for printing customized error messages (eg. in another language).
262
    If the default error messages suffice, then this method doesn't need
263
    to be called.
264
 
265
    FunctionParser::ParseErrorType is an enumerated type inside the class
266
    (ie. its values are accessed like "FunctionParser::SYNTAX_ERROR").
267
 
268
    The possible values for FunctionParser::ParseErrorType are listed below,
269
    along with their equivalent error message returned by the ErrorMsg()
270
    method:
271
 
272
FP_NO_ERROR        : If no error occurred in the previous call to Parse().
273
SYNTAX_ERROR       : "Syntax error"
274
MISM_PARENTH       : "Mismatched parenthesis"
275
MISSING_PARENTH    : "Missing ')'"
276
EMPTY_PARENTH      : "Empty parentheses"
277
EXPECT_OPERATOR    : "Syntax error: Operator expected"
278
OUT_OF_MEMORY      : "Not enough memory"
4078 fschmid 279
UNEXPECTED_ERROR   : "An unexpected error occurred. Please make a full bug "
280
                     "report to the author"
161 Franz 281
INVALID_VARS       : "Syntax error in parameter 'Vars' given to "
282
                     "FunctionParser::Parse()"
283
ILL_PARAMS_AMOUNT  : "Illegal number of parameters to function"
284
PREMATURE_EOS      : "Syntax error: Premature end of string"
285
EXPECT_PARENTH_FUNC: "Syntax error: Expecting ( after function"
286
 
287
 
288
---------------------------------------------------------------------------
289
double Eval(const double* Vars);
290
---------------------------------------------------------------------------
291
 
292
    Evaluates the function given to Parse().
293
    The array given as parameter must contain the same amount of values as
294
    the amount of variables given to Parse(). Each value corresponds to each
295
    variable, in the same order.
296
 
297
    Return values:
298
    -On success returns the evaluated value of the function given to
299
     Parse().
300
    -On error (such as division by 0) the return value is unspecified,
301
     probably 0.
302
 
303
    Example:
304
 
305
      double Vars[] = {1, -2.5};
306
      double result = parser.Eval(Vars);
307
 
308
 
309
---------------------------------------------------------------------------
310
int EvalError(void) const;
311
---------------------------------------------------------------------------
312
 
313
    Used to test if the call to Eval() succeeded.
314
 
315
    Return values:
316
      If there was no error in the previous call to Eval(), returns 0,
317
      else returns a positive value as follows:
318
        1: division by zero
319
        2: sqrt error (sqrt of a negative value)
320
        3: log error (logarithm of a negative value)
321
        4: trigonometric error (asin or acos of illegal value)
4078 fschmid 322
        5: maximum recursion level in eval() reached
161 Franz 323
 
324
 
325
---------------------------------------------------------------------------
326
void Optimize();
327
---------------------------------------------------------------------------
328
 
329
    This method can be called after calling the Parse() method. It will try
330
    to simplify the internal bytecode so that it will evaluate faster (it
331
    tries to reduce the amount of opcodes in the bytecode).
332
 
333
      For example, the bytecode for the function "5+x*y-25*4/8" will be
334
    reduced to a bytecode equivalent to the function "x*y-7.5" (the original
335
    11 opcodes will be reduced to 5). Besides calculating constant expressions
336
    (like in the example), it also performs other types of simplifications
337
    with variable and function expressions.
338
 
339
      This method is quite slow and the decision of whether to use it or
340
    not should depend on the type of application. If a function is parsed
341
    once and evaluated millions of times, then calling Optimize() may speed-up
342
    noticeably. However, if there are tons of functions to parse and each one
343
    is evaluated once or just a few times, then calling Optimize() will only
344
    slow down the program.
345
      Also, if the original function is expected to be optimal, then calling
346
    Optimize() would be useless.
347
 
348
      Note: Currently this method does not make any checks (like Eval() does)
349
    and thus things like "1/0" will cause undefined behaviour. (On the other
350
    hand, if such expression is given to the parser, Eval() will always give
351
    an error code, no matter what the parameters.) If caching this type of
352
    errors is important, a work-around is to call Eval() once before calling
353
    Optimize() and checking EvalError().
354
 
355
      If the destination application is not going to use this method,
4078 fschmid 356
    the compiler constant SUPPORT_OPTIMIZER can be undefined in fpconfig.hh
357
    to make the library smaller (Optimize() can still be called, but it will
358
    not do anything).
161 Franz 359
 
360
    (If you are interested in seeing how this method optimizes the opcode,
361
    you can call the PrintByteCode() method before and after the call to
362
    Optimize() to see the difference.)
363
 
364
 
365
---------------------------------------------------------------------------
366
bool AddConstant(const std::string& name, double value);
367
---------------------------------------------------------------------------
368
 
369
    This method can be used to add constants to the parser. Syntactically
370
    constants are identical to variables (ie. they follow the same naming
371
    rules and they can be used in the function string in the same way as
372
    variables), but internally constants are directly replaced with their
373
    value at parse time.
374
 
375
      Constants used by a function must be added before calling Parse()
376
    for that function. Constants are preserved between Parse() calls in
377
    the current FunctionParser instance, so they don't need to be added
378
    but once. (If you use the same constant in several instances of
379
    FunctionParser, you will need to add it to all the instances separately.)
380
 
381
      Constants can be added at any time and the value of old constants can
382
    be changed, but new additions and changes will only have effect the next
383
    time Parse() is called. (That is, changing the value of a constant
384
    after calling Parse() and before calling Eval() will have no effect.)
385
 
386
      The return value will be false if the 'name' of the constant was
387
    illegal, else true. If the name was illegal, the method does nothing.
388
 
4078 fschmid 389
    Example: parser.AddConstant("pi", 3.1415926535897932);
161 Franz 390
 
391
    Now for example parser.Parse("x*pi", "x"); will be identical to the
4078 fschmid 392
    call parser.Parse("x*3.1415926535897932", "x");
161 Franz 393
 
394
 
395
---------------------------------------------------------------------------
396
bool AddFunction(const std::string& name,
397
                 double (*functionPtr)(const double*),
398
                 unsigned paramsAmount);
399
---------------------------------------------------------------------------
400
 
401
    This method can be used to add new functions to the parser. For example,
402
    if you would like to add a function "sqr(A)" which squares the value
403
    of A, you can do it with this method (so that you don't need to touch
404
    the source code of the parser).
405
 
406
      The method takes three parameters:
407
 
408
    - The name of the function. The name follows the same naming conventions
409
      as variable names.
410
 
411
    - A C++ function, which will be called when evaluating the function
412
      string (if the user-given function is called there). The C++ function
413
      must have the form:
414
          double functionName(const double* params);
415
 
4078 fschmid 416
    - The number of parameters the function takes. 0 is a valid value
417
      in which case the function takes no parameters (such function
418
      should simply ignore the double* it gets as a parameter).
161 Franz 419
 
420
    The return value will be false if the given name was invalid (either it
421
    did not follow the variable naming conventions, or the name was already
422
    reserved), else true. If the return value is false, nothing is added.
423
 
424
    Example:
425
    Suppose we have a C++ function like this:
426
 
427
    double Square(const double* p)
428
    {
429
        return p[0]*p[0];
430
    }
431
 
432
    Now we can add this function to the parser like this:
433
 
434
    parser.AddFunction("sqr", Square, 1);
435
 
436
    parser.Parse("2*sqr(x)", "x");
437
 
438
 
4078 fschmid 439
    An example of a useful function taking no parameters is a function
440
    returning a random value. For example:
441
 
442
    double Rand(const double*)
443
    {
444
        return drand48();
445
    }
446
 
447
    parser.AddFunction("rand", Rand, 0);
448
 
449
 
161 Franz 450
    IMPORTANT NOTE: If you use the Optimize() method, it will assume that
451
    the user-given function has no side-effects, that is, it always
452
    returns the same value for the same parameters. The optimizer will
453
    optimize the function call away in some cases, making this assumption.
4078 fschmid 454
    (The Rand() function given as example above is one such problematic case.)
161 Franz 455
 
456
 
457
---------------------------------------------------------------------------
458
bool AddFunction(const std::string& name, FunctionParser&);
459
---------------------------------------------------------------------------
460
 
461
    This method is almost identical to the previous AddFunction(), but
462
    instead of taking a C++ function, it takes another FunctionParser
463
    instance.
464
 
465
    There are some important restrictions on making a FunctionParser instance
466
    call another:
467
 
468
    - The FunctionParser instance given as parameter must be initialized
469
      with a Parse() call before giving it as parameter. That is, if you
470
      want to use the parser A in the parser B, you must call A.Parse()
471
      before you can call B.AddFunction("name", A).
472
 
4078 fschmid 473
    - The amount of variables in the FunctionParser instance given as
161 Franz 474
      parameter must not change after it has been given to the AddFunction()
4078 fschmid 475
      of another instance. Changing the number of variables will result in
161 Franz 476
      malfunction.
477
 
478
    - AddFunction() will fail (ie. return false) if a recursive loop is
479
      formed. The method specifically checks that no such loop is built.
480
 
481
    Example:
482
 
483
    FunctionParser f1, f2;
484
    f1.Parse("x*x", "x");
485
    f2.AddFunction("sqr", f1);
486
 
4078 fschmid 487
    This version of the AddFunction() method can be useful to eg. chain
488
    user-given functions. For example, ask the user for a function F1,
489
    and then ask the user another function F2, but now the user can
490
    call F1 in this second function if he wants (and so on with a third
491
    function F3, where he can call F1 and F2, etc).
161 Franz 492
 
493
 
494
 
495
 
496
=============================================================================
497
  - The function string
498
=============================================================================
499
 
500
  The function string understood by the class is very similar to the C-syntax.
501
  Arithmetic float expressions can be created from float literals, variables
502
or functions using the following operators in this order of precedence:
503
 
504
   ()             expressions in parentheses first
4078 fschmid 505
   A^B            exponentiation (A raised to the power B)
161 Franz 506
   -A             unary minus
4078 fschmid 507
   !A             unary logical not (result is 1 if int(A) is 0, else 0)
161 Franz 508
   A*B  A/B  A%B  multiplication, division and modulo
509
   A+B  A-B       addition and subtraction
4078 fschmid 510
   A=B  A!=B  A<B  A<=B  A>B  A>=B
511
                  comparison between A and B (result is either 0 or 1)
512
   A&B            result is 1 if int(A) and int(B) differ from 0, else 0
513
   A|B            result is 1 if int(A) or int(B) differ from 0, else 0
161 Franz 514
 
515
    Since the unary minus has higher precedence than any other operator, for
516
  example the following expression is valid: x*-y
517
 
4078 fschmid 518
    The comparison operators use an epsilon value, so expressions which may
519
  differ in very least-significant digits should work correctly. For example,
520
  "0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1+0.1 = 1" should always return 1, and
521
  the same comparison done with ">" or "<" should always return 0.
522
  (The epsilon value can be configured in the fpconfig.hh file.)
523
  Without epsilon this comparison probably returns the wrong value.
524
 
161 Franz 525
  The class supports these functions:
526
 
527
  abs(A)    : Absolute value of A. If A is negative, returns -A otherwise
528
              returns A.
529
  acos(A)   : Arc-cosine of A. Returns the angle, measured in radians,
530
              whose cosine is A.
531
  acosh(A)  : Same as acos() but for hyperbolic cosine.
532
  asin(A)   : Arc-sine of A. Returns the angle, measured in radians, whose
533
              sine is A.
534
  asinh(A)  : Same as asin() but for hyperbolic sine.
535
  atan(A)   : Arc-tangent of (A). Returns the angle, measured in radians,
536
              whose tangent is (A).
537
  atan2(A,B): Arc-tangent of A/B. The two main differences to atan() is
538
              that it will return the right angle depending on the signs of
539
              A and B (atan() can only return values betwen -pi/2 and pi/2),
540
              and that the return value of pi/2 and -pi/2 are possible.
541
  atanh(A)  : Same as atan() but for hyperbolic tangent.
542
  ceil(A)   : Ceiling of A. Returns the smallest integer greater than A.
543
              Rounds up to the next higher integer.
544
  cos(A)    : Cosine of A. Returns the cosine of the angle A, where A is
545
              measured in radians.
546
  cosh(A)   : Same as cos() but for hyperbolic cosine.
547
  cot(A)    : Cotangent of A (equivalent to 1/tan(A)).
548
  csc(A)    : Cosecant of A (equivalent to 1/sin(A)).
549
  eval(...) : This a recursive call to the function to be evaluated. The
550
              number of parameters must be the same as the number of parameters
4078 fschmid 551
              taken by the function. Must be called inside if() to avoid
161 Franz 552
              infinite recursion.
553
  exp(A)    : Exponential of A. Returns the value of e raised to the power
554
              A where e is the base of the natural logarithm, i.e. the
555
              non-repeating value approximately equal to 2.71828182846.
556
  floor(A)  : Floor of A. Returns the largest integer less than A. Rounds
557
              down to the next lower integer.
558
  if(A,B,C) : If int(A) differs from 0, the return value of this function is B,
559
              else C. Only the parameter which needs to be evaluated is
560
              evaluated, the other parameter is skipped; this makes it safe to
561
              use eval() in them.
562
  int(A)    : Rounds A to the closest integer. 0.5 is rounded to 1.
563
  log(A)    : Natural (base e) logarithm of A.
564
  log10(A)  : Base 10 logarithm of A.
565
  max(A,B)  : If A>B, the result is A, else B.
566
  min(A,B)  : If A<B, the result is A, else B.
567
  sec(A)    : Secant of A (equivalent to 1/cos(A)).
568
  sin(A)    : Sine of A. Returns the sine of the angle A, where A is
569
              measured in radians.
570
  sinh(A)   : Same as sin() but for hyperbolic sine.
571
  sqrt(A)   : Square root of A. Returns the value whose square is A.
572
  tan(A)    : Tangent of A. Returns the tangent of the angle A, where A
573
              is measured in radians.
574
  tanh(A)   : Same as tan() but for hyperbolic tangent.
575
 
576
 
577
  Examples of function string understood by the class:
578
 
579
  "1+2"
580
  "x-1"
581
  "-sin(sqrt(x^2+y^2))"
582
  "sqrt(XCoord*XCoord + YCoord*YCoord)"
583
 
584
  An example of a recursive function is the factorial function:
585
 
586
  "if(n>1, n*eval(n-1), 1)"
587
 
588
  Note that a recursive call has some overhead, which makes it a bit slower
589
  than any other operation. It may be a good idea to avoid recursive functions
590
  in very time-critical applications. Recursion also takes some memory, so
591
  extremely deep recursions should be avoided (eg. millions of nested recursive
592
  calls).
593
 
4078 fschmid 594
  Also note that even though the maximum recursion level of eval() is
595
  limited, it is possible to write functions which never reach that level
596
  but still take enormous amounts of time to evaluate.
597
  This can sometimes be undesirable because it is prone to exploitation,
598
  but you can disable the eval() function completely in the fpconfig.hh file.
161 Franz 599
 
600
 
4078 fschmid 601
 
161 Franz 602
=============================================================================
603
  - Contacting the author
604
=============================================================================
605
 
606
  Any comments, bug reports, etc. should be sent to warp@iki.fi
607
 
608
 
609
=============================================================================
610
  - The algorithm used in the library
611
=============================================================================
612
 
613
  The whole idea behind the algorithm is to convert the regular infix
614
format (the regular syntax for mathematical operations in most languages,
615
like C and the input of the library) to postfix format. The postfix format
616
is also called stack arithmetic since an expression in postfix format
617
can be evaluated using a stack and operating with the top of the stack.
618
 
619
  For example:
620
 
621
  infix    postfix
622
  2+3      2 3 +
623
  1+2+3    1 2 + 3 +
624
  5*2+8/2  5 2 * 8 2 / +
625
  (5+9)*3  5 9 + 3 *
626
 
627
  The postfix notation should be read in this way:
628
 
629
  Let's take for example the expression: 5 2 * 8 2 / +
630
  - Put 5 on the stack
631
  - Put 2 on the stack
632
  - Multiply the two values on the top of the stack and put the result on
633
    the stack (removing the two old values)
634
  - Put 8 on the stack
635
  - Put 2 on the stack
636
  - Divide the two values on the top of the stack
637
  - Add the two values on the top of the stack (which are in this case
638
    the result of 5*2 and 8/2, that is, 10 and 4).
639
 
640
  At the end there's only one value in the stack, and that value is the
641
result of the expression.
642
 
643
  Why stack arithmetic?
644
 
645
  The last example above can give you a hint.
646
  In infix format operators have precedence and we have to use parentheses to
647
group operations with lower precedence to be calculated before operations
648
with higher precedence.
649
  This causes a problem when evaluating an infix expression, specially
650
when converting it to byte code. For example in this kind of expression:
651
    (x+1)/(y+2)
652
we have to calculate first the two additions before we can calculate the
653
division. We have to also keep counting parentheses, since there can be
654
a countless amount of nested parentheses. This usually means that you
655
have to do some type of recursion.
656
 
657
  The most simple and efficient way of calculating this is to convert it
658
to postfix notation.
659
  The postfix notation has the advantage that you can make all operations
660
in a straightforward way. You just evaluate the expression from left to
661
right, applying each operation directly and that's it. There are no
662
parentheses to worry about. You don't need recursion anywhere.
663
  You have to keep a stack, of course, but that's extremely easily done.
664
Also you just operate with the top of the stack, which makes it very easy.
665
You never have to go deeper than 2 items in the stack.
666
  And even better: Evaluating an expression in postfix format is never
667
slower than in infix format. All the contrary, in many cases it's a lot
668
faster (eg. because all parentheses are optimized away).
669
  The above example could be expressed in postfix format:
670
    x 1 + y 2 + /
671
 
672
  The good thing about the postfix notation is also the fact that it can
673
be extremely easily expressed in bytecode form.
674
  You only need a byte value for each operation, for each variable and
675
to push a constant to the stack.
676
  Then you can interpret this bytecode straightforwardly. You just interpret
677
it byte by byte, from the beginning to the end. You never have to go back,
678
make loops or anything.
679
 
680
  This is what makes byte-coded stack arithmetic so fast.
681
 
682
 
683
 
684
=============================================================================
685
  Usage license:
686
=============================================================================
687
 
4078 fschmid 688
Copyright © 2003-2005 Juha Nieminen, Joel Yliluoma
161 Franz 689
 
690
  This library is distributed under two distinct usage licenses depending
691
on the software ("Software" below) which uses the Function Parser library
692
("Library" below).
693
  The reason for having two distinct usage licenses is to make the library
694
compatible with the GPL license while still being usable in other non-GPL
695
(even commercial) software.
696
 
697
A) If the Software using the Library is distributed under the GPL license,
698
   then the Library can be used under the GPL license as well.
699
 
700
   The Library will be under the GPL license only when used with the
701
   Software. If the Library is separated from the Software and used in
702
   another different software under a different license, then the Library
703
   will have the B) license below.
704
 
705
   Exception to the above: If the Library is modified for the GPL Software,
706
   then the Library cannot be used with the B) license without the express
707
   permission of the author of the modifications. A modified library will
708
   be under the GPL license by default. That is, only the original,
709
   unmodified version of the Library can be taken to another software
710
   with the B) license below.
711
 
712
   The author of the Software should provide an URL to the original
713
   version of the Library if the one used in the Software has been
714
   modified. (http://iki.fi/warp/FunctionParser/)
715
 
716
   This text file must be distributed in its original intact form along
717
   with the sources of the Library. (Documentation about possible
718
   modifications to the library should be put in a different text file.)
719
 
720
B) If the Software using the Library is not distributed under the GPL
721
   license but under any other license, then the following usage license
722
   applies to the Library:
723
 
724
  1. This library is free for non-commercial usage. You can do whatever you
725
     like with it as long as you don't claim you made it yourself.
726
 
727
  2. It is possible to use this library in a commercial program, but in this
728
     case you MUST contact me first (warp@iki.fi) and ask express permission
729
     for this. (Read explanation at the end of the file.)
730
       If you are making a free program or a shareware program with just a
731
     nominal price (5 US dollars or less), you don't have to ask for
732
     permission.
733
       In any case, I DON'T WANT MONEY for the usage of this library. It is
734
     free, period.
735
 
736
  3. You can make any modifications you want to it so that it conforms your
737
     needs. If you make modifications to it, you have, of course, credits for
738
     the modified parts.
739
 
740
  4. If you use this library in your own program, you don't have to provide
741
     the source code if you don't want to (ie. the source code of your program
742
     or this library).
743
       If you DO include the source code for this library, this text file
744
     must be included in its original intact form.
745
 
746
  5. If you distribute a program which uses this library, and specially if you
747
     provide the source code, proper credits MUST be included. Trying to
748
     obfuscate the fact that this library is not made by you or that it is
749
     free is expressly prohibited. When crediting the usage of this library,
750
     it's enough to include my name and email address, that is:
751
     "Juha Nieminen (warp@iki.fi)". Also a URL to the library download page
752
     would be nice, although not required. The official URL is:
753
       http://iki.fi/warp/FunctionParser/
754
 
755
  6. And the necessary "lawyer stuff":
756
 
757
     The above copyright notice and this permission notice shall be
758
     included in all copies or substantial portions of the Software.
759
 
760
     The software is provided "as is", without warranty of any kind,
761
     express or implied, including but not limited to the warranties of
762
     merchantability, fitness for a particular purpose and noninfringement.
763
     In no event shall the authors or copyright holders be liable for any
764
     claim, damages or other liability, whether in an action of contract,
765
     tort or otherwise, arising from, out of or in connection with the
766
     software or the use or other dealings in the software.
767
 
768
 
769
---  Explanation of the section 2 of the B) license above:
770
 
771
  The section 2 tries to define "fair use" of the library in commercial
772
programs.
773
  "Fair use" of the library means that the program is not heavily dependent
774
on the library, but the library only provides a minor secondary feature
775
to the program.
776
  "Heavily dependent" means that the program depends so much on the library
777
that without it the functionality of the program would be seriously
778
degraded or the program would even become completely non-functional.
779
 
780
  In other words: If the program does not depend heavily on the library,
781
that is, the library only provides a minor secondary feature which could
782
be removed without the program being degraded in any considerable way,
783
then it's OK to use the library in the commercial program.
784
  If, however, the program depends so heavily on the library that
785
removing it would make the program non-functional or degrade its
786
functionality considerably, then it's NOT OK to use the library.
787
 
788
  The ideology behind this is that it's not fair to use a free library
789
as a base for a commercial program, but it's fair if the library is
790
just a minor, unimportant extra.
791
 
792
  If you are going to ask me for permission to use the library in a
793
commercial program, please describe the feature which the library will
794
be providing and how important it is to the program.