1 /*
2 This file is part of darktable,
3 Copyright (C) 2013-2020 darktable developers.
4
5 darktable is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 darktable is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with darktable. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #include <glib.h>
20 #include <math.h>
21 #include <stdio.h>
22 #include <stdlib.h>
23
24 typedef enum token_types_t
25 {
26 T_NUMBER, // everything will be treated as floats
27 T_OPERATOR
28 } token_types_t;
29
30 typedef enum operators_t
31 {
32 O_PLUS,
33 O_INC,
34 O_MINUS,
35 O_DEC,
36 O_MULTIPLY,
37 O_DIVISION,
38 O_MODULO,
39 O_POWER,
40 O_LEFTROUND,
41 O_RIGHTROUND,
42 } operators_t;
43
44 typedef union token_data_t
45 {
46 float number;
47 operators_t operator;
48 } token_data_t;
49
50 typedef struct token_t
51 {
52 token_types_t type;
53 token_data_t data;
54 } token_t;
55
56 typedef struct parser_state_t
57 {
58 char *p;
59 float x;
60 token_t *token;
61 } parser_state_t;
62
63 /** the scanner **/
64
read_number(parser_state_t * self)65 static float read_number(parser_state_t *self)
66 {
67 return g_ascii_strtod(self->p, &self->p);
68 }
69
get_token(parser_state_t * self)70 static token_t *get_token(parser_state_t *self)
71 {
72 if(!self->p) return NULL;
73
74 token_t *token = (token_t *)malloc(sizeof(token_t));
75
76 for(; *self->p; self->p++)
77 {
78 switch(*self->p)
79 {
80 case ' ':
81 case '\t':
82 continue;
83 case '+':
84 if(self->p[1] == '+')
85 {
86 self->p += 2;
87 token->data.operator= O_INC;
88 }
89 else
90 {
91 self->p++;
92 token->data.operator= O_PLUS;
93 }
94 token->type = T_OPERATOR;
95 return token;
96 case '-':
97 if(self->p[1] == '-')
98 {
99 self->p += 2;
100 token->data.operator= O_DEC;
101 }
102 else
103 {
104 self->p++;
105 token->data.operator= O_MINUS;
106 }
107 token->type = T_OPERATOR;
108 return token;
109 case '*':
110 self->p++;
111 token->type = T_OPERATOR;
112 token->data.operator= O_MULTIPLY;
113 return token;
114 case '/':
115 self->p++;
116 token->type = T_OPERATOR;
117 token->data.operator= O_DIVISION;
118 return token;
119 case '%':
120 self->p++;
121 token->type = T_OPERATOR;
122 token->data.operator= O_MODULO;
123 return token;
124 case '^':
125 self->p++;
126 token->type = T_OPERATOR;
127 token->data.operator= O_POWER;
128 return token;
129 case '(':
130 self->p++;
131 token->type = T_OPERATOR;
132 token->data.operator= O_LEFTROUND;
133 return token;
134 case ')':
135 self->p++;
136 token->type = T_OPERATOR;
137 token->data.operator= O_RIGHTROUND;
138 return token;
139 case 'x':
140 case 'X':
141 self->p++;
142 token->type = T_NUMBER;
143 token->data.number = self->x;
144 return token;
145 case '0':
146 case '1':
147 case '2':
148 case '3':
149 case '4':
150 case '5':
151 case '6':
152 case '7':
153 case '8':
154 case '9':
155 case '.':
156 case ',':
157 {
158 token->data.number = read_number(self);
159 token->type = T_NUMBER;
160 return token;
161 }
162 default:
163 // people complained about the messages when "TRUE" was fed to the calculator
164 // printf("error: %c\n", *self->p);
165 break;
166 }
167 }
168
169 free(token);
170 return NULL;
171 }
172
173 /** the parser **/
174
175 static float parse_expression(parser_state_t *self);
176 static float parse_additive_expression(parser_state_t *self);
177 static float parse_multiplicative_expression(parser_state_t *self);
178 static float parse_power_expression(parser_state_t *self);
179 static float parse_unary_expression(parser_state_t *self);
180 static float parse_primary_expression(parser_state_t *self);
181
parse_expression(parser_state_t * self)182 static float parse_expression(parser_state_t *self)
183 {
184 return parse_additive_expression(self);
185 }
186
parse_additive_expression(parser_state_t * self)187 static float parse_additive_expression(parser_state_t *self)
188 {
189 if(!self->token) return NAN;
190
191 float left = parse_multiplicative_expression(self);
192
193 while(self->token && self->token->type == T_OPERATOR)
194 {
195 const operators_t operator= self->token->data.operator;
196
197 if(operator!= O_PLUS &&operator!= O_MINUS) return left;
198
199 free(self->token);
200 self->token = get_token(self);
201
202 const float right = parse_multiplicative_expression(self);
203
204 if(operator== O_PLUS)
205 left += right;
206 else if(operator== O_MINUS)
207 left -= right;
208 }
209
210 return left;
211 }
212
parse_multiplicative_expression(parser_state_t * self)213 static float parse_multiplicative_expression(parser_state_t *self)
214 {
215 if(!self->token) return NAN;
216
217 float left = parse_power_expression(self);
218
219 while(self->token && self->token->type == T_OPERATOR)
220 {
221 const operators_t operator= self->token->data.operator;
222
223 if(operator!= O_MULTIPLY &&operator!= O_DIVISION &&operator!= O_MODULO) return left;
224
225 free(self->token);
226 self->token = get_token(self);
227
228 float right = parse_power_expression(self);
229
230 if(operator== O_MULTIPLY)
231 left *= right;
232 else if(operator== O_DIVISION)
233 left /= right;
234 else if(operator== O_MODULO)
235 left = fmodf(left, right);
236 }
237
238 return left;
239 }
240
parse_power_expression(parser_state_t * self)241 static float parse_power_expression(parser_state_t *self)
242 {
243 float left, right;
244
245 if(!self->token) return NAN;
246
247 left = parse_unary_expression(self);
248
249 while(self->token && self->token->type == T_OPERATOR)
250 {
251 if(self->token->data.operator!= O_POWER) return left;
252
253 free(self->token);
254 self->token = get_token(self);
255
256 right = parse_unary_expression(self);
257
258 left = powf(left, right);
259 }
260
261 return left;
262 }
263
parse_unary_expression(parser_state_t * self)264 static float parse_unary_expression(parser_state_t *self)
265 {
266 if(!self->token) return NAN;
267
268 if(self->token->type == T_OPERATOR)
269 {
270 if(self->token->data.operator== O_MINUS)
271 {
272 free(self->token);
273 self->token = get_token(self);
274
275 return -1.0 * parse_unary_expression(self);
276 }
277 if(self->token->data.operator== O_PLUS)
278 {
279 free(self->token);
280 self->token = get_token(self);
281
282 return parse_unary_expression(self);
283 }
284 }
285
286 return parse_primary_expression(self);
287 }
288
parse_primary_expression(parser_state_t * self)289 static float parse_primary_expression(parser_state_t *self)
290 {
291 if(!self->token) return NAN;
292
293 if(self->token->type == T_NUMBER)
294 {
295 float result = self->token->data.number;
296 free(self->token);
297 self->token = get_token(self);
298 return result;
299 }
300 if(self->token->type == T_OPERATOR && self->token->data.operator== O_LEFTROUND)
301 {
302 float result;
303 free(self->token);
304 self->token = get_token(self);
305 result = parse_expression(self);
306 if(!self->token || self->token->type != T_OPERATOR || self->token->data.operator!= O_RIGHTROUND)
307 return NAN;
308 free(self->token);
309 self->token = get_token(self);
310 return result;
311 }
312
313 return NAN;
314 }
315
316 /** the public interface **/
317
dt_calculator_solve(float x,const char * formula)318 float dt_calculator_solve(float x, const char *formula)
319 {
320 if(formula == NULL || *formula == '\0') return NAN;
321
322 float result;
323 gchar *dotformula = g_strdup(formula);
324 parser_state_t *self = (parser_state_t *)malloc(sizeof(parser_state_t));
325
326 self->p = g_strdelimit(dotformula, ",", '.');
327 self->x = x;
328
329 self->token = get_token(self);
330
331 // operators_t operator = -1;
332 if(self->token && self->token->type == T_OPERATOR)
333 {
334 switch(self->token->data.operator)
335 {
336 case O_INC:
337 result = x + 1.0;
338 goto end;
339 case O_DEC:
340 result = x - 1.0;
341 goto end;
342 // case O_PLUS:
343 // case O_MINUS:
344 // case O_MULTIPLY:
345 // case O_DIVISION:
346 // case O_MODULO:
347 // case O_POWER:
348 // operator = self->token->data.operator;
349 // free(self->token);
350 // self->token = get_token(self);
351 // break;
352 default:
353 break;
354 }
355 }
356
357 result = parse_expression(self);
358
359 // switch(operator)
360 // {
361 // case O_PLUS: result = x + res; break;
362 // case O_MINUS: result = x - res; break;
363 // case O_MULTIPLY: result = x * res; break;
364 // case O_DIVISION: result = x / res; break;
365 // case O_MODULO: result = fmodf(x, res); break;
366 // case O_POWER: result = powf(x, res); break;
367 // default: break;
368 // }
369
370 if(self->token) result = NAN;
371
372 end:
373 free(self->token);
374 free(self);
375 g_free(dotformula);
376
377 return result;
378 }
379
380 // int main()
381 // {
382 // const char *input = "5/0";
383 // float x = 3;
384 //
385 // printf("%s\n", input);
386 //
387 // float res = dt_calculator_solve(x, input);
388 //
389 // printf("%f\n", res);
390 //
391 // return 0;
392 // }
393
394 // modelines: These editor modelines have been set for all relevant files by tools/update_modelines.sh
395 // vim: shiftwidth=2 expandtab tabstop=2 cindent
396 // kate: tab-indents: off; indent-width 2; replace-tabs on; indent-mode cstyle; remove-trailing-spaces modified;
397