home *** CD-ROM | disk | FTP | other *** search
/ Frozen Fish 1: Amiga / FrozenFish-Apr94.iso / bbs / alib / d0xx / d092 / parse.lha / Parse / parse.c next >
Encoding:
C/C++ Source or Header  |  1987-08-22  |  10.6 KB  |  410 lines
  1. /********************************************************************
  2.  * Parse.c (C) copyright 1987 John M. Olsen
  3.  *
  4.  * /|  |    /|||  /\|        |    John M. Olsen
  5.  * \|()|\|\_ |||. \/|/)@|\_    |    1547 Jamestown Drive
  6.  *  |                |    Salt Lake City, UT  84121-2051
  7.  * u-jmolse@ug.utah.edu  or  ...!{seismo,ihnp4}!utah-cs!utah-ug!u-jmolse
  8.  *
  9.  * This program or any significant portion of it may not be used in a
  10.  * commercial product without written permission of the author.  (My
  11.  * permission is easy to get).
  12.  *
  13.  * Feel free to distribute this code as part of any public domain collection,
  14.  * or hack on it to make it more user friendly, as long as you try to
  15.  * document your changes as not being my code.
  16.  *
  17.  * This is a recursive descent exprsession parser, based very loosely on one
  18.  * found in Herbert Schildt's book "Advanced C", published by McGraw-Hill.
  19.  * It parses expressions by having each layer either recognize something that
  20.  * it can do, or passing it on to the next function which does higher
  21.  * precedence operators.
  22.  *
  23.  * It has very minimal error checking, and does not check for overflow or
  24.  * underflow on calculations.  If it detects an error, it will give a message
  25.  * and what it thinks the correct result was up to that time.
  26.  *
  27.  * It converts expressions to lower case so it only needs to look for math
  28.  * function names spelled one way.
  29.  *
  30.  * It uses standard I/O, so it must be used from the CLI.  This makes it
  31.  * very easy to port to other machines.
  32.  *
  33.  * Aztec instructions using fast floating point:
  34.  *
  35.  * cc parse.c
  36.  * ln parse.o -lm -lc
  37.  *
  38.  * Aztec 4.30a using IEEE double precision floating point: (Big difference!)
  39.  *
  40.  * cc parse.c +fi
  41.  * ln parse.o -lmx -lc
  42.  *
  43.  * It has also been (fairly) successfully compiled on a VAX1180, but it
  44.  * complained at expressions on the argument list.  The only modification
  45.  * required was to comment out the #include <functions.h> command.
  46.  *
  47.  *********************************************************************/
  48.  
  49. #include <stdio.h>
  50. #include <ctype.h>
  51. #include <functions.h>
  52. #include <math.h>
  53.  
  54. #define PI ((double)3.14159265358979)
  55. #define E  ((double)2.71828182845904)
  56.  
  57. #define TOK_SIZE 20    /* Tokens are no longer than this number. */
  58. #define EXP_SIZE 80    /* Expressions no longer than this number. */
  59.  
  60. #define TRUE 1
  61. #define FALSE 0
  62.  
  63. extern double atof(), binary(), fn_eval();
  64. extern double parse(), parse2(), parse3(), parse4(), parse5();
  65.  
  66. /* Here is a simple calling program to test it. */
  67.  
  68. main (argc, argv)
  69. int argc;
  70. char *argv[];
  71. {
  72.     char exprs[EXP_SIZE];
  73.     double ans;
  74.     int loop;
  75.  
  76.     if(argc < 2)
  77.     {
  78.         ans = 0;
  79.         printf("Type '?' for help.\n");
  80.         printf("Enter exprsression: ");
  81.         gets (exprs);
  82.     }
  83.     else
  84.     {
  85.         exprs[0] = NULL;
  86.         for(loop = 1; loop < argc; loop++)
  87.             strcat(exprs, argv[loop]);
  88.     }
  89.     for(loop = 0; loop < strlen(exprs); loop++) /* convert to lower case */
  90.         if(isalpha(exprs[loop]))
  91.             exprs[loop] = tolower(exprs[loop]);
  92.     if(exprs[0] == '?' || exprs[0] == 'h')
  93.     {    /* help menu */
  94.         printf("Supported binary operators: + - / % ^\n");
  95.         printf("Supported unary operators:  + -\n");
  96.         printf("Supported unary functions:  sin, cos, tan,\n");
  97.         printf("    asin, acos, atan, sinh, cosh, tahn,\n");
  98.         printf("    log, logten, abs, sqrt, int.\n");
  99.         printf("Defined constants:          pi, e.\n\n");
  100.         printf("Usage: %s (expression)\n", argv[0]);
  101.         printf("   or: %s ?\n", argv[0]);
  102.         exit(0);
  103.     }
  104.     ans = parse (exprs);
  105.     if(exprs[0])
  106.         printf("Bad expression.\n");
  107.     else
  108.         printf ("%f\n", ans);
  109. }
  110.  
  111. /*******************************************************************
  112. The main parser function. It parses + and -.
  113. *******************************************************************/
  114. double parse (exprs)
  115. char exprs[];
  116. {
  117.     char tok[TOK_SIZE];    /* this should only be a + or - character. */
  118.     double a;
  119.  
  120.     a = parse2 (exprs);
  121.     while (exprs[0])
  122.     {
  123.         get_token (tok, exprs);
  124.         if (tok[0] == '+' || tok[0] == '-')
  125.             a = binary (a, parse2 (exprs), tok);
  126.         else
  127.             return (a);
  128.     }
  129.     return (a);
  130. }
  131.  
  132. /*******************************************************************
  133. The secondary parser, which parses * and /.
  134. *******************************************************************/
  135. double parse2 (exprs)
  136. char *exprs;
  137. {
  138.     char tok[TOK_SIZE];
  139.     double a;
  140.  
  141.     a = parse3 (exprs);
  142.     while (exprs[0])
  143.     {
  144.         get_token (tok, exprs);
  145.         if (tok[0] == '*' || tok[0] == '/' || tok[0] == 'm'
  146.                      || tok[0] == 'd')
  147.             a = binary (a, parse3 (exprs), tok);
  148.         else
  149.         {
  150.             unget_tok (tok, exprs);
  151.             return (a);
  152.         }    
  153.     }
  154.     return (a);
  155. }
  156.  
  157. /*******************************************************************
  158. The third parser, which parses ^.
  159. *******************************************************************/
  160. double parse3 (exprs)
  161. char *exprs;
  162. {
  163.     char tok[TOK_SIZE];
  164.     double a;
  165.  
  166.     a = parse4 (exprs);
  167.     while (exprs[0])
  168.     {
  169.         get_token (tok, exprs);
  170.         if (tok[0]=='^')
  171.             a = (binary (a, parse4 (exprs), tok));
  172.         else
  173.         {
  174.             unget_tok (tok, exprs);
  175.             return (a);
  176.         }    
  177.     }
  178.     return (a);
  179. }
  180.  
  181. /*******************************************************************
  182. The fourth parser, which parses unary minus and plus.
  183. *******************************************************************/
  184. double parse4 (exprs)
  185. char *exprs;
  186. {
  187.     char tok[TOK_SIZE];
  188.  
  189.     get_token (tok, exprs);
  190.     if (tok[0] == '-')
  191.         return (-(parse4 (exprs)));
  192.     else if(tok[0] == '+')
  193.         return(parse4(exprs));
  194.     unget_tok (tok, exprs);
  195.     return (parse5 (exprs));
  196. }
  197.  
  198. /*******************************************************************
  199. The fifth parser, which parses functions and parentheses.
  200. *******************************************************************/
  201. double parse5 (exprs)
  202. char *exprs;
  203. {
  204.     char tok[TOK_SIZE], buff[EXP_SIZE];
  205.     double a;
  206.  
  207.     get_fn (tok, exprs);
  208.     if (tok[0])    /* a function call. */
  209.         return (fn_eval (tok, exprs));
  210.     get_numb (tok, exprs);
  211.     if (tok[0])    /* A number. */
  212.         return (atof (tok));
  213.     if (exprs[0] == '(')    /* a parenthesized exprsression. */
  214.     {    /*strip open paren, call parse, strip close paren. */
  215.         strcpy (buff, exprs + 1);
  216.         strcpy (exprs, buff);
  217.         a = parse (exprs);
  218.         if (exprs[0] == ')')
  219.         {
  220.             strcpy (buff, exprs + 1);
  221.             strcpy (exprs, buff);
  222.         }
  223.         else
  224.         {    /* Error if here. */
  225.             printf("Bad parentheses.\n");
  226.         }
  227.         return (a);
  228.     }
  229.     printf("Bad parentheses.\n");
  230. }
  231.  
  232. /*******************************************************************
  233. Return a pointer to a string with the token in it.  A token may be
  234. at most TOK_SIZE characters.  All after that are tossed into the
  235. bit bucket.
  236. *******************************************************************/
  237. get_token (tok, exprs)
  238. char *tok, *exprs;
  239. {
  240.     char temp[EXP_SIZE];
  241.  
  242.     tok[0] = 0;
  243.     while (iswhite (exprs[0]))    /* move from exprs[1] to exprs[0] */
  244.     {
  245.         strcpy (temp, exprs + 1);
  246.         strcpy (exprs, temp);
  247.     }
  248.     sscanf (exprs, "%1[+-*/^]", tok);
  249.     strcpy (temp, exprs + strlen (tok));
  250.     strcpy (exprs, temp);
  251. }
  252.  
  253. /*******************************************************************
  254. Get a number from the front of the exprsression.
  255. *******************************************************************/
  256. get_numb (tok, exprs)
  257. char *tok, *exprs;
  258. {
  259.     char temp[EXP_SIZE];
  260.  
  261.     tok[0] = 0;
  262.     while (iswhite (exprs[0]))    /* move from exprs[1] to exprs[0] */
  263.     {
  264.         strcpy (temp, exprs + 1);
  265.         strcpy (exprs, temp);
  266.     }
  267.     sscanf (exprs, "%[0123456789.]", tok);
  268.     strcpy (temp, exprs + strlen (tok));
  269.     strcpy (exprs, temp);
  270. }
  271. /*******************************************************************
  272. Get a function name from the front of the exprsression.
  273. *******************************************************************/
  274. get_fn (tok, exprs)
  275. char *tok, *exprs;
  276. {
  277.     char temp[EXP_SIZE];
  278.  
  279.     tok[0] = 0;
  280.     while (iswhite (exprs[0]))    /* move from exprs[1] to exprs[0] */
  281.     {
  282.         strcpy (temp, exprs + 1);
  283.         strcpy (exprs, temp);
  284.     }
  285.     sscanf (exprs, "%[abcdefghijklmnopqrstuvwxyz]", tok);
  286.     strcpy (temp, exprs + strlen (tok));
  287.     strcpy (exprs, temp);
  288. }
  289.  
  290. /*******************************************************************
  291. Replace a token at the front of the exprsression.
  292. *******************************************************************/
  293. unget_tok (tok, exprs)
  294. char *tok, *exprs;
  295. {
  296.     char buff[EXP_SIZE];
  297.  
  298.     strcpy (buff, exprs);
  299.     strcpy (exprs, tok);
  300.     strcat (exprs, buff);
  301. }
  302.  
  303. /*******************************************************************
  304. This fn returns true if the key given to it is white space.
  305. *******************************************************************/
  306. iswhite (key)
  307. char key;
  308. {
  309.     if (key == ' ' || key == 9 || key == 13)
  310.         return (1);
  311.     return (0);
  312. }
  313. /*******************************************************************
  314. This fn returns (a operator b), or just a if an error occurs.
  315. *******************************************************************/
  316. double binary (a, b, tok)
  317. double a, b;
  318. char *tok;
  319. {
  320.     int loop;
  321.     double c;
  322.  
  323.     switch (tok[0])
  324.     {
  325.         case '+':
  326.             return (a + b);
  327.         case '-':
  328.             return (a - b);
  329.         case '*':
  330.             return (a * b);
  331.         case '/':
  332.             if (!near_zero (b))    /* if b != 0 */
  333.                 return (a / b);
  334.             else
  335.             {    /* division by zero error message. */
  336.                 printf("Division by zero error.\n");
  337.             }
  338.             return (a);
  339.         case '^':    /* a to the b power. */
  340.         {
  341.             c = a;
  342.             if (near_zero (b))    
  343.                 return (a);
  344.             return(pow(a,b));
  345.             /* non-function if you don't like the pow function */
  346.             for (loop = (int) b - 1;loop > 0; --loop)
  347.                 a = a * c;
  348.             return (a);
  349.         }
  350.         default:
  351.             printf("No such token as %c\n", tok[0]);
  352.     }
  353. }
  354.  
  355. /*******************************************************************
  356. Evaluates the function on the front of exprs.
  357. *******************************************************************/
  358. double fn_eval (tok, exprs)
  359. char *exprs, *tok;
  360. {
  361.     if (tok[0])
  362.     {
  363.         if (!strcmp(tok, "abs"))
  364.             return(fabs (parse5(exprs)));
  365.         if (!strcmp(tok, "sqrt"))
  366.             return(sqrt (parse5(exprs)));
  367.         if (!strcmp(tok, "tan"))
  368.             return(tan (parse5(exprs)));
  369.         if (!strcmp(tok, "sin"))
  370.             return(sin (parse5(exprs)));
  371.         if (!strcmp(tok, "cos"))
  372.             return(cos (parse5(exprs)));
  373.         if (!strcmp(tok, "atan"))
  374.             return(atan (parse5(exprs)));
  375.         if (!strcmp(tok, "asin"))
  376.             return(asin (parse5(exprs)));
  377.         if (!strcmp(tok, "acos"))
  378.             return(acos (parse5(exprs)));
  379.         if (!strcmp(tok, "tanh"))
  380.             return(tanh (parse5(exprs)));
  381.         if (!strcmp(tok, "sinh"))
  382.             return(sinh (parse5(exprs)));
  383.         if (!strcmp(tok, "cosh"))
  384.             return(cosh (parse5(exprs)));
  385.         if (!strcmp(tok, "pi"))
  386.             return(PI);
  387.         if (!strcmp(tok, "e"))
  388.             return(E);
  389.         if (!strcmp(tok, "log"))
  390.             return(log(parse5(exprs)));
  391.         if (!strcmp(tok, "logten"))
  392.             return(log10(parse5(exprs)));
  393.         if (!strcmp(tok, "int"))
  394.             return((double)((long)(parse5(exprs))));
  395.     }
  396.     printf("Could not find expression %s\n",tok);
  397.     unget_tok(tok, exprs);
  398. }
  399.  
  400. /*******************************************************************
  401. Returns true if num is near zero. It's used in division checks.
  402. *******************************************************************/
  403. near_zero (num)
  404. double num;
  405. {
  406.     if (fabs (num) < .000000001)
  407.         return (1);
  408.     return (0);
  409. }
  410.