00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #include <stdio.h>
00028 #include <stdlib.h>
00029 #include <string.h>
00030 #include <math.h>
00031 #include <ctype.h>
00032 #include <sys/time.h>
00033
00034 #include <formula-calc.h>
00035 #include <formula.h>
00036
00037 double math_b_and(double **val)
00038 {
00039 return (*val[0] > 0) && (*val[1] > 0);
00040 }
00041
00042 double math_b_or(double **val)
00043 {
00044 return (*val[0] > 0) || (*val[1] > 0);
00045 }
00046
00047 double math_b_not(double **val)
00048 {
00049 return !(*val[0] > 0);
00050 }
00051
00052 double math_eq(double **val)
00053 {
00054 return *val[0] == *val[1];
00055 }
00056
00057 double math_neq(double **val)
00058 {
00059 return *val[0] != *val[1];
00060 }
00061
00062 double math_gtr(double **val)
00063 {
00064 return *val[0] > *val[1];
00065 }
00066
00067 double math_geq(double **val)
00068 {
00069 return *val[0] >= *val[1];
00070 }
00071
00072 double math_lss(double **val)
00073 {
00074 return *val[0] < *val[1];
00075 }
00076
00077 double math_leq(double **val)
00078 {
00079 return *val[0] <= *val[1];
00080 }
00081
00082 double math_add(double **val)
00083 {
00084 return *val[0] + *val[1];
00085 }
00086
00087 double math_sub(double **val)
00088 {
00089 return *val[0] - *val[1];
00090 }
00091
00092 double math_mul(double **val)
00093 {
00094 return *val[0] * *val[1];
00095 }
00096
00097 double math_div(double **val)
00098 {
00099 return *val[0] / *val[1];
00100 }
00101
00102 double math_pow(double **val)
00103 {
00104 return pow(*val[0], *val[1]);
00105 }
00106
00107 double math_sin(double **val)
00108 {
00109 return sin(*val[0]);
00110 }
00111
00112 double math_cos(double **val)
00113 {
00114 return cos(*val[0]);
00115 }
00116
00117 double math_tan(double **val)
00118 {
00119 return tan(*val[0]);
00120 }
00121
00122 double math_sinh(double **val)
00123 {
00124 return sinh(*val[0]);
00125 }
00126
00127 double math_cosh(double **val)
00128 {
00129 return cosh(*val[0]);
00130 }
00131
00132 double math_tanh(double **val)
00133 {
00134 return tanh(*val[0]);
00135 }
00136
00137 double math_atan(double **val)
00138 {
00139 return atan(*val[0]);
00140 }
00141
00142 double math_asin(double **val)
00143 {
00144 return asin(*val[0]);
00145 }
00146
00147 double math_acos(double **val)
00148 {
00149 return acos(*val[0]);
00150 }
00151
00152 double math_atan2(double **val)
00153 {
00154 return atan2(*val[0], *val[1]);
00155 }
00156
00157 double math_sqrt(double **val)
00158 {
00159 return sqrt(*val[0]);
00160 }
00161
00162 double math_exp(double **val)
00163 {
00164 return exp(*val[0]);
00165 }
00166
00167 double math_let(double **val)
00168 {
00169 return *val[0] = *val[1];
00170 }
00171
00172 double math_sign(double **val)
00173 {
00174 if (*val[0] < 0)
00175 return -1;
00176 return 1;
00177 }
00178
00179 double math_fabs(double **val)
00180 {
00181 return fabs(*val[0]);
00182 }
00183
00184 double math_log10(double **val)
00185 {
00186 return log10(*val[0]);
00187 }
00188
00189 double math_ln(double **val)
00190 {
00191 return log(*val[0]);
00192 }
00193
00194 double math_pi(double **val)
00195 {
00196 return M_PI;
00197 }
00198
00199 double math_e(double **val)
00200 {
00201 return M_E;
00202 }
00203
00204 double math_mod(double **val)
00205 {
00206 return fmod(*val[0], *val[1]);
00207 }
00208
00209 double math_round(double **val)
00210 {
00211 return round(*val[0]);
00212 }
00213
00214 #define OPERATION_MUL 11
00215 struct operation_t operation[] =
00216 {
00217 { "==", 4, TYPE_OP, math_eq, 2 },
00218 { "=", 1, TYPE_OP, math_let, 2 },
00219 { "||", 2, TYPE_OP, math_b_or, 2 },
00220 { "&&", 3, TYPE_OP, math_b_and, 2 },
00221 { "!=", 4, TYPE_OP, math_neq, 2 },
00222 { "<=", 5, TYPE_OP, math_leq, 2 },
00223 { ">=", 5, TYPE_OP, math_geq, 2 },
00224 { "<", 5, TYPE_OP, math_lss, 2 },
00225 { ">", 5, TYPE_OP, math_gtr, 2 },
00226 { "+", 7, TYPE_OP, math_add, 2 },
00227 { "-", 7, TYPE_OP, math_sub, 2 },
00228 { "*", 8, TYPE_OP, math_mul, 2 },
00229 { "/", 8, TYPE_OP, math_div, 2 },
00230 { "!", 11, TYPE_OP, math_b_not, 1 },
00231 { "pi", 17, TYPE_MATH, math_pi, 0 },
00232 { "e", 17, TYPE_MATH, math_e, 0 },
00233 { "log10", 17, TYPE_MATH, math_log10, 1 },
00234 { "ln", 17, TYPE_MATH, math_ln, 1 },
00235 { "sin", 17, TYPE_MATH, math_sin, 1 },
00236 { "cos", 17, TYPE_MATH, math_cos, 1 },
00237 { "tan", 17, TYPE_MATH, math_tan, 1 },
00238 { "sinh", 17, TYPE_MATH, math_sinh, 1 },
00239 { "cosh", 17, TYPE_MATH, math_cosh, 1 },
00240 { "tanh", 17, TYPE_MATH, math_tanh, 1 },
00241 { "asin", 17, TYPE_MATH, math_asin, 1 },
00242 { "acos", 17, TYPE_MATH, math_acos, 1 },
00243 { "atan2", 17, TYPE_MATH, math_atan2, 2 },
00244 { "atan", 17, TYPE_MATH, math_atan, 1 },
00245 { "exp", 17, TYPE_MATH, math_exp, 1 },
00246 { "sqrt", 17, TYPE_MATH, math_sqrt, 1 },
00247 { "abs", 17, TYPE_MATH, math_fabs, 1 },
00248 { "sign", 17, TYPE_MATH, math_sign, 1 },
00249 { "round", 17, TYPE_MATH, math_round, 1 },
00250 { "mod", 17, TYPE_MATH, math_mod, 2 },
00251 { "pow", 17, TYPE_MATH, math_pow, 2 },
00252 { "", -1, TYPE_MAX, NULL, 0 }
00253 };
00254
00255 struct rpf_t *rpf_last(struct rpf_t *rpf)
00256 {
00257 for (; rpf->next; rpf = rpf->next)
00258 ;
00259
00260 return rpf;
00261 }
00262
00263 struct rpf_t *rpf_push(struct rpf_t *rpf, struct stack_t *obj)
00264 {
00265 rpf->next = malloc(sizeof(struct rpf_t));
00266 rpf->next->type = obj->type;
00267 rpf->next->value = obj->value;
00268 rpf->next->next = NULL;
00269
00270 return rpf->next;
00271 }
00272
00273 struct rpf_t *rpf_join(struct rpf_t *rpf, struct rpf_t *rpf2)
00274 {
00275 rpf->next = rpf2;
00276 for (; rpf->next; rpf = rpf->next)
00277 ;
00278
00279 return rpf;
00280 }
00281
00282 int rpf_count_num(struct rpf_t *rpf)
00283 {
00284 int count;
00285
00286 count = 0;
00287 for (; rpf; rpf = rpf->next)
00288 {
00289 count++;
00290 }
00291
00292 return count;
00293 }
00294
00295 struct rpf_t *formula_output(struct stack_t *num, int *sp_num, struct stack_t *op, int *sp_op, int rank)
00296 {
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313 int sp_op2;
00314 for (sp_op2 = *sp_op - 1; sp_op2 >= 0; sp_op2--)
00315 {
00316 struct rpf_t rpf2, *rpf2_tmp;
00317 int sp_num2;
00318
00319 rpf2_tmp = &rpf2;
00320 rpf2.type = TYPE_START;
00321
00322 int num_cnt;
00323 num_cnt = ((struct operation_t *)op[sp_op2].value)->narg;
00324 if (num_cnt > *sp_num)
00325 return NULL;
00326 for (sp_num2 = *sp_num - num_cnt; sp_num2 < *sp_num; sp_num2++)
00327 {
00328 switch (num[sp_num2].type)
00329 {
00330 case TYPE_RPF:
00331 rpf2_tmp = rpf_join(rpf2_tmp, num[sp_num2].value);
00332
00333 break;
00334 default:
00335 rpf2_tmp = rpf_push(rpf2_tmp, &num[sp_num2]);
00336
00337 break;
00338 }
00339 }
00340
00341 (*sp_num) -= num_cnt;
00342 rpf2_tmp = rpf_push(rpf2_tmp, &op[sp_op2]);
00343 (*sp_op)--;
00344
00345 num[*sp_num].rank = 0;
00346 num[*sp_num].type = TYPE_RPF;
00347 num[*sp_num].value = rpf2.next;
00348 (*sp_num)++;
00349
00350
00351
00352 }
00353 return num[*sp_num - 1].value;
00354 }
00355
00356 int formula(const char *expr, struct rpf_t **rpf, const struct variables_t *variable)
00357 {
00358 int i;
00359 struct stack_t op[256];
00360 struct stack_t num[256];
00361 int sp_op, sp_num;
00362 struct rpf_t rpf_start;
00363 struct rpf_t *rpf_tmp;
00364 *rpf = NULL;
00365 int op_cont;
00366
00367 sp_num = 0;
00368 sp_op = 0;
00369 op_cont = 0;
00370 for (; *expr; expr++)
00371 {
00372
00373 if (*expr == '(')
00374 {
00375 const char *end;
00376 int rank2;
00377 struct rpf_t *rpf2;
00378
00379 rank2 = 0;
00380 for (; isspace(*expr); expr++)
00381 ;
00382 for (end = expr; *end; end++)
00383 {
00384 if (*end == '(')
00385 rank2++;
00386 if (*end == ')')
00387 rank2--;
00388 if (rank2 == 0)
00389 break;
00390 }
00391 if (rank2 || !(*end))
00392 return 0;
00393 if (formula(expr + 1, &rpf2, variable) == 0)
00394 return 0;
00395 if (rpf2)
00396 {
00397 num[sp_num].rank = 0;
00398 num[sp_num].type = TYPE_RPF;
00399 num[sp_num].value = rpf2;
00400 sp_num++;
00401 }
00402
00403 expr = end;
00404 op_cont = 0;
00405 continue;
00406 }
00407 else if (*expr == ')')
00408 {
00409 op_cont = 0;
00410 break;
00411 }
00412 else if (*expr == ',')
00413 {
00414 if (formula_output(num, &sp_num, op, &sp_op, 0) == NULL)
00415 return 0;
00416 op_cont = 0;
00417 continue;
00418 }
00419 else if (isspace(*expr))
00420 {
00421 op_cont = 0;
00422 continue;
00423 }
00424 for (i = 0; operation[i].type != TYPE_MAX; i++)
00425 {
00426 if (strstr(expr, operation[i].op) == expr)
00427 {
00428 if (sp_op > 0 && op[sp_op - 1].rank == operation[i].rank)
00429 {
00430 int sp_op2;
00431 sp_op2 = 1;
00432 if (formula_output(num, &sp_num, op + sp_op - 1, &sp_op2, operation[i].rank) == NULL)
00433 return 0;
00434 sp_op--;
00435 }
00436 else if (sp_op > 0 && op[sp_op - 1].rank > operation[i].rank)
00437 {
00438 if (formula_output(num, &sp_num, op, &sp_op, operation[i].rank) == NULL)
00439 return 0;
00440 }
00441 expr += strlen(operation[i].op);
00442 for (; isspace(*expr); expr++)
00443 ;
00444
00445 if (sp_num == 0 && operation[i].func == math_sub)
00446 {
00447
00448 num[sp_num].rank = 0;
00449 num[sp_num].type = TYPE_VALUE;
00450 num[sp_num].value = malloc(sizeof(double));
00451 *((double *)num[sp_num].value) = -1;
00452 sp_num++;
00453 op[sp_op].rank = operation[OPERATION_MUL].rank;
00454 op[sp_op].type = operation[OPERATION_MUL].type;
00455 op[sp_op].value = &operation[OPERATION_MUL];
00456 sp_op++;
00457 op_cont = 0;
00458 expr--;
00459 break;
00460 }
00461 else if (op_cont == 1 && operation[i].type != TYPE_MATH)
00462 {
00463 if (operation[i].func == math_sub)
00464 {
00465
00466 num[sp_num].rank = 0;
00467 num[sp_num].type = TYPE_VALUE;
00468 num[sp_num].value = malloc(sizeof(double));
00469 *((double *)num[sp_num].value) = -1;
00470 sp_num++;
00471 op[sp_op].rank = operation[OPERATION_MUL].rank;
00472 op[sp_op].type = operation[OPERATION_MUL].type;
00473 op[sp_op].value = &operation[OPERATION_MUL];
00474 sp_op++;
00475 op_cont = 0;
00476 expr--;
00477 break;
00478 }
00479 else
00480 {
00481
00482 return 0;
00483 }
00484 }
00485
00486 if (operation[i].type != TYPE_MATH)
00487 {
00488 op_cont = 1;
00489 }
00490 else
00491 {
00492 op[sp_op].rank = operation[i].rank;
00493 op[sp_op].type = operation[i].type;
00494 op[sp_op].value = &operation[i];
00495 sp_op++;
00496 op_cont = 0;
00497 if (operation[i].narg > 0)
00498 {
00499 const char *end;
00500 int rank2;
00501 struct rpf_t *rpf2;
00502
00503 rank2 = 0;
00504
00505 for (end = expr; *end; end++)
00506 {
00507 if (*end == '(')
00508 rank2++;
00509 if (*end == ')')
00510 rank2--;
00511 if (rank2 == 0)
00512 break;
00513 }
00514 if (rank2 || !(*end))
00515 return 0;
00516 if (formula(expr + 1, &rpf2, variable) == 0)
00517 return 0;
00518 if (!rpf2)
00519 return 0;
00520
00521 num[sp_num].rank = 0;
00522 num[sp_num].type = TYPE_RPF;
00523 num[sp_num].value = rpf2;
00524 rpf_push(rpf_last(rpf2), &op[sp_op - 1]);
00525 sp_op--;
00526 sp_num++;
00527 expr = end + 1;
00528 }
00529 }
00530 if (operation[i].type != TYPE_MATH)
00531 {
00532 op[sp_op].rank = operation[i].rank;
00533 op[sp_op].type = operation[i].type;
00534 op[sp_op].value = &operation[i];
00535 sp_op++;
00536 }
00537 expr--;
00538
00539 break;
00540 }
00541 }
00542 if (operation[i].type != TYPE_MAX)
00543 continue;
00544 op_cont = 0;
00545 if (isalpha(*expr))
00546 {
00547 const char *end;
00548 char variable_name[256];
00549 int i;
00550
00551 if (!variable)
00552 return 0;
00553
00554 i = 0;
00555 for (end = expr; *end; end++)
00556 {
00557 if (!(isalnum(*end) || *end == '_' || *end == '[' || *end == ']'))
00558 break;
00559 variable_name[i++] = *end;
00560 }
00561 variable_name[i] = 0;
00562
00563 for (i = 0; variable[i].name; i++)
00564 {
00565 if (strcmp(variable[i].name, variable_name) == 0)
00566 {
00567 num[sp_num].rank = 0;
00568 num[sp_num].type = TYPE_VARIABLE;
00569 num[sp_num].value = variable[i].pointer;
00570 sp_num++;
00571 break;
00572 }
00573 }
00574 if (!variable[i].name)
00575 return 0;
00576 expr = end - 1;
00577 }
00578 else
00579 {
00580 const char *end;
00581
00582 for (end = expr; *end; end++)
00583 {
00584 if (!(isdigit(*end) || (end == expr && *end == '-') || *end == '.'))
00585 break;
00586 }
00587 num[sp_num].rank = 0;
00588 num[sp_num].type = TYPE_VALUE;
00589 num[sp_num].value = malloc(sizeof(double));
00590 *((double *)num[sp_num].value) = strtod(expr, NULL);
00591 sp_num++;
00592 expr = end - 1;
00593 }
00594 }
00595 if (formula_output(num, &sp_num, op, &sp_op, 0) == NULL)
00596 return 0;
00597 if (sp_num < 0 || sp_op != 0)
00598 return 0;
00599
00600 rpf_start.type = TYPE_START;
00601 rpf_tmp = &rpf_start;
00602 for (sp_num--; sp_num >= 0; sp_num--)
00603 {
00604 switch (num[sp_num].type)
00605 {
00606 case TYPE_RPF:
00607 rpf_tmp = rpf_join(rpf_tmp, num[sp_num].value);
00608 break;
00609 default:
00610 rpf_tmp = rpf_push(rpf_tmp, &num[sp_num]);
00611 break;
00612 }
00613 }
00614 *rpf = rpf_start.next;
00615 return 1;
00616 }
00617
00618 void formula_free(struct rpf_t *rpf)
00619 {
00620 for (; rpf;)
00621 {
00622 struct rpf_t *tmp;
00623 switch (rpf->type)
00624 {
00625 case TYPE_VALUE:
00626 free(rpf->value);
00627 break;
00628 case TYPE_VARIABLE:
00629 break;
00630 default:
00631 break;
00632 }
00633 tmp = rpf->next;
00634 free(rpf);
00635 rpf = tmp;
00636 }
00637 }
00638
00639 double formula_eval(struct rpf_t *rpf)
00640 {
00641 double _stack[512];
00642 double *stack[512];
00643 int sp;
00644 struct operation_t *op;
00645 double tmp;
00646
00647 sp = 0;
00648 for (; rpf; rpf = rpf->next)
00649 {
00650 switch (rpf->type)
00651 {
00652 case TYPE_VALUE:
00653 case TYPE_VARIABLE:
00654 stack[sp] = ((double *)rpf->value);
00655 sp++;
00656 break;
00657 default:
00658 op = (struct operation_t *)rpf->value;
00659 tmp = (op->func)(&stack[sp - op->narg]);
00660 sp -= op->narg;
00661 stack[sp] = &_stack[sp];
00662 _stack[sp] = tmp;
00663 sp++;
00664 break;
00665 }
00666 }
00667 return *stack[0];
00668 }
00669
00670 struct rpf_t *formula_optimize(struct rpf_t *rpf_orig)
00671 {
00672 double *stack[512];
00673 struct rpf_t *rpf_st[512];
00674 int fixed[512];
00675 int sp;
00676 struct rpf_t *rpf_new;
00677 struct rpf_t rpf_new_st;
00678 int i;
00679 struct rpf_t *rpf = rpf_orig;
00680
00681 sp = 0;
00682 for (; rpf; rpf = rpf->next)
00683 {
00684 struct operation_t *op;
00685 double tmp;
00686 switch (rpf->type)
00687 {
00688 case TYPE_VALUE:
00689 case TYPE_VARIABLE:
00690 fixed[sp] = 0;
00691 rpf_st[sp] = malloc(sizeof(struct rpf_t));
00692 *(rpf_st[sp]) = *rpf;
00693 if (rpf->type == TYPE_VALUE)
00694 {
00695 stack[sp] = malloc(sizeof(double));
00696 *(stack[sp]) = *((double *)rpf->value);
00697 rpf_st[sp]->value = stack[sp];
00698 fixed[sp] = 1;
00699 }
00700 else
00701 {
00702 stack[sp] = NULL;
00703 fixed[sp] = 0;
00704 }
00705 sp++;
00706 break;
00707 default:
00708 op = (struct operation_t *)rpf->value;
00709 for (i = 0; i < op->narg; i++)
00710 {
00711 if (!fixed[sp - 1 - i])
00712 break;
00713 }
00714 if (i == op->narg)
00715 {
00716 tmp = (op->func)(&stack[sp - op->narg]);
00717 for (i = 0; i < op->narg; i++)
00718 {
00719 if (stack[sp - 1 - i])
00720 free(stack[sp - 1 - i]);
00721 free(rpf_st[sp - 1 - i]);
00722 }
00723 sp -= op->narg;
00724 stack[sp] = malloc(sizeof(double));
00725 *(stack[sp]) = tmp;
00726 fixed[sp] = 1;
00727
00728 rpf_st[sp] = malloc(sizeof(struct rpf_t));
00729 rpf_st[sp]->type = TYPE_VALUE;
00730 rpf_st[sp]->value = stack[sp];
00731 sp++;
00732 }
00733 else
00734 {
00735 rpf_st[sp] = malloc(sizeof(struct rpf_t));
00736 *(rpf_st[sp]) = *rpf;
00737 fixed[sp] = 0;
00738 sp++;
00739 }
00740 break;
00741 }
00742 }
00743
00744 rpf_new = &rpf_new_st;
00745 rpf_new->type = TYPE_START;
00746 for (i = 0; i < sp; i++)
00747 {
00748 rpf_new->next = rpf_st[i];
00749 rpf_new->next->next = NULL;
00750 rpf_new = rpf_new->next;
00751 }
00752 return rpf_new_st.next;
00753 }
00754
00755 void formula_print(FILE *stream, struct rpf_t *rpf)
00756 {
00757 for (; rpf; rpf = rpf->next)
00758 {
00759 switch (rpf->type)
00760 {
00761 case TYPE_VALUE:
00762 fprintf(stream, "%f ", *(double *)rpf->value);
00763 break;
00764 case TYPE_VARIABLE:
00765 fprintf(stream, "VARIABLE ");
00766 break;
00767 default:
00768 fprintf(stream, "%s ", ((struct operation_t *)rpf->value)->op);
00769 break;
00770 }
00771 }
00772 }