1/*
2 * TINYEXPR - Tiny recursive descent parser and evaluation engine in C
3 *
4 * Copyright (c) 2015-2018 Lewis Van Winkle
5 *
6 * http://CodePlea.com
7 *
8 * This software is provided 'as-is', without any express or implied
9 * warranty. In no event will the authors be held liable for any damages
10 * arising from the use of this software.
11 *
12 * Permission is granted to anyone to use this software for any purpose,
13 * including commercial applications, and to alter it and redistribute it
14 * freely, subject to the following restrictions:
15 *
16 * 1. The origin of this software must not be misrepresented; you must not
17 * claim that you wrote the original software. If you use this software
18 * in a product, an acknowledgement in the product documentation would be
19 * appreciated but is not required.
20 * 2. Altered source versions must be plainly marked as such, and must not be
21 * misrepresented as being the original software.
22 * 3. This notice may not be removed or altered from any source distribution.
23 */
24
25/* COMPILE TIME OPTIONS */
26
27/* Exponentiation associativity:
28For a^b^c = (a^b)^c and -a^b = (-a)^b do nothing.
29For a^b^c = a^(b^c) and -a^b = -(a^b) uncomment the next line.*/
30/* #define TE_POW_FROM_RIGHT */
31
32/* Logarithms
33For log = base 10 log do nothing
34For log = natural log uncomment the next line. */
35/* #define TE_NAT_LOG */
36
37#include "tinyexpr.h"
38#include <stdlib.h>
39#include <math.h>
40#include <string.h>
41#include <stdio.h>
42#include <limits.h>
43
44#ifndef NAN
45#define NAN (0.0/0.0)
46#endif
47
48#ifndef INFINITY
49#define INFINITY (1.0/0.0)
50#endif
51
52
53typedef double (*te_fun2)(double, double);
54
55enum {
56 TOK_NULL = TE_CLOSURE7+1, TOK_ERROR, TOK_END, TOK_SEP,
57 TOK_OPEN, TOK_CLOSE, TOK_NUMBER, TOK_VARIABLE, TOK_INFIX
58};
59
60
61enum {TE_CONSTANT = 1};
62
63
64typedef struct state {
65 const char *start;
66 const char *next;
67 int type;
68 union {double value; const double *bound; const void *function;};
69 void *context;
70
71 const te_variable *lookup;
72 int lookup_len;
73} state;
74
75
76#define TYPE_MASK(TYPE) ((TYPE)&0x0000001F)
77
78#define IS_PURE(TYPE) (((TYPE) & TE_FLAG_PURE) != 0)
79#define IS_FUNCTION(TYPE) (((TYPE) & TE_FUNCTION0) != 0)
80#define IS_CLOSURE(TYPE) (((TYPE) & TE_CLOSURE0) != 0)
81#define ARITY(TYPE) ( ((TYPE) & (TE_FUNCTION0 | TE_CLOSURE0)) ? ((TYPE) & 0x00000007) : 0 )
82#define NEW_EXPR(type, ...) new_expr((type), (const te_expr*[]){__VA_ARGS__})
83
84static te_expr *new_expr(const int type, const te_expr *parameters[]) {
85 const int arity = ARITY(type);
86 const int psize = sizeof(void*) * arity;
87 const int size = (sizeof(te_expr) - sizeof(void*)) + psize + (IS_CLOSURE(type) ? sizeof(void*) : 0);
88 te_expr *ret = malloc(size);
89 memset(ret, 0, size);
90 if (arity && parameters) {
91 memcpy(ret->parameters, parameters, psize);
92 }
93 ret->type = type;
94 ret->bound = 0;
95 return ret;
96}
97
98
99void te_free_parameters(te_expr *n) {
100 if (!n) return;
101 switch (TYPE_MASK(n->type)) {
102 case TE_FUNCTION7: case TE_CLOSURE7: te_free(n->parameters[6]); /* Falls through. */
103 case TE_FUNCTION6: case TE_CLOSURE6: te_free(n->parameters[5]); /* Falls through. */
104 case TE_FUNCTION5: case TE_CLOSURE5: te_free(n->parameters[4]); /* Falls through. */
105 case TE_FUNCTION4: case TE_CLOSURE4: te_free(n->parameters[3]); /* Falls through. */
106 case TE_FUNCTION3: case TE_CLOSURE3: te_free(n->parameters[2]); /* Falls through. */
107 case TE_FUNCTION2: case TE_CLOSURE2: te_free(n->parameters[1]); /* Falls through. */
108 case TE_FUNCTION1: case TE_CLOSURE1: te_free(n->parameters[0]);
109 }
110}
111
112
113void te_free(te_expr *n) {
114 if (!n) return;
115 te_free_parameters(n);
116 free(n);
117}
118
119
120static double pi(void) {return 3.14159265358979323846;}
121static double e(void) {return 2.71828182845904523536;}
122static double fac(double a) {/* simplest version of fac */
123 if (a < 0.0)
124 return NAN;
125 if (a > UINT_MAX)
126 return INFINITY;
127 unsigned int ua = (unsigned int)(a);
128 unsigned long int result = 1, i;
129 for (i = 1; i <= ua; i++) {
130 if (i > ULONG_MAX / result)
131 return INFINITY;
132 result *= i;
133 }
134 return (double)result;
135}
136static double ncr(double n, double r) {
137 if (n < 0.0 || r < 0.0 || n < r) return NAN;
138 if (n > UINT_MAX || r > UINT_MAX) return INFINITY;
139 unsigned long int un = (unsigned int)(n), ur = (unsigned int)(r), i;
140 unsigned long int result = 1;
141 if (ur > un / 2) ur = un - ur;
142 for (i = 1; i <= ur; i++) {
143 if (result > ULONG_MAX / (un - ur + i))
144 return INFINITY;
145 result *= un - ur + i;
146 result /= i;
147 }
148 return result;
149}
150static double npr(double n, double r) {return ncr(n, r) * fac(r);}
151static double te_ceil(double x) {return ceil(x);}
152static double te_floor(double x) {return floor(x);}
153
154static const te_variable functions[] = {
155 /* must be in alphabetical order */
156 {"abs", fabs, TE_FUNCTION1 | TE_FLAG_PURE, 0},
157 {"acos", acos, TE_FUNCTION1 | TE_FLAG_PURE, 0},
158 {"asin", asin, TE_FUNCTION1 | TE_FLAG_PURE, 0},
159 {"atan", atan, TE_FUNCTION1 | TE_FLAG_PURE, 0},
160 {"atan2", atan2, TE_FUNCTION2 | TE_FLAG_PURE, 0},
161 {"ceil", te_ceil, TE_FUNCTION1 | TE_FLAG_PURE, 0},
162 {"cos", cos, TE_FUNCTION1 | TE_FLAG_PURE, 0},
163 {"cosh", cosh, TE_FUNCTION1 | TE_FLAG_PURE, 0},
164 {"e", e, TE_FUNCTION0 | TE_FLAG_PURE, 0},
165 {"exp", exp, TE_FUNCTION1 | TE_FLAG_PURE, 0},
166 {"fac", fac, TE_FUNCTION1 | TE_FLAG_PURE, 0},
167 {"floor",te_floor,TE_FUNCTION1 | TE_FLAG_PURE, 0},
168 {"ln", log, TE_FUNCTION1 | TE_FLAG_PURE, 0},
169#ifdef TE_NAT_LOG
170 {"log", log, TE_FUNCTION1 | TE_FLAG_PURE, 0},
171#else
172 {"log", log10, TE_FUNCTION1 | TE_FLAG_PURE, 0},
173#endif
174 {"log10", log10, TE_FUNCTION1 | TE_FLAG_PURE, 0},
175 {"ncr", ncr, TE_FUNCTION2 | TE_FLAG_PURE, 0},
176 {"npr", npr, TE_FUNCTION2 | TE_FLAG_PURE, 0},
177 {"pi", pi, TE_FUNCTION0 | TE_FLAG_PURE, 0},
178 {"pow", pow, TE_FUNCTION2 | TE_FLAG_PURE, 0},
179 {"sin", sin, TE_FUNCTION1 | TE_FLAG_PURE, 0},
180 {"sinh", sinh, TE_FUNCTION1 | TE_FLAG_PURE, 0},
181 {"sqrt", sqrt, TE_FUNCTION1 | TE_FLAG_PURE, 0},
182 {"tan", tan, TE_FUNCTION1 | TE_FLAG_PURE, 0},
183 {"tanh", tanh, TE_FUNCTION1 | TE_FLAG_PURE, 0},
184 {0, 0, 0, 0}
185};
186
187static const te_variable *find_builtin(const char *name, int len) {
188 int imin = 0;
189 int imax = sizeof(functions) / sizeof(te_variable) - 2;
190
191 /*Binary search.*/
192 while (imax >= imin) {
193 const int i = (imin + ((imax-imin)/2));
194 int c = strncmp(name, functions[i].name, len);
195 if (!c) c = '\0' - functions[i].name[len];
196 if (c == 0) {
197 return functions + i;
198 } else if (c > 0) {
199 imin = i + 1;
200 } else {
201 imax = i - 1;
202 }
203 }
204
205 return 0;
206}
207
208static const te_variable *find_lookup(const state *s, const char *name, int len) {
209 int iters;
210 const te_variable *var;
211 if (!s->lookup) return 0;
212
213 for (var = s->lookup, iters = s->lookup_len; iters; ++var, --iters) {
214 if (strncmp(name, var->name, len) == 0 && var->name[len] == '\0') {
215 return var;
216 }
217 }
218 return 0;
219}
220
221
222
223static double add(double a, double b) {return a + b;}
224static double sub(double a, double b) {return a - b;}
225static double mul(double a, double b) {return a * b;}
226static double divide(double a, double b) {return a / b;}
227static double negate(double a) {return -a;}
228static double comma(double a, double b) {(void)a; return b;}
229
230
231void next_token(state *s) {
232 s->type = TOK_NULL;
233
234 do {
235
236 if (!*s->next){
237 s->type = TOK_END;
238 return;
239 }
240
241 /* Try reading a number. */
242 if ((s->next[0] >= '0' && s->next[0] <= '9') || s->next[0] == '.') {
243 s->value = strtod(s->next, (char**)&s->next);
244 s->type = TOK_NUMBER;
245 } else {
246 /* Look for a variable or builtin function call. */
247 if (s->next[0] >= 'a' && s->next[0] <= 'z') {
248 const char *start;
249 start = s->next;
250 while ((s->next[0] >= 'a' && s->next[0] <= 'z') || (s->next[0] >= '0' && s->next[0] <= '9') || (s->next[0] == '_')) s->next++;
251
252 const te_variable *var = find_lookup(s, start, s->next - start);
253 if (!var) var = find_builtin(start, s->next - start);
254
255 if (!var) {
256 s->type = TOK_ERROR;
257 } else {
258 switch(TYPE_MASK(var->type))
259 {
260 case TE_VARIABLE:
261 s->type = TOK_VARIABLE;
262 s->bound = var->address;
263 break;
264
265 case TE_CLOSURE0: case TE_CLOSURE1: case TE_CLOSURE2: case TE_CLOSURE3: /* Falls through. */
266 case TE_CLOSURE4: case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7: /* Falls through. */
267 s->context = var->context; /* Falls through. */
268
269 case TE_FUNCTION0: case TE_FUNCTION1: case TE_FUNCTION2: case TE_FUNCTION3: /* Falls through. */
270 case TE_FUNCTION4: case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7: /* Falls through. */
271 s->type = var->type;
272 s->function = var->address;
273 break;
274 }
275 }
276
277 } else {
278 /* Look for an operator or special character. */
279 switch (s->next++[0]) {
280 case '+': s->type = TOK_INFIX; s->function = add; break;
281 case '-': s->type = TOK_INFIX; s->function = sub; break;
282 case '*': s->type = TOK_INFIX; s->function = mul; break;
283 case '/': s->type = TOK_INFIX; s->function = divide; break;
284 case '^': s->type = TOK_INFIX; s->function = pow; break;
285 case '%': s->type = TOK_INFIX; s->function = fmod; break;
286 case '(': s->type = TOK_OPEN; break;
287 case ')': s->type = TOK_CLOSE; break;
288 case ',': s->type = TOK_SEP; break;
289 case ' ': case '\t': case '\n': case '\r': break;
290 default: s->type = TOK_ERROR; break;
291 }
292 }
293 }
294 } while (s->type == TOK_NULL);
295}
296
297
298static te_expr *list(state *s);
299static te_expr *expr(state *s);
300static te_expr *power(state *s);
301
302static te_expr *base(state *s) {
303 /* <base> = <constant> | <variable> | <function-0> {"(" ")"} | <function-1> <power> | <function-X> "(" <expr> {"," <expr>} ")" | "(" <list> ")" */
304 te_expr *ret;
305 int arity;
306
307 switch (TYPE_MASK(s->type)) {
308 case TOK_NUMBER:
309 ret = new_expr(TE_CONSTANT, 0);
310 ret->value = s->value;
311 next_token(s);
312 break;
313
314 case TOK_VARIABLE:
315 ret = new_expr(TE_VARIABLE, 0);
316 ret->bound = s->bound;
317 next_token(s);
318 break;
319
320 case TE_FUNCTION0:
321 case TE_CLOSURE0:
322 ret = new_expr(s->type, 0);
323 ret->function = s->function;
324 if (IS_CLOSURE(s->type)) ret->parameters[0] = s->context;
325 next_token(s);
326 if (s->type == TOK_OPEN) {
327 next_token(s);
328 if (s->type != TOK_CLOSE) {
329 s->type = TOK_ERROR;
330 } else {
331 next_token(s);
332 }
333 }
334 break;
335
336 case TE_FUNCTION1:
337 case TE_CLOSURE1:
338 ret = new_expr(s->type, 0);
339 ret->function = s->function;
340 if (IS_CLOSURE(s->type)) ret->parameters[1] = s->context;
341 next_token(s);
342 ret->parameters[0] = power(s);
343 break;
344
345 case TE_FUNCTION2: case TE_FUNCTION3: case TE_FUNCTION4:
346 case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7:
347 case TE_CLOSURE2: case TE_CLOSURE3: case TE_CLOSURE4:
348 case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7:
349 arity = ARITY(s->type);
350
351 ret = new_expr(s->type, 0);
352 ret->function = s->function;
353 if (IS_CLOSURE(s->type)) ret->parameters[arity] = s->context;
354 next_token(s);
355
356 if (s->type != TOK_OPEN) {
357 s->type = TOK_ERROR;
358 } else {
359 int i;
360 for(i = 0; i < arity; i++) {
361 next_token(s);
362 ret->parameters[i] = expr(s);
363 if(s->type != TOK_SEP) {
364 break;
365 }
366 }
367 if(s->type != TOK_CLOSE || i != arity - 1) {
368 s->type = TOK_ERROR;
369 } else {
370 next_token(s);
371 }
372 }
373
374 break;
375
376 case TOK_OPEN:
377 next_token(s);
378 ret = list(s);
379 if (s->type != TOK_CLOSE) {
380 s->type = TOK_ERROR;
381 } else {
382 next_token(s);
383 }
384 break;
385
386 default:
387 ret = new_expr(0, 0);
388 s->type = TOK_ERROR;
389 ret->value = NAN;
390 break;
391 }
392
393 return ret;
394}
395
396
397static te_expr *power(state *s) {
398 /* <power> = {("-" | "+")} <base> */
399 int sign = 1;
400 while (s->type == TOK_INFIX && (s->function == add || s->function == sub)) {
401 if (s->function == sub) sign = -sign;
402 next_token(s);
403 }
404
405 te_expr *ret;
406
407 if (sign == 1) {
408 ret = base(s);
409 } else {
410 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, base(s));
411 ret->function = negate;
412 }
413
414 return ret;
415}
416
417#ifdef TE_POW_FROM_RIGHT
418static te_expr *factor(state *s) {
419 /* <factor> = <power> {"^" <power>} */
420 te_expr *ret = power(s);
421
422 int neg = 0;
423 te_expr *insertion = 0;
424
425 if (ret->type == (TE_FUNCTION1 | TE_FLAG_PURE) && ret->function == negate) {
426 te_expr *se = ret->parameters[0];
427 free(ret);
428 ret = se;
429 neg = 1;
430 }
431
432 while (s->type == TOK_INFIX && (s->function == pow)) {
433 te_fun2 t = s->function;
434 next_token(s);
435
436 if (insertion) {
437 /* Make exponentiation go right-to-left. */
438 te_expr *insert = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, insertion->parameters[1], power(s));
439 insert->function = t;
440 insertion->parameters[1] = insert;
441 insertion = insert;
442 } else {
443 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, power(s));
444 ret->function = t;
445 insertion = ret;
446 }
447 }
448
449 if (neg) {
450 ret = NEW_EXPR(TE_FUNCTION1 | TE_FLAG_PURE, ret);
451 ret->function = negate;
452 }
453
454 return ret;
455}
456#else
457static te_expr *factor(state *s) {
458 /* <factor> = <power> {"^" <power>} */
459 te_expr *ret = power(s);
460
461 while (s->type == TOK_INFIX && (s->function == pow)) {
462 te_fun2 t = s->function;
463 next_token(s);
464 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, power(s));
465 ret->function = t;
466 }
467
468 return ret;
469}
470#endif
471
472
473
474static te_expr *term(state *s) {
475 /* <term> = <factor> {("*" | "/" | "%") <factor>} */
476 te_expr *ret = factor(s);
477
478 while (s->type == TOK_INFIX && (s->function == mul || s->function == divide || s->function == fmod)) {
479 te_fun2 t = s->function;
480 next_token(s);
481 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, factor(s));
482 ret->function = t;
483 }
484
485 return ret;
486}
487
488
489static te_expr *expr(state *s) {
490 /* <expr> = <term> {("+" | "-") <term>} */
491 te_expr *ret = term(s);
492
493 while (s->type == TOK_INFIX && (s->function == add || s->function == sub)) {
494 te_fun2 t = s->function;
495 next_token(s);
496 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, term(s));
497 ret->function = t;
498 }
499
500 return ret;
501}
502
503
504static te_expr *list(state *s) {
505 /* <list> = <expr> {"," <expr>} */
506 te_expr *ret = expr(s);
507
508 while (s->type == TOK_SEP) {
509 next_token(s);
510 ret = NEW_EXPR(TE_FUNCTION2 | TE_FLAG_PURE, ret, expr(s));
511 ret->function = comma;
512 }
513
514 return ret;
515}
516
517
518#define TE_FUN(...) ((double(*)(__VA_ARGS__))n->function)
519#define M(e) te_eval(n->parameters[e])
520
521
522double te_eval(const te_expr *n) {
523 if (!n) return NAN;
524
525 switch(TYPE_MASK(n->type)) {
526 case TE_CONSTANT: return n->value;
527 case TE_VARIABLE: return *n->bound;
528
529 case TE_FUNCTION0: case TE_FUNCTION1: case TE_FUNCTION2: case TE_FUNCTION3:
530 case TE_FUNCTION4: case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7:
531 switch(ARITY(n->type)) {
532 case 0: return TE_FUN(void)();
533 case 1: return TE_FUN(double)(M(0));
534 case 2: return TE_FUN(double, double)(M(0), M(1));
535 case 3: return TE_FUN(double, double, double)(M(0), M(1), M(2));
536 case 4: return TE_FUN(double, double, double, double)(M(0), M(1), M(2), M(3));
537 case 5: return TE_FUN(double, double, double, double, double)(M(0), M(1), M(2), M(3), M(4));
538 case 6: return TE_FUN(double, double, double, double, double, double)(M(0), M(1), M(2), M(3), M(4), M(5));
539 case 7: return TE_FUN(double, double, double, double, double, double, double)(M(0), M(1), M(2), M(3), M(4), M(5), M(6));
540 default: return NAN;
541 }
542
543 case TE_CLOSURE0: case TE_CLOSURE1: case TE_CLOSURE2: case TE_CLOSURE3:
544 case TE_CLOSURE4: case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7:
545 switch(ARITY(n->type)) {
546 case 0: return TE_FUN(void*)(n->parameters[0]);
547 case 1: return TE_FUN(void*, double)(n->parameters[1], M(0));
548 case 2: return TE_FUN(void*, double, double)(n->parameters[2], M(0), M(1));
549 case 3: return TE_FUN(void*, double, double, double)(n->parameters[3], M(0), M(1), M(2));
550 case 4: return TE_FUN(void*, double, double, double, double)(n->parameters[4], M(0), M(1), M(2), M(3));
551 case 5: return TE_FUN(void*, double, double, double, double, double)(n->parameters[5], M(0), M(1), M(2), M(3), M(4));
552 case 6: return TE_FUN(void*, double, double, double, double, double, double)(n->parameters[6], M(0), M(1), M(2), M(3), M(4), M(5));
553 case 7: return TE_FUN(void*, double, double, double, double, double, double, double)(n->parameters[7], M(0), M(1), M(2), M(3), M(4), M(5), M(6));
554 default: return NAN;
555 }
556
557 default: return NAN;
558 }
559
560}
561
562#undef TE_FUN
563#undef M
564
565static void optimize(te_expr *n) {
566 /* Evaluates as much as possible. */
567 if (n->type == TE_CONSTANT) return;
568 if (n->type == TE_VARIABLE) return;
569
570 /* Only optimize out functions flagged as pure. */
571 if (IS_PURE(n->type)) {
572 const int arity = ARITY(n->type);
573 int known = 1;
574 int i;
575 for (i = 0; i < arity; ++i) {
576 optimize(n->parameters[i]);
577 if (((te_expr*)(n->parameters[i]))->type != TE_CONSTANT) {
578 known = 0;
579 }
580 }
581 if (known) {
582 const double value = te_eval(n);
583 te_free_parameters(n);
584 n->type = TE_CONSTANT;
585 n->value = value;
586 }
587 }
588}
589
590
591te_expr *te_compile(const char *expression, const te_variable *variables, int var_count, int *error) {
592 state s;
593 s.start = s.next = expression;
594 s.lookup = variables;
595 s.lookup_len = var_count;
596
597 next_token(&s);
598 te_expr *root = list(&s);
599
600 if (s.type != TOK_END) {
601 te_free(root);
602 if (error) {
603 *error = (s.next - s.start);
604 if (*error == 0) *error = 1;
605 }
606 return 0;
607 } else {
608 optimize(root);
609 if (error) *error = 0;
610 return root;
611 }
612}
613
614
615double te_interp(const char *expression, int *error) {
616 te_expr *n = te_compile(expression, 0, 0, error);
617 double ret;
618 if (n) {
619 ret = te_eval(n);
620 te_free(n);
621 } else {
622 ret = NAN;
623 }
624 return ret;
625}
626
627static void pn (const te_expr *n, int depth) {
628 int i, arity;
629 printf("%*s", depth, "");
630
631 switch(TYPE_MASK(n->type)) {
632 case TE_CONSTANT: printf("%f\n", n->value); break;
633 case TE_VARIABLE: printf("bound %p\n", n->bound); break;
634
635 case TE_FUNCTION0: case TE_FUNCTION1: case TE_FUNCTION2: case TE_FUNCTION3:
636 case TE_FUNCTION4: case TE_FUNCTION5: case TE_FUNCTION6: case TE_FUNCTION7:
637 case TE_CLOSURE0: case TE_CLOSURE1: case TE_CLOSURE2: case TE_CLOSURE3:
638 case TE_CLOSURE4: case TE_CLOSURE5: case TE_CLOSURE6: case TE_CLOSURE7:
639 arity = ARITY(n->type);
640 printf("f%d", arity);
641 for(i = 0; i < arity; i++) {
642 printf(" %p", n->parameters[i]);
643 }
644 printf("\n");
645 for(i = 0; i < arity; i++) {
646 pn(n->parameters[i], depth + 1);
647 }
648 break;
649 }
650}
651
652
653void te_print(const te_expr *n) {
654 pn(n, 0);
655}
656