SHARE
TWEET

fcalc.c

avp210159 Feb 1st, 2016 (edited) 400 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // avp 2016 (for ru.stackoverflow.com)
  2. // калькулятор арифметики с функциями и переменными
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include <ctype.h>
  7. #include <math.h>
  8. #include <limits.h>
  9. #include <stdint.h>
  10.  
  11. #include "fcalc.h" // http://pastebin.com/5qX5isEh
  12.  
  13. // список предопределенных функций
  14. struct dfunc {
  15.   function f;
  16.   const char *name;
  17. };
  18.  
  19. static struct dfunc dfun[] = {
  20.   {(function)sin, "sin"},
  21.   {(function)asin, "asin"},
  22.   {(function)cos, "cos"},
  23.   {(function)acos, "acos"},
  24.   {(function)tan, "tan"},
  25.   {(function)atan, "atan"},
  26.   {(function)fabs, "fabs"},
  27.   {(function)round, "round"},
  28.   {(function)ceil, "ceil"},
  29.   {(function)floor, "floor"},
  30.   {(function)trunc, "trunc"},
  31.   {(function)sqrt, "sqrt"},
  32.   {(function)cbrt, "cbrt"},
  33.   {(function)pow, "pow"},
  34.   {(function)exp, "exp"},
  35.   {(function)log, "log"},
  36.   {(function)log2, "log2"},
  37.   {(function)log10, "log10"}
  38. };
  39.  
  40. static Symtab *calc_fun = 0; /* таблица предопределенных функций,
  41.                 строится при первом вызове calc() */
  42.  
  43.  
  44. struct fact { // функция ("параметры" операции F) в стеке оперций
  45.   function f;
  46.   int fsp;    // индекс в стеке операндов (начало аргументов вызова функции)
  47. };
  48.  
  49. // контекст вычисляемого выражения
  50. struct ucalc {
  51.   const char *str; // "исходник" выражения
  52.   int  rc,         // return code (OK == 0 иначе код ошибки)
  53.     pos,           // позиция в str для поиска следующей лексемы
  54.     prevop,        // тип предыдущей лексемы (.curlex.type)
  55.     histop;        /* "история" видов лексем (operation == 1 / number == 0)
  56.               при каждом вызове calc_getlex() сдвигается влево,
  57.               младший бит устанавливается в вид текущей лексемы */
  58.   struct calc_lexem curlex;
  59.   double result;   /* конечный или любой промежуточный результат
  60.               в т.ч. прочитанное calc_getlex() число */
  61. #define STACK(T) struct { T *mem; int size, sp; }
  62.   STACK(double)      nums;  // стек опрерандов (чисел)
  63.   STACK(char)        ops;   // стек операций
  64.   STACK(struct fact) funcs; // "расширение" стека операций для функций
  65. #undef STACK
  66. };
  67.  
  68. /************************
  69.   HashTable utilities
  70. *************************/
  71.  
  72. // элемент в hashtable (ключ .name[.len])
  73. struct u_item {
  74.   struct u_item *next;
  75.   union {
  76.     function f;
  77.     double v;
  78.   };
  79.   int len;      // реальное количество байт в name[]
  80.   char name[1]; // ключ элемента hashtable
  81. };
  82.  
  83. // начальный размер  hashtable
  84. #define INIT_HTAB_SIZE 5
  85. /*
  86.   Когда ожидаемая длина списка синонимов достигает  HTAB_REHASH
  87.   (т.е. items_counter / capacity >= HTAB_REHASH)
  88.   проводим рехэширование в новую таблицу с размером в количество элементов
  89. */
  90. #define HTAB_REHASH 2
  91.  
  92. // делаем пустую таблицу p[] с указателями на списки синонимов (struct u_item)
  93. // p[-2] -- capacity (cast to `ulong`), p[-1] -- items_counter
  94. // returns &p[0] !!!
  95. static struct u_item **
  96. make_htab (uint32_t sz)
  97. {
  98.   struct u_item **p = (typeof(p))calloc(sizeof(*p), sz + 2);
  99.  
  100.   if (p) {
  101.     p[0] = (typeof(*p))(ulong)sz;
  102.     p += 2;
  103.   }
  104.  
  105.   return p;
  106. }
  107.  
  108. static inline uint32_t
  109. hash32 (const char *s, int len)
  110. {
  111.   uint32_t h = 0;
  112.  
  113.   /* Bernstein */
  114.   while (len--)
  115.     h = h * 33 + (uint8_t)(*s++);
  116.  
  117.   /* Murmur OAAT
  118.   while (len--) {
  119.     h ^= (uint8_t)(*s++);
  120.     h *= 0x5bd1e995;
  121.     h ^= h >> 15;
  122.   }
  123.   */
  124.  
  125.   /* FNV
  126.   h ^= 2166136261U;
  127.   while (len--) {
  128.     h ^= (uint8_t)(*s++);
  129.     h *= 16777619;
  130.   }
  131.   */
  132.  
  133.   return h;
  134. }
  135.  
  136. static void
  137. rehash (struct u_item **htab[])
  138. {
  139.   struct u_item **t = *htab, **newtab, *p;
  140.   ulong i, j, hsize = (ulong)t[-2], n = (ulong)t[-1];
  141.  
  142.   if (n)
  143.     if ((newtab = (typeof(newtab))calloc(sizeof(*newtab), n + 2))) {
  144.       newtab[0] = newtab[1] = (typeof(*newtab))n;
  145.       *htab = newtab + 2;
  146.  
  147.       for (i = 0; i < hsize; i++)
  148.         while ((p = t[i])) {
  149.           t[i] = p->next;
  150.           p->next = (*htab)[j = hash32(p->name, p->len) % n];
  151.           (*htab)[j] = p;
  152.         }
  153.       free(t - 2);
  154.     }
  155. }
  156.  
  157. // проверяет и при необходимости реорганизует (rehash) или создает hashtable
  158. // (пока реализовано только расширение hashtable)
  159. static int
  160. check_htab (struct u_item **htab[])
  161. {
  162.   if (htab) {
  163.     if (!*htab)
  164.       if (!(*htab = make_htab(INIT_HTAB_SIZE)))
  165.         return 0;
  166.     if ((ulong)(*htab)[-1] / (ulong)(*htab)[-2] >= HTAB_REHASH)
  167.       rehash(htab);
  168.      
  169.     return 1;
  170.   }
  171.   return 0;
  172. }
  173.  
  174. // возвращает указатель на элемент hashtable
  175. static struct u_item *
  176. get_htab (struct u_item **htab[], const char *name, int len)
  177. {
  178.   struct u_item *p = 0;
  179.  
  180.   if (len > 0 && check_htab(htab))
  181.     for (p = (*htab)[hash32(name, len) % (ulong)(*htab)[-2]]; p; p = p->next)
  182.       if (len == p->len && memcmp(p->name, name, len) == 0)
  183.         break;
  184.  
  185.   return p;
  186. }
  187.  
  188. // возвращает указатель на элемент hashtable,
  189. // если такого элемента нет, то создает его  (возвращает NULL, если нет памяти)
  190. static struct u_item *
  191. put_htab (struct u_item **htab[], const char *name, int len)
  192. {
  193.   struct u_item *p = 0;
  194.  
  195.   if (len > 0 && check_htab(htab)) {
  196.     ulong hsize = (ulong)(*htab)[-2], j = hash32(name, len) % hsize;
  197.  
  198.     for (p = (*htab)[j]; p; p = p->next)
  199.       if (p->len == len && memcmp(p->name, name, len) == 0)
  200.         break;
  201.     if (!p && (p = (typeof(p))calloc(1, sizeof(*p) + len))) {
  202.       (*(ulong *)(*htab - 1))++; // incr items counter
  203.       p->next = (*htab)[j];
  204.       (*htab)[j] = p;
  205.       memcpy(p->name, name, p->len = len);
  206.     }
  207.   }
  208.  
  209.   return p;
  210. }
  211.  
  212. // удаляет элемент hashtable (если hashtable не было, создает пустую)
  213. static int
  214. del_htab (struct u_item **htab[], const char *name, int len)
  215. {
  216.   struct u_item *p = 0, **pp = 0;
  217.  
  218.   if (len > 0 && check_htab(htab)) {
  219.     ulong hsize = (ulong)(*htab)[-2], j = hash32(name, len) % hsize;
  220.  
  221.     for (p = (*htab)[j], pp = *htab + j; p; pp = &p->next, p = p->next)
  222.       if (len == p->len && memcmp(p->name, name, len) == 0) {
  223.         *pp = p->next;
  224.         (*(ulong *)(*htab - 1))--; // decr items counter
  225.         free(p);
  226.         return 1;
  227.       }
  228.   }
  229.  
  230.   return 0;
  231. }
  232.  
  233. /*********************************
  234.    calc interface to hashtables
  235. **********************************/
  236.  
  237. /*
  238.   печать hashtable в stdout для отладки или пустого любопытства
  239.   (act < 1 только статистика, иначе еще имена, а act > 1 и их double значения)
  240.   (вызывается для всех известных таблиц из calc() при str = "?";)
  241. */
  242. int
  243. calc_pristat (Symtab t[], int act)
  244. {
  245.   int rc = 0;
  246.  
  247.   if (t) {
  248.     long i, sz = (long)t[-2], n = (long)t[-1], nnz = 0, mx = 0;
  249.     printf("table: size=%ld count=%ld %c", sz, n, act > 0 ? '\n' : ' ');
  250.  
  251.     for (i = 0; i < sz; i++)
  252.       if (t[i]) {
  253.         nnz++;
  254.         int s = 0;
  255.         Symtab p;
  256.         for (p = t[i]; p; p = p->next) {
  257.             s++;
  258.             if (act) {
  259.                 char buf[p->len+1];
  260.                 memcpy(buf, p->name, p->len);
  261.                 buf[p->len] = 0;
  262.                 printf("%s ", buf);
  263.                 if (act > 1)
  264.                   printf("%g", p->v);
  265.                 printf("%c", p->next ? ' ' : '\n');
  266.           }
  267.         }
  268.         if (s > mx)
  269.           mx = s;
  270.       }
  271.       printf(" nnz=%ld mx=%ld\n", nnz, mx);
  272.       rc = 1;
  273.   }
  274.  
  275.   return rc;
  276. }
  277.  
  278. // удаляет таблицу со всеми элементами
  279. void
  280. calc_destroy_symtab (Symtab **htab)
  281. {
  282.   if (htab && *htab) {
  283.     struct u_item **t = *htab, *p;
  284.     ulong hsize = (ulong)t[-2], i;
  285.  
  286.     for (i = 0; i < hsize; i++)
  287.       while ((p = t[i])) {
  288.         t[i] = p->next;
  289.         free(p);
  290.       }
  291.  
  292.     free(t - 2);
  293.     *htab = 0;
  294.   }
  295. }
  296.  
  297. // удаляет таблицу с предопределенными функциями (чистит память за calc())
  298. void
  299. calc_free ()
  300. {
  301.   calc_destroy_symtab(&calc_fun);
  302. }
  303.  
  304.  
  305. // создает переменную или меняет значение существующей
  306. double *
  307. calc_set_var (Symtab **p, const char *name, int len, double v)
  308. {
  309.   struct u_item *pv = put_htab(p, name, len);
  310.  
  311.   if (pv)
  312.     pv->v = v;
  313.  
  314.   return pv ? &pv->v : 0;
  315. }
  316.  
  317. // доступ к значению существующей переменной
  318. double *
  319. calc_get_var (Symtab **p, const char *name, int len)
  320. {
  321.   struct u_item *pv = get_htab(p, name, len);
  322.  
  323.   return pv ? &pv->v : 0;
  324. }
  325.  
  326. // добавляет функцию или меняет указатель на нее
  327. function *
  328. calc_set_func (Symtab **p, const char *name, function f)
  329. {
  330.   //  struct u_item *pv = put_htab((struct u_item ***)p, name, len);
  331.   struct u_item *pv = put_htab(p, name, strlen(name));
  332.  
  333.   if (pv)
  334.     pv->f = f;
  335.  
  336.   return pv ? &pv->f : 0;
  337. }
  338.  
  339. // доступ к указателю на функцию
  340. function *
  341. calc_get_func (Symtab **p, const char *name, int len)
  342. {
  343.   struct u_item *pv = get_htab(p, name, len);
  344.  
  345.   return pv ? &pv->f : 0;
  346. }
  347.  
  348. // удаляет из таблицы переменную или функцию
  349. int
  350. calc_delsymb (Symtab **p, const char *name)
  351. {
  352.   return del_htab(p, name, strlen(name));
  353. }
  354.  
  355. // взять функцию из таблицы пользователя,
  356. //  если не нашли, то из предопределенных функций calc()
  357. static function *
  358. calc_get_function (Symtab *pcf, const char *name, int len)
  359. {
  360.   function *pf = pcf ? calc_get_func(&pcf, name, len) : 0;
  361.   if (!pf)
  362.     pf = calc_get_func(&calc_fun, name, len);
  363.  
  364.   return pf ? pf : 0;
  365. }
  366.  
  367. // инициализация таблицы предопределеных функций
  368. static void
  369. ini_func ()
  370. {
  371.   if (!calc_fun) {
  372.     int i;
  373.    
  374.     for (i = 0; i < (int)(sizeof(dfun) / sizeof(dfun[0])); i++)
  375.       calc_set_func(&calc_fun, dfun[i].name, dfun[i].f);
  376.   }
  377.    
  378. }
  379.  
  380. // для g++ [SYMB_INDEX] должны следовать строго по порядку
  381. static const char *msgs[] = {
  382.   [CALC_OK] = "success",
  383.   [CALC_OUT_OF_MEM] = "out of memory (Unbelivable, internal error?)",
  384.   [CALC_NO_OP] = "two operands without operation beetwen them",
  385.   [CALC_NO_VAL] = "operand expected, but found operation or ')'",
  386.   [CALC_NO_RP] = "unbalanced '('",
  387.   [CALC_NO_LP] = "unbalanced ')'",
  388.   [CALC_ERR_OP] = "Invalid operation in expr() (INTERNAL ERROR)",
  389.   [CALC_NO_NUMS] = "no operands for current operation (INTERNAL ERROR)",
  390.   [CALC_NUMS_ERR] = "at end operands stack depth too big (internal error?)",
  391.   [CALC_OPRS_ERR] = "at end operations left in stack (internal error?)",
  392.   [CALC_ERR_INPUT] = "invalid input char (letter, graph ...)",
  393.   [CALC_NO_FRP] = "unbalanced function '('",
  394.   [CALC_NO_INPUT] = "empty input",
  395.   [CALC_ERR_CODE] = "invalid error code (CALLER ERROR)",
  396.   [CALC_EOD] = "End Of Data",
  397.   [CALC_ARGS_ERR] = "too many function arguments",
  398.   [CALC_ASSG_ERR] = "assignment in middle of expression not implemented",
  399.   [CALC_COMMA_ERR] = "comma (`,`) not in function arguments list",
  400.   [CALC_NO_VAR] = "undefined variable",
  401.   [CALC_NO_FUNC] = "undefined function",
  402.   [CALC_ERR_PRTY] = "eval priority (INTERNAL ERROR)"
  403. };
  404.  
  405. // Получить текст сообщения по коду ошибки
  406. const char *
  407. calc_strerr (int code)
  408. {
  409.   if (code == EOF)
  410.     code = CALC_EOD;
  411.   if (code < 0 || code >= (int)(sizeof(msgs) / sizeof(msgs[0])))
  412.     code = CALC_ERR_CODE;
  413.  
  414.   return msgs[code];
  415. }
  416.  
  417. /****************************
  418.    Calc code
  419.  ***************************/
  420.  
  421. // это пробельные символы
  422. #define SPACES " \t\v\f\r\n"
  423. // предыдущая лексема была операцией?
  424. #define PREVOP(x) ((x) & 2)
  425. // следующий непробельный символ
  426. #define PEEKCHR(s, p) ({typeof(s) t = (s); t[(*p) = strspn(t, SPACES)];})
  427.  
  428. // макросы для работы со стеком
  429. #define INCR_STACK 100
  430.  
  431. // добавить память если требуется (Unbelievable)
  432. #define CORRECT_STACK(st) ({ int rc = 1;                \
  433.       if (!(st)->mem) {(st)->size = (st)->sp = 0;}          \
  434.       if ((st)->size == (st)->sp) {                 \
  435.     int s = sizeof(*((st)->mem)) * ((st)->size + INCR_STACK);   \
  436.     void *t = realloc((st)->mem, s);                \
  437.     if (!t)                             \
  438.       rc = 0;                           \
  439.     else {                              \
  440.       (st)->mem = (typeof((st)->mem))t; (st)->size += INCR_STACK;   \
  441.     }                               \
  442.       }                                 \
  443.       rc;                               \
  444.     })
  445.  
  446. #define PUSH(stack, v) ({int rc = CORRECT_STACK(stack); \
  447.       if (rc)                       \
  448.     (stack)->mem[(stack)->sp++] = v;        \
  449.       rc;                       \
  450.     })
  451.  
  452. #define TOP(stack) ({typeof(((stack)->mem)) v =  \
  453.     (stack)->mem && (stack)->sp ?         \
  454.     &(stack)->mem[(stack)->sp - 1] : 0; v;})
  455.  
  456. #define POP(stack) ({typeof(((stack)->mem)) v =  \
  457.     (stack)->mem && (stack)->sp ?         \
  458.     &(stack)->mem[--((stack)->sp)] : 0; v;})
  459.  
  460. #define EMPTY(stack) (!((stack)->mem && (stack)->sp))
  461.  
  462. #define CMPTOP(stack, v) (!EMPTY(stack) && *TOP(stack) == (v))
  463.  
  464.  
  465. /*
  466.    Берет следующую лексему, начиная с ctx->str[ctx->pos]
  467.    Returns ее код
  468.    (помещает double значение числа в ctx->result)
  469. */
  470. int
  471. calc_getlex (struct ucalc *ctx)
  472. {
  473.   int i = ctx->pos, // с этой точки начинаем поиск лексемы
  474.     op; // а это будет ее код
  475.   // организуем историю видов (операнд/операция) лексем
  476.   ctx->histop <<= 1;
  477.   ctx->prevop = ctx->curlex.type;
  478.  
  479.   // пропустим пробелы
  480.   if (!(ctx->str[i += strspn(ctx->str + ctx->pos, SPACES)])) {
  481.     ctx->pos = i;
  482.     return ctx->curlex.type = EOF;
  483.   }
  484.   ctx->pos = i + 1;    // начальная позиция для следующего вызова
  485.   ctx->curlex.pos = i; // начало лексемы
  486.   ctx->curlex.len = 1; // ее длина
  487.  
  488.   char *p;
  489.   // по текущему символу (`op`) определим тип лексемы
  490.   if ((p = (char *)strchr("+-*/(),", op = ctx->str[i]))) {
  491.     // это операция, уточним какая именно
  492.     if (op == '+' && PREVOP(ctx->histop))
  493.       op = 'P'; // unary `+`
  494.     else if (op == '-' && PREVOP(ctx->histop))
  495.       op = 'M'; // unary `-`
  496.     // а вот `)`  должна выглядеть как операнд для проверки на ошибки
  497.     ctx->histop |= (!(op == ')')); // занесем в историю вид лексемы
  498.   } else if (isdigit(op) || op == '.') { // число?
  499.     ctx->result = ctx->curlex.v = strtod(ctx->str + i, &p);
  500.     if (p != ctx->str + i) {
  501.       op = 'N';
  502.       ctx->pos = p - ctx->str; // обновим начальную позицию
  503.       ctx->curlex.len = ctx->pos - ctx->curlex.pos; // и длину лексемы
  504.     }
  505.   } else if (isalpha(op) || op == '_') { // идентификатор?
  506.     int l, c, j;
  507.     // пропустим допустимые для имени символы
  508.     for (l = ctx->pos; (c = ctx->str[l]) && (isalnum(c) || c == '_'); l++);
  509.     ctx->curlex.len = l - ctx->curlex.pos; // и обновим длину лексемы
  510.     op = 'V';
  511.     if ((c = PEEKCHR(ctx->str + l, &j)) == '=')
  512.       op = 'S'; // это оказывается присваивание переменной
  513.     else if (c == '(')
  514.       op = 'F'; // а если так, то обнаружили вызов функции
  515.  
  516.     ctx->histop |= (op != 'V'); // переменная это операнд, а остальное операция
  517.     ctx->pos = l + ((op == 'V') ? 0 : j + 1); // новая начальная позиция
  518.   } else
  519.     op = '?';
  520.  
  521.   ctx->curlex.type = op;
  522.   return op;
  523. }
  524.  
  525. /*
  526.   Выполним операцию с операндами из стека и поместим результат в стек
  527.   Returns 0 -- error or 1 -- OK
  528.  */
  529. static int
  530. expr (struct ucalc *ctx, int op)
  531. {
  532.   int n = op == 'M' ? 1 : 2; // число операндов для данной операции
  533.  
  534.   if (op != 'F' && ctx->nums.sp < n) // это не справедливо для вызова функции
  535.     return !(ctx->rc = CALC_NO_NUMS);
  536.  
  537.   switch (op) {
  538.   case '+':
  539.     ctx->result = ctx->nums.mem[ctx->nums.sp - 1] +
  540.       ctx->nums.mem[ctx->nums.sp - 2];
  541.     break;
  542.   case '-':
  543.     ctx->result = ctx->nums.mem[ctx->nums.sp - 2] -
  544.       ctx->nums.mem[ctx->nums.sp - 1];
  545.     break;      
  546.   case '*':
  547.     ctx->result = ctx->nums.mem[ctx->nums.sp - 1] *
  548.       ctx->nums.mem[ctx->nums.sp - 2];
  549.     break;
  550.   case '/':
  551.     ctx->result = ctx->nums.mem[ctx->nums.sp - 2] /
  552.       ctx->nums.mem[ctx->nums.sp - 1];
  553.     break;
  554.   case 'M':
  555.     ctx->result = -(ctx->nums.mem[ctx->nums.sp - 1]);
  556.     break;
  557.   case 'F':
  558.     { // вызов функции
  559.       // возможные аргументы, обнулим для -Wall
  560.       struct { double d0, d1, d2, d3, d4, d5, d6, d7, d8, d9; } a = {0};
  561.       int isp = ctx->funcs.sp - 1, // индекс функции в стеке функций
  562.     nsp = ctx->nums.sp;
  563.      
  564.       // перевычислим `n` -- число аргументов функции
  565.       if ((n = nsp - ctx->funcs.mem[isp].fsp) == 0 && !ctx->nums.mem) {
  566.     // и инициализируем стек операндов для вызова функции без аргументов
  567.     PUSH(&ctx->nums, 0);
  568.     POP(&ctx->nums);
  569.       }
  570.       if (n > 10)
  571.     return !(ctx->rc = CALC_ARGS_ERR);
  572.       switch (n - 1) { // скопируем аргументы из стека операндов
  573.       case 9:   a.d9 = ctx->nums.mem[--nsp];
  574.       case 8:   a.d8 = ctx->nums.mem[--nsp];
  575.       case 7:   a.d7 = ctx->nums.mem[--nsp];
  576.       case 6:   a.d6 = ctx->nums.mem[--nsp];
  577.       case 5:   a.d5 = ctx->nums.mem[--nsp];
  578.       case 4:   a.d4 = ctx->nums.mem[--nsp];
  579.       case 3:   a.d3 = ctx->nums.mem[--nsp];
  580.       case 2:   a.d2 = ctx->nums.mem[--nsp];
  581.       case 1:   a.d1 = ctx->nums.mem[--nsp];
  582.       case 0:   a.d0 = ctx->nums.mem[--nsp];
  583.       }
  584.       // выполним функцию
  585.       ctx->result = ctx->funcs.mem[isp].f(a.d0, a.d1, a.d2, a.d3,
  586.                       a.d4, a.d5, a.d6, a.d7, a.d8, a.d9);
  587.       // уберем функцию из стека функций
  588.       POP(&ctx->funcs);
  589.     }
  590.     break;
  591.     // internal error, unknown op
  592.   default:
  593.     return !(ctx->rc = CALC_ERR_OP);
  594.   }
  595.  
  596.   // поместим результат в новую вершину стека операндов
  597.   ctx->nums.mem[ctx->nums.sp - n] = ctx->result;
  598.   ctx->nums.sp -= (n - 1); // и скорректируем индекс вершины
  599.  
  600.   return 1;
  601. }
  602.  
  603. // Returns приоритет операции
  604. static int
  605. prty (int op)
  606. {
  607.   static char
  608.     oprs[] = "+-M*/(),F",
  609.     prio[] = "335441121";
  610.  
  611.   return op == EOF ? 0 : prio[strchr(oprs, op) - oprs] - '0';
  612. }
  613.  
  614.  
  615. /*
  616.   Выбираем и выполняем все операции из стека с приоритетом меньшим или
  617.   равным приоритету новой операции (ctx->curlex.type), затем помещаем ее в стек.
  618.   Закрывающая скобка, операция "запятая" (`,`) и EOF в стек не помещаются,
  619.   `)` и `,` вычисляют и удаляют из стека все операции до `(` или `F` на
  620.   вершине, `)` "аннигилирует" вместе с '(` или `F`,
  621.   EOF же, выполняя операции и обнаружив '(` или `F`, возвращает ошибку.
  622.  
  623.   Returns 0 -- error or 1 -- OK, last calculation result in ctx->result
  624.  */
  625. static int
  626. eval (struct ucalc *ctx)
  627. {
  628.   int op = ctx->curlex.type, p1 = prty(op);
  629.  
  630.   while (!EMPTY(&ctx->ops) && (p1  <= prty(*TOP(&ctx->ops)))) {
  631.     int top = *POP(&ctx->ops);
  632.     if (top == 'F' || top == '(') {
  633.       switch (op) {
  634.       case EOF:
  635.     return !(ctx->rc = (top == '(' ? CALC_NO_RP : CALC_NO_FRP)); // 0 - err
  636.       case ')':
  637.     return top == '(' ? 1 : expr(ctx, top);
  638.       default:
  639.     return !(ctx->rc = CALC_ERR_PRTY);
  640.       }
  641.     }
  642.  
  643.     if (!expr(ctx, top))
  644.       return 0;
  645.   }
  646.  
  647.   if (op == ')')
  648.     return !(ctx->rc = CALC_NO_LP);
  649.   if (op == ',')
  650.     return CMPTOP(&ctx->ops, 'F') ? 1 : !(ctx->rc = CALC_COMMA_ERR);
  651.   // поместим новую операцию в стек
  652.   if (op != EOF && !PUSH(&ctx->ops, op))
  653.     return !(ctx->rc = CALC_OUT_OF_MEM);
  654.  
  655.   return 1;
  656. }
  657.  
  658. /**
  659.  * calc --  Калькулятор арифметических выражений с переменными и функциями.
  660.  * @str:    IN    -- строка с выражением
  661.  * @pres:   OUT   -- указатель для результата вычисления
  662.  * @user:   INOUT -- указатель структуры (контекста выражения) с полями
  663.  *   .varlist IN  -- таблица переменных
  664.  *   .funlist IN  -- таблица функций
  665.  *   .reuslt  OUT -- результат вычисления
  666.  *   .rc      OUT -- код ошибки
  667.  *   .curlex  OUT -- последняя прочитанная лексема выражения
  668.  *                   (можно использовать при печати сообщения об ошибке)
  669.  * Returns: 0 -- успешное вычисление, иначе код ошибки @.rc или EOF (@str == 0)
  670.  */
  671. int
  672. calc (const char *str, double *pres, struct calc *user)
  673. {
  674.   if (!str)
  675.     return EOF;
  676.   ini_func(); // инициализация таблицы предопределенных функций
  677.   if (*str == '?') { // печать в stdout таблиц переменных и функций
  678.     fputs("variable ", stdout);
  679.     if (!calc_pristat(user ? user->varlist : 0, 2))
  680.       puts("");
  681.     fputs("user functions ", stdout);
  682.     if (!calc_pristat(user ? user->funlist : 0, 1))
  683.       puts("");
  684.  
  685.     return fputs("calc functions ", stdout), calc_pristat(calc_fun, 1), 0;
  686.   }
  687.  
  688.   struct ucalc ctx = {0}; // контекст вычисления выражения
  689.   ctx.str = str;
  690.   ctx.result = NAN;
  691.   if (pres)
  692.     *pres = NAN;
  693.   if (user)
  694.     user->result = NAN;
  695.   ctx.histop = 1; // моделируем, что предыдущая лексема была операцией
  696.  
  697.   int loop = 0,   // номер цикла, присваивание допустимо только для loop == 1
  698.     op; // тип лексемы
  699.   struct calc_lexem setlex = {0}; // лексема переменной оператора присваивания
  700.  
  701.   /*
  702.     Основной цикл вычисления.
  703.     Вычисляем до первой ошибки (ctx.rc != 0) или до конца выражения (op == EOF).
  704.     Алгоритм:
  705.       Берем очередную лексему.
  706.  
  707.       Операции `(`, M (унарный минус) и F (вызов функции) сразу помещаем
  708.       в стек операций, для остальных операций вызываем eval(),
  709.       которая выполняет операции с меньшим или равным приоритету текущей
  710.       операции из стека над операндами из стека операндов, а затем помещает
  711.       текущую операцию в стек.
  712.  
  713.       Операнды (числа и значения переменных) заносим в стек операндов.
  714.    */
  715.   while (ctx.rc == 0 && (op = calc_getlex(&ctx)) != EOF) {
  716.     loop++;
  717.     switch (op) {
  718.       // игнорируем унарный плюс
  719.     case 'P':
  720.       break;
  721.       // обрабатываем присваивание
  722.     case 'S':
  723.       if (loop == 1) // допустимо только в начале выражения
  724.     setlex = ctx.curlex;
  725.       else
  726.     ctx.rc = CALC_ASSG_ERR;
  727.       break;
  728.       // эти операции сразу в стек
  729.     case '(':
  730.     case 'F':
  731.       if (!PREVOP(ctx.histop)) {
  732.     ctx.rc = CALC_NO_OP;
  733.     break;
  734.       }
  735.       if (op == 'F') {
  736.     function *pf = calc_get_function(user ? user->funlist : 0,
  737.                      str + ctx.curlex.pos, ctx.curlex.len);
  738.     if (!pf) {
  739.       ctx.rc = CALC_NO_FUNC;
  740.       break;
  741.     }
  742.     // запомним атрибуты вызова функции (ее адрес и SP стека операндов)
  743.     struct fact fs = {*pf, ctx.nums.sp};
  744.     if(!PUSH(&ctx.funcs, fs))
  745.       ctx.rc = CALC_OUT_OF_MEM;
  746.       }
  747.     case 'M':
  748.       if(!PUSH(&ctx.ops, op))
  749.     ctx.rc = CALC_OUT_OF_MEM;
  750.       break;
  751.       // выполним операцию, eval() положит ее в стек
  752.     case ')':
  753.     case ',':
  754.     case '*':
  755.     case '/':
  756.       if (PREVOP(ctx.histop) && !(op == ')' && ctx.prevop == 'F')) {
  757.     ctx.rc = CALC_NO_VAL;
  758.     break;
  759.       }
  760.     case '+':
  761.     case '-':
  762.       eval(&ctx);
  763.       break;
  764.       // запомним операнд в стеке операндов
  765.     case 'V':
  766.       { // для переменной найдем ее значение
  767.     double *p = calc_get_var(user ? &user->varlist : 0,
  768.                  str + ctx.curlex.pos, ctx.curlex.len);
  769.     if (!p) {
  770.       ctx.rc = CALC_NO_VAR;
  771.       break;
  772.     }
  773.     ctx.result = *p;
  774.       }
  775.     case 'N':
  776.       if (!PREVOP(ctx.histop))
  777.     ctx.rc = CALC_NO_OP;
  778.       else if (!PUSH(&ctx.nums, ctx.result))
  779.       ctx.rc = CALC_OUT_OF_MEM;
  780.       break;
  781.       // прочли какой-то неизвестный символ
  782.     default:
  783.       ctx.rc = CALC_ERR_INPUT;
  784.     }
  785.   }
  786.  
  787.   if (!ctx.rc)  
  788.     eval(&ctx); // OK, вычислим все из стека
  789.  
  790.   // финальные проверки вроде бы безошибочного вычисления
  791.   if (!ctx.rc) {
  792.     if (ctx.nums.sp == 0 && ctx.ops.sp == 0)
  793.       ctx.rc = CALC_NO_INPUT; // на самом деле просто ничего не было
  794.     else if (ctx.nums.sp > 1)
  795.       ctx.rc = CALC_NUMS_ERR;
  796.     else if (ctx.ops.sp)
  797.       ctx.rc = CALC_OPRS_ERR;
  798.     else if (setlex.len && user && // и наконец, присваивание переменной
  799.          !calc_set_var(&user->varlist, str + setlex.pos, setlex.len,
  800.             ctx.result))
  801.       ctx.rc = CALC_OUT_OF_MEM;
  802.   }
  803.   free(ctx.nums.mem);
  804.   free(ctx.ops.mem);
  805.   free(ctx.funcs.mem);
  806.  
  807.   if (pres)
  808.     *pres = ctx.result;
  809.   if (user) {
  810.     user->curlex = ctx.curlex;
  811.     user->result = ctx.result;
  812.   }
  813.  
  814.   return ctx.rc;
  815. }
  816.  
  817. #ifdef STACK_TEST
  818. int
  819. main ()
  820. {
  821.   struct ucalc cx = {0};
  822.  
  823.   puts("test PUSH/TOP/POP/EMPTY");
  824.  
  825.   PUSH(&cx.ops, 'a');
  826.   PUSH(&cx.ops, 'a');
  827.   PUSH(&cx.ops, 'b');
  828.   PUSH(&cx.ops, 'c');
  829.   PUSH(&cx.ops, 0);
  830.  
  831.   double *dp = TOP(&cx.nums);
  832.   printf("empty top: %f\n",  dp ? *dp : NAN);
  833.   PUSH(&cx.nums, 9.8);
  834.   printf(" top: %f\n", *TOP(&cx.nums));
  835.   PUSH(&cx.nums, 3.14);
  836.   printf(" top: %f\n", *TOP(&cx.nums));
  837.   PUSH(&cx.nums, 2.87);
  838.   printf(" top: %f\n", *TOP(&cx.nums));
  839.  
  840.   int i;
  841.   for (i = cx.nums.sp - 1; i >= 0; i--)
  842.     printf("%f\n", cx.nums.mem[i]);
  843.  
  844.   puts(cx.ops.mem);
  845.   POP(&cx.ops);
  846.   while (!EMPTY(&cx.ops))
  847.     printf("pop: '%c'\n", *POP(&cx.ops));
  848.  
  849.   return puts("END test PUSH/TOP/POP/EMPTY") == EOF;
  850. }
  851. #endif
  852.  
  853. #ifdef LEXEM_TEST
  854. int
  855. main ()
  856. {
  857.   struct ucalc cx = {0};
  858.   char str[1000];
  859.   int op;
  860.  
  861.   puts("test getlex(), enter expressions, stop by ^D");
  862.   while (fputs("> ", stdout), fgets(str, 1000, stdin)) {
  863.     cx = (struct ucalc){0}; cx.str = str;
  864.     while (cx.rc == 0 && (op = calc_getlex(&cx)) != EOF)
  865.       printf("op: '%c'  pos: %d res: %f [%d %d]\n",
  866.          op, cx.pos, op == 'N' ? cx.result : NAN,
  867.          cx.curlex.pos, cx.curlex.len);
  868.     printf("Fin: op: %d  pos: %d\n", op, cx.pos);
  869.   }
  870.  
  871.   cx.str = "900"; cx.rc = cx.pos = 0;
  872.   while (cx.rc == 0 && (op = calc_getlex(&cx)) != EOF)
  873.     printf("Op: '%c'  pos: %d res: %f\n",
  874.        op, cx.pos, op == 'N' ? cx.result : NAN);
  875.   printf("Fin2: op: %d  pos: %d\n", op, cx.pos);
  876.  
  877.   return puts("End") == EOF;
  878. }
  879. #endif
  880.  
  881. #ifdef CALC_TEST
  882. // grad to radian
  883. static double rad (double g)
  884. {
  885.   return g / (360.0 / (2 * M_PI));
  886. }
  887.  
  888. // radian to grad
  889. static double grad (double r)
  890. {
  891.   return r * (360.0 / (2 * M_PI));
  892. }
  893.  
  894. static double drand()
  895. {
  896.   return rand() / (double)RAND_MAX;
  897. }
  898.  
  899.  
  900. int main ()
  901. {
  902.   struct calc cx = {0};
  903.   calc_set_func(&cx.funlist, "rad", (function)rad);
  904.   calc_set_func(&cx.funlist, "grad", (function)grad);
  905.   calc_set_func(&cx.funlist, "rand", (function)drand);
  906.   //  calc_pristat(cx.funlist, 1);
  907.  
  908.   char str[1000];
  909.   int rc = 0;
  910.  
  911. #if 1
  912.   puts("test calc1(), enter expressions, stop by ^D");
  913.   while (fputs("> ", stdout),
  914.      (rc = calc(fgets(str, 1000, stdin), 0, &cx)) != EOF) {
  915.     if (!rc)
  916.       printf("%.16g\n", cx.result);
  917.     else {
  918.       int i, l = strlen(str) - 1;
  919.       str[l] = 0;
  920.       puts(str);
  921.       for (i = 0; i < l; i++)
  922.     if (i == cx.curlex.pos) {
  923.       putchar('^'); break;
  924.     } else
  925.       putchar(isspace(str[i]) ? str[i] : ' ');
  926.       printf("  %s\n", calc_strerr(rc));
  927.       str[l] = '\n';
  928.     }
  929. #if 0
  930.     printf("`%s` rc = %d result = %.16g [t: %d '%c' p: %d l: %d] %s\n",
  931.        cx.str, rc, cx.result,
  932.        cx.curlex.type, cx.curlex.type, cx.curlex.pos, cx.curlex.len,
  933.        calc_strerr(rc));
  934. #endif
  935.   }
  936. #endif
  937.  
  938.   calc_destroy_symtab(&cx.varlist);
  939.   calc_destroy_symtab(&cx.funlist);
  940.   calc("?", 0, 0);
  941.   calc_free();
  942.   puts("Final");
  943.   return puts(calc_strerr(rc)) == EOF;
  944. }
  945. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top