|
14
|
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
|
