Mercurial > ~darius > hgwebdir.cgi > modulator

comparison q/expr.c @ 14:388074ff9474

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add fixed point code
author Daniel O'Connor <darius@dons.net.au>
date Tue, 25 Feb 2025 13:28:29 +1030
parents
children
comparison
equal deleted inserted replaced
13:032acb7fbc04 14:388074ff9474
1 /* Project: Small Expression Evaluator for Q library
2 * Author: Richard James Howe
3 * License: The Unlicense
4 * See: <https://en.wikipedia.org/wiki/Shunting-yard_algorithm> */
5
6 #include <assert.h>
7 #include <ctype.h>
8 #include <limits.h>
9 #include <stdarg.h>
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13 #include "q.h"
14
15 #define BUILD_BUG_ON(condition) ((void)sizeof(char[1 - 2*!!(condition)]))
16 #define DEFAULT_STACK_SIZE (64)
17
18 enum { ASSOCIATE_NONE, ASSOCIATE_LEFT, ASSOCIATE_RIGHT, };
19 enum { LEX_NUMBER, LEX_OPERATOR, LEX_END, };
20
21 static void expr_delete(qexpr_t *e) {
22 if (!e)
23 return;
24 free(e->ops);
25 free(e->numbers);
26 for (size_t i = 0; i < e->vars_max; i++) {
27 free(e->vars[i]->name);
28 free(e->vars[i]);
29 }
30 free(e->vars);
31 free(e);
32 }
33
34 static qexpr_t *expr_new(size_t max) {
35 max = max ? max : 64;
36 qexpr_t *e = calloc(sizeof(*e), 1);
37 if (!e)
38 goto fail;
39 e->ops = calloc(sizeof(*e->ops), max);
40 e->numbers = calloc(sizeof(*(e->numbers)), max);
41 if (!(e->ops) || !(e->numbers))
42 goto fail;
43 e->ops_max = max;
44 e->numbers_max = max;
45 qexpr_init(e);
46 return e;
47 fail:
48 expr_delete(e);
49 return NULL;
50 }
51
52 static qvariable_t *variable_lookup(qexpr_t *e, const char *name) {
53 assert(e);
54 for (size_t i = 0; i < e->vars_max; i++) {
55 qvariable_t *v = e->vars[i];
56 if (!strcmp(v->name, name))
57 return v;
58 }
59 return NULL;
60 }
61
62 static char *estrdup(const char *s) {
63 assert(s);
64 const size_t l = strlen(s) + 1;
65 char *r = malloc(l);
66 return memcpy(r, s, l);
67 }
68
69 static int variable_name_is_valid(const char *n) {
70 assert(n);
71 if (!isalpha(*n) && !(*n == '_'))
72 return 0;
73 for (n++; *n; n++)
74 if (!isalnum(*n) && !(*n == '_'))
75 return 0;
76 return 1;
77 }
78
79 static qvariable_t *variable_add(qexpr_t *e, const char *name, q_t value) {
80 assert(e);
81 assert(name);
82 qvariable_t *v = variable_lookup(e, name), **vs = e->vars;
83 if (v) {
84 v->value = value;
85 return v;
86 }
87 if (!variable_name_is_valid(name))
88 return NULL;
89 char *s = estrdup(name);
90 vs = realloc(e->vars, (e->vars_max + 1) * sizeof(*vs));
91 v = calloc(1, sizeof(*v));
92 if (!vs || !v || !s)
93 goto fail;
94 v->name = s;
95 v->value = value;
96 vs[e->vars_max++] = v;
97 e->vars = vs;
98 return v;
99 fail:
100 free(v);
101 free(s);
102 free(vs);
103 if (vs != e->vars)
104 free(e->vars);
105 return NULL;
106 }
107
108 static inline int tests(FILE *out) {
109 assert(out);
110 int report = 0;
111 static const struct test {
112 int r;
113 q_t result;
114 const char *expr;
115 } tests[] = { // NB. Variables defined later.
116 { -1, QINT( 0), "" },
117 { -1, QINT( 0), "(" },
118 { -1, QINT( 0), ")" },
119 { -1, QINT( 0), "2**3" },
120 { 0, QINT( 0), "0" },
121 { 0, QINT( 2), "1+1" },
122 { 0, -QINT( 1), "-1" },
123 { 0, QINT( 1), "--1" },
124 { 0, QINT(14), "2+(3*4)" },
125 { 0, QINT(23), "a+(b*5)" },
126 { -1, QINT(14), "(2+(3* 4)" },
127 { -1, QINT(14), "2+(3*4)(" },
128 { 0, QINT(14), "2+3*4" },
129 { 0, QINT( 0), " 2==3 " },
130 { 0, QINT( 1), "2 ==2" },
131 { 0, QINT( 1), "2== (1+1)" },
132 //{ 0, QINT( 8), "2 pow 3" },
133 //{ -1, QINT( 0), "2pow3" },
134 { 0, QINT(20), "(2+3)*4" },
135 { 0, -QINT( 4), "(2+(-3))*4" },
136 { -1, QINT( 0), "1/0" },
137 { -1, QINT( 0), "1%0" },
138 { 0, QINT(50), "100/2" },
139 { 0, QINT( 2), "1--1", },
140 { 0, QINT( 0), "1---1", },
141 };
142
143 if (fputs("Running Built In Self Tests:\n", out) < 0)
144 report = -1;
145 const size_t length = sizeof (tests) / sizeof (tests[0]);
146 for (size_t i = 0; i < length; i++) {
147 qexpr_t *e = expr_new(64);
148 const struct test *test = &tests[i];
149 if (!e) {
150 (void)fprintf(out, "test failed (unable to allocate)\n");
151 report = -1;
152 goto end;
153 }
154
155 qvariable_t *v1 = variable_add(e, "a", QINT(3));
156 qvariable_t *v2 = variable_add(e, "b", QINT(4));
157 qvariable_t *v3 = variable_add(e, "c", -QINT(5));
158 if (!v1 || !v2 || !v3) {
159 (void)fprintf(out, "test failed (unable to assign variable)\n");
160 report = -1;
161 goto end;
162 }
163
164 const int r = qexpr(e, test->expr);
165 const q_t tos = e->numbers[0];
166 const int pass = (r == test->r) && (r != 0 || tos == test->result);
167 if (fprintf(out, "%s: r(%2d), eval(\"%s\") = %lg \n",
168 pass ? " ok" : " FAIL", r, test->expr, (double)tos) < 0)
169 report = -1;
170 if (!pass) {
171 (void)fprintf(out, "\tExpected: r(%2d), %lg\n",
172 test->r, (double)(test->result));
173 report = -1;
174 }
175 expr_delete(e);
176 }
177 end:
178 if (fprintf(out, "Tests Complete: %s\n", report == 0 ? "pass" : "FAIL") < 0)
179 report = -1;
180 return report;
181 }
182
183 static qexpr_t *expr_new_with_vars(size_t max) {
184 qexpr_t *e = expr_new(max);
185 if (!e) return NULL;
186 if (!variable_add(e, "whole", qinfo.whole)) goto fail;
187 if (!variable_add(e, "fractional", qinfo.fractional)) goto fail;
188 if (!variable_add(e, "bit", qinfo.bit)) goto fail;
189 if (!variable_add(e, "smallest", qinfo.min)) goto fail;
190 if (!variable_add(e, "biggest", qinfo.max)) goto fail;
191 if (!variable_add(e, "pi", qinfo.pi)) goto fail;
192 if (!variable_add(e, "e", qinfo.e)) goto fail;
193 if (!variable_add(e, "sqrt2", qinfo.sqrt2)) goto fail;
194 if (!variable_add(e, "sqrt3", qinfo.sqrt3)) goto fail;
195 if (!variable_add(e, "ln2", qinfo.ln2)) goto fail;
196 if (!variable_add(e, "ln10", qinfo.ln10)) goto fail;
197 return e;
198 fail:
199 expr_delete(e);
200 return NULL;
201 }
202
203 static int usage(FILE *out, const char *arg0) {
204 assert(out);
205 assert(arg0);
206 return fprintf(out, "usage: %s expr\n", arg0);
207 }
208
209 int main(int argc, char *argv[]) {
210
211 if (argc == 1) {
212 if (usage(stderr, argv[0]) < 0) { return 1; }
213 return tests(stderr);
214 }
215
216 if (argc < 2) {
217 (void)fprintf(stderr, "usage: %s expr\n", argv[0]);
218 return 1;
219 }
220
221 int r = 0;
222
223 for (int i = 1; i < argc; i++) {
224 qexpr_t *e = expr_new_with_vars(0);
225 if (!e) {
226 (void)fprintf(stderr, "allocate failed\n");
227 r = 1;
228 break;
229 }
230 if (qexpr(e, argv[i]) == 0) {
231 char n[64 + 1] = { 0, };
232 qsprint(e->numbers[0], n, sizeof n);
233 if (printf("%s\n", n) < 0)
234 r = 1;
235 r = 0;
236 } else {
237 (void)fprintf(stderr, "error: %s\n", e->error_string);
238 r = 1;
239 }
240 expr_delete(e);
241 }
242 return r;
243 }
244
245