1 /*
2 * UAE - The Un*x Amiga Emulator
3 *
4 * Infix->RPN conversion and calculation
5 *
6 */
7
8
9 /*
10
11 Original code from http://en.wikipedia.org/wiki/Shunting_yard_algorithm
12
13 */
14
15 #define CALC_DEBUG 0
16
17 #if CALC_DEBUG
18 #define calc_log(x) do { write_log x; } while(0)
19 #else
20 #define calc_log(x)
21 #endif
22
23 #include "sysconfig.h"
24 #include "sysdeps.h"
25
26 #include "calc.h"
27
28 #include <string.h>
29 #include <stdio.h>
30
31 #define STACK_SIZE 32
32 #define MAX_VALUES 32
33 #define IOBUFFERS 256
34
35 static double parsedvalues[MAX_VALUES];
36
37 // operators
38 // precedence operators associativity
39 // 1 ! right to left
40 // 2 * / % left to right
41 // 3 + - left to right
42 // 4 = right to left
op_preced(const TCHAR c)43 static int op_preced(const TCHAR c)
44 {
45 switch(c) {
46 case '!':
47 return 4;
48 case '*': case '/': case '\\': case '%':
49 return 3;
50 case '+': case '-':
51 return 2;
52 case '=':
53 return 1;
54 }
55 return 0;
56 }
57
op_left_assoc(const TCHAR c)58 static bool op_left_assoc(const TCHAR c)
59 {
60 switch(c) {
61 // left to right
62 case '*': case '/': case '%': case '+': case '-':
63 return true;
64 // right to left
65 case '=': case '!':
66 return false;
67 }
68 return false;
69 }
70
op_arg_count(const TCHAR c)71 static unsigned int op_arg_count(const TCHAR c)
72 {
73 switch(c) {
74 case '*': case '/': case '%': case '+': case '-': case '=':
75 return 2;
76 case '!':
77 return 1;
78 default:
79 return c - 'A';
80 }
81 return 0;
82 }
83
84 #define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=')
85 #define is_function(c) (c >= 'A' && c <= 'Z')
86 #define is_ident(c) ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z'))
87
shunting_yard(const TCHAR * input,TCHAR * output)88 static bool shunting_yard(const TCHAR *input, TCHAR *output)
89 {
90 const TCHAR *strpos = input, *strend = input + _tcslen(input);
91 TCHAR c, *outpos = output;
92
93 TCHAR stack[STACK_SIZE]; // operator stack
94 unsigned int sl = 0; // stack length
95 TCHAR sc; // used for record stack element
96
97 while(strpos < strend) {
98 if (sl >= STACK_SIZE)
99 return false;
100
101 // read one token from the input stream
102 c = *strpos;
103 if(c != ' ') {
104 // If the token is a number (identifier), then add it to the output queue.
105 if(is_ident(c)) {
106 *outpos = c; ++outpos;
107 }
108 // If the token is a function token, then push it onto the stack.
109 else if(is_function(c)) {
110 stack[sl] = c;
111 ++sl;
112 }
113 // If the token is a function argument separator (e.g., a comma):
114 else if(c == ',') {
115 bool pe = false;
116 while(sl > 0) {
117 sc = stack[sl - 1];
118 if(sc == '(') {
119 pe = true;
120 break;
121 }
122 else {
123 // Until the token at the top of the stack is a left parenthesis,
124 // pop operators off the stack onto the output queue.
125 *outpos = sc;
126 ++outpos;
127 sl--;
128 }
129 }
130 // If no left parentheses are encountered, either the separator was misplaced
131 // or parentheses were mismatched.
132 if(!pe) {
133 calc_log ((_T("Error: separator or parentheses mismatched\n")));
134 return false;
135 }
136 }
137 // If the token is an operator, op1, then:
138 else if(is_operator(c)) {
139 while(sl > 0) {
140 sc = stack[sl - 1];
141 // While there is an operator token, o2, at the top of the stack
142 // op1 is left-associative and its precedence is less than or equal to that of op2,
143 // or op1 is right-associative and its precedence is less than that of op2,
144 if(is_operator(sc) &&
145 ((op_left_assoc(c) && (op_preced(c) <= op_preced(sc))) ||
146 (!op_left_assoc(c) && (op_preced(c) < op_preced(sc))))) {
147 // Pop o2 off the stack, onto the output queue;
148 *outpos = sc;
149 ++outpos;
150 sl--;
151 }
152 else {
153 break;
154 }
155 }
156 // push op1 onto the stack.
157 stack[sl] = c;
158 ++sl;
159 }
160 // If the token is a left parenthesis, then push it onto the stack.
161 else if(c == '(') {
162 stack[sl] = c;
163 ++sl;
164 }
165 // If the token is a right parenthesis:
166 else if(c == ')') {
167 bool pe = false;
168 // Until the token at the top of the stack is a left parenthesis,
169 // pop operators off the stack onto the output queue
170 while(sl > 0) {
171 sc = stack[sl - 1];
172 if(sc == '(') {
173 pe = true;
174 break;
175 }
176 else {
177 *outpos = sc;
178 ++outpos;
179 sl--;
180 }
181 }
182 // If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
183 if(!pe) {
184 calc_log ((_T("Error: parentheses mismatched\n")));
185 return false;
186 }
187 // Pop the left parenthesis from the stack, but not onto the output queue.
188 sl--;
189 // If the token at the top of the stack is a function token, pop it onto the output queue.
190 if(sl > 0) {
191 sc = stack[sl - 1];
192 if(is_function(sc)) {
193 *outpos = sc;
194 ++outpos;
195 sl--;
196 }
197 }
198 }
199 else {
200 calc_log ((_T("Unknown token %c\n"), c));
201 return false; // Unknown token
202 }
203 }
204 ++strpos;
205 }
206 // When there are no more tokens to read:
207 // While there are still operator tokens in the stack:
208 while(sl > 0) {
209 sc = stack[sl - 1];
210 if(sc == '(' || sc == ')') {
211 printf("Error: parentheses mismatched\n");
212 return false;
213 }
214 *outpos = sc;
215 ++outpos;
216 --sl;
217 }
218 *outpos = 0; // Null terminator
219 return true;
220 }
221
222
223 struct calcstack
224 {
225 TCHAR *s;
226 double val;
227 };
228
docalcx(TCHAR op,double v1,double v2)229 static double docalcx(TCHAR op, double v1, double v2)
230 {
231 switch (op)
232 {
233 case '-':
234 return v1 - v2;
235 case '+':
236 return v1 + v2;
237 case '*':
238 return v1 * v2;
239 case '/':
240 return v1 / v2;
241 case '\\':
242 return (int)v1 % (int)v2;
243
244 }
245 return 0;
246 }
247
stacktoval(struct calcstack * st)248 static double stacktoval(struct calcstack *st)
249 {
250 if (st->s) {
251 if (_tcslen(st->s) == 1 && st->s[0] >= 'a' && st->s[0] <= 'z')
252 return parsedvalues[st->s[0] - 'a'];
253 return _tstof (st->s);
254 } else {
255 return st->val;
256 }
257 }
258
docalc2(TCHAR op,struct calcstack * sv1,struct calcstack * sv2)259 static double docalc2(TCHAR op, struct calcstack *sv1, struct calcstack *sv2)
260 {
261 double v1, v2;
262
263 v1 = stacktoval(sv1);
264 v2 = stacktoval(sv2);
265 return docalcx (op, v1, v2);
266 }
docalc1(TCHAR op,struct calcstack * sv1,double v2)267 static double docalc1(TCHAR op, struct calcstack *sv1, double v2)
268 {
269 double v1;
270
271 v1 = stacktoval(sv1);
272 return docalcx (op, v1, v2);
273 }
274
275 #if CALC_DEBUG
stacktostr(struct calcstack * st)276 static TCHAR *stacktostr(struct calcstack *st)
277 {
278 static TCHAR out[256];
279 if (st->s)
280 return st->s;
281 _stprintf(out, _T("%f"), st->val);
282 return out;
283 }
284 #endif
285
chartostack(TCHAR c)286 static TCHAR *chartostack(TCHAR c)
287 {
288 TCHAR *s = xmalloc (TCHAR, 2);
289 s[0] = c;
290 s[1] = 0;
291 return s;
292 }
293
execution_order(const TCHAR * input,double * outval)294 static bool execution_order(const TCHAR *input, double *outval)
295 {
296 const TCHAR *strpos = input, *strend = input + _tcslen(input);
297 TCHAR c, res[4];
298 unsigned int sl = 0, rn = 0;
299 struct calcstack stack[STACK_SIZE] = { { 0 } }, *sc, *sc2;
300 double val = 0;
301 int i;
302 bool ok = false;
303
304 // While there are input tokens left
305 while(strpos < strend) {
306
307 if (sl >= STACK_SIZE)
308 return false;
309
310 // Read the next token from input.
311 c = *strpos;
312 // If the token is a value or identifier
313 if(is_ident(c)) {
314 // Push it onto the stack.
315 stack[sl].s = chartostack (c);
316 ++sl;
317 }
318 // Otherwise, the token is an operator (operator here includes both operators, and functions).
319 else if(is_operator(c) || is_function(c)) {
320 _stprintf(res, _T("_%02d"), rn);
321 calc_log ((_T("%s = "), res));
322 ++rn;
323 // It is known a priori that the operator takes n arguments.
324 unsigned int nargs = op_arg_count(c);
325 // If there are fewer than n values on the stack
326 if(sl < nargs) {
327 // (Error) The user has not input sufficient values in the expression.
328 return false;
329 }
330 // Else, Pop the top n values from the stack.
331 // Evaluate the operator, with the values as arguments.
332 if(is_function(c)) {
333 calc_log ((_T("%c("), c));
334 while(nargs > 0){
335 sc = &stack[sl - nargs]; // to remove reverse order of arguments
336 if(nargs > 1) {
337 calc_log ((_T("%s, "), sc));
338 }
339 else {
340 calc_log ((_T("%s)\n"), sc));
341 }
342 --nargs;
343 }
344 sl-=op_arg_count(c);
345 }
346 else {
347 if(nargs == 1) {
348 sc = &stack[sl - 1];
349 sl--;
350 val = docalc1 (c, sc, val);
351 calc_log ((_T("%c %s = %f;\n"), c, stacktostr(sc), val));
352 }
353 else {
354 sc = &stack[sl - 2];
355 calc_log ((_T("%s %c "), stacktostr(sc), c));
356 sc2 = &stack[sl - 1];
357 val = docalc2 (c, sc, sc2);
358 sl--;sl--;
359 calc_log ((_T("%s = %f;\n"), stacktostr(sc2), val));
360 }
361 }
362 // Push the returned results, if any, back onto the stack.
363 stack[sl].val = val;
364 stack[sl].s = NULL;
365 ++sl;
366 }
367 ++strpos;
368 }
369 // If there is only one value in the stack
370 // That value is the result of the calculation.
371 if(sl == 1) {
372 sc = &stack[sl - 1];
373 sl--;
374 calc_log ((_T("result = %f\n"), val));
375 if (outval)
376 *outval = val;
377 ok = true;
378 }
379 for (i = 0; i < STACK_SIZE; i++)
380 xfree (stack[i].s);
381
382 // If there are more values in the stack
383 // (Error) The user input has too many values.
384
385 return ok;
386 }
387
is_separator(TCHAR c)388 static bool is_separator(TCHAR c)
389 {
390 if (is_operator(c))
391 return true;
392 return c == 0 || c == ')' || c == ' ';
393 }
394
parse_values(const TCHAR * ins,TCHAR * out)395 static bool parse_values(const TCHAR *ins, TCHAR *out)
396 {
397 int ident = 0;
398 TCHAR tmp;
399 TCHAR inbuf[IOBUFFERS];
400 int op;
401
402 _tcscpy (inbuf, ins);
403 TCHAR *in = inbuf;
404 TCHAR *p = out;
405 op = 0;
406 if (in[0] == '-' || in[0] == '+') {
407 *p++ = '0';
408 }
409 while (*in) {
410 TCHAR *instart = in;
411 if (!_tcsncmp(in, _T("true"), 4) && is_separator(in[4])) {
412 in[0] = '1';
413 in[1] = ' ';
414 in[2] = ' ';
415 in[3] = ' ';
416 } else if (!_tcsncmp(in, _T("false"), 5) && is_separator(in[5])) {
417 in[0] = '0';
418 in[1] = ' ';
419 in[2] = ' ';
420 in[3] = ' ';
421 in[4] = ' ';
422 }
423 if (_istdigit (*in)) {
424 if (ident >= MAX_VALUES)
425 return false;
426 if (op > 1 && (in[-1] == '-' || in[-1] == '+')) {
427 instart--;
428 p--;
429 }
430 *p++ = ident + 'a';
431 while (_istdigit (*in) || *in == '.')
432 in++;
433 tmp = *in;
434 *in = 0;
435 parsedvalues[ident++] = _tstof (instart);
436 *in = tmp;
437 op = 0;
438 } else {
439 if (is_operator(*in))
440 op++;
441 *p++ = *in++;
442 }
443 }
444 *p = 0;
445 return true;
446 }
447
calc(const TCHAR * input,double * outval)448 bool calc(const TCHAR *input, double *outval)
449 {
450 TCHAR output[IOBUFFERS], output2[IOBUFFERS];
451 calc_log ((_T("IN: '%s'\n"), input));
452 if (parse_values(input, output2)) {
453 if(shunting_yard(output2, output)) {
454 calc_log ((_T("RPN OUT: %s\n"), output));
455 if(!execution_order(output, outval)) {
456 calc_log ((_T("PARSE ERROR!\n")));
457 } else {
458 return true;
459 }
460 }
461 }
462 return false;
463 }
464
iscalcformula(const TCHAR * formula)465 bool iscalcformula (const TCHAR *formula)
466 {
467 for (int i = 0; i < _tcslen (formula); i++) {
468 TCHAR c = formula[i];
469 if (is_operator (c))
470 return true;
471 }
472 return false;
473 }
474
475