home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Applications / RTrace 1.0 / source / interp_equation.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-09-09  |  21.0 KB  |  708 lines  |  [TEXT/KAHL]
  1. /*****************************************************************************\
  2. * interp_equation.c                                                           *
  3. *                                                                             *
  4. * This file contains code which implements a general-purpose equation         *
  5. * interpreter.  Given an equation string, it can return a floating point      *
  6. * which is the evaluated numeric value of the equation.                       *
  7. \*****************************************************************************/
  8.  
  9. #include <stdlib.h>
  10. #include <string.h>
  11. #include <ctype.h>
  12. #include <math.h>
  13. #include "interp_equation.h"
  14.  
  15.  
  16. /* error codes */
  17. enum
  18.     {
  19.     NO_ERROR = 0,
  20.     INVALID_NUMBER,
  21.     UNKNOWN_FUNCTION,
  22.     MISSING_RIGHT_PARENTHESIS,
  23.     INVALID_VARIABLE
  24.     };
  25.  
  26.  
  27. /* error messages */
  28. char *error_messages[] = 
  29.     {
  30.     "No error",                        /* NO_ERROR */
  31.     "Invalid number format",        /* INVALID_NUMBER */
  32.     "Unknown function",                /* UNKNOWN_FUNCTION */
  33.     "Missing right parenthesis",    /* MISSING_RIGHT_PARENTHESIS */
  34.     "Unknown variable"                /* INVALID_VARIABLE */
  35.     };
  36.  
  37.  
  38. /* built-in functions */
  39. char *built_in_functions[] =
  40.     {
  41.     "sin",
  42.     "cos",
  43.     "tan",
  44.     "exp",
  45.     "sqrt",
  46.     "abs",
  47.     "ln",
  48.     "log",
  49.     "int",
  50.     "atan",
  51.     "acos",
  52.     "asin",
  53.     "cosh",
  54.     "sinh",
  55.     "tanh"
  56.     };
  57.  
  58. enum
  59.     {
  60.     SIN = 0,
  61.     COS,
  62.     TAN,
  63.     EXP,
  64.     SQRT,
  65.     ABS,
  66.     LN,
  67.     LOG,
  68.     INT,
  69.     ATAN,
  70.     ACOS,
  71.     ASIN,
  72.     COSH,
  73.     SINH,
  74.     TANH
  75.     };
  76.  
  77. /* Globals */
  78. variable_value_proc var_proc;
  79.  
  80. /* Prototypes */
  81. short get_expression_value(char **expression, double *sum);
  82. short get_addend_value(char **addend, double *product);
  83. short get_factor_value(char **factor, double *power_fact);
  84. short get_power_factor_value(char **power_factor, double *value);
  85. short get_variable_or_function_value(char **name, double *value);
  86. short get_number(char **number, double *value);
  87.  
  88.  
  89. /*****************************************************************************\
  90. *                                                                             *
  91. * Terminology:                                                                *
  92. *                                                                             *
  93. *   An expression is a string of characters which make up a mathematical      *
  94. *   expression.  Expressions may contain any valid mathematical construction. *
  95. *                                                                             *
  96. *   An addend is like an expression, but it may not contain + or -            *
  97. *                                                                             *
  98. *   A factor is like an addend, but it may not contain * or /                 *                                                                          *
  99. *                                                                             *
  100. *   A power factor is like a factor, but it may not contain ^.  Anything in   *
  101. *   parentheses is considered a power factor, even if it contains ^.  Any     *
  102. *   standard function like sin or tan is also a power factor.                 *
  103. *                                                                             *
  104. * Examples:                                                                   *
  105. *                                                                             *
  106. *   Expressions:   a+2, b*7, (2+5)*67, x^2-2*x+5, y                           *
  107. *   Addends:       a*2, 23/7, x^2+5, 3                                        *
  108. *   Factors:       5, a, x^y                                                  *
  109. *   Power Factors: 8, x, (x-3), ((65-y)*x)), (x-2)^12, (x^2), sin(x), cos(4)  *
  110. *                                                                             *
  111. \*****************************************************************************/
  112.  
  113.  
  114.  
  115. /*****************************************************************************\
  116. * procedure evaluate_equation                                                 *
  117. *                                                                             *
  118. * Purpose: This procedure takes a string containing a mathematical expression *
  119. *          and evaluates it, returning the floating point value.              *
  120. *                                                                             *
  121. * Parameters: expression: the string expression to evaluate                   *
  122. *             value:      receives the value of the expression                *
  123. *             proc:       called when a variable is encountered.  This        *
  124. *                         procedure should set its second parameter (a        *
  125. *                         double) to the value of the variable whose name is  *
  126. *                         the first parameter (a string).  It should return a *
  127. *                         zero if there were no problems, or non-zero if the  *
  128. *                         variable name was invalid.                          *
  129. *             returns error code.                                             *
  130. *                                                                             *
  131. * Created by: Greg Ferrar                                                     *
  132. * Created on: September 9, 1992                                               *
  133. * Modified:                                                                   *
  134. \*****************************************************************************/
  135.  
  136. short evaluate_equation(char *expression, double *value, variable_value_proc proc)
  137. {
  138.  
  139.     short    i;
  140.     short    error;
  141.     char    temp_string[255];
  142.     char    *expression_ptr = expression;
  143.     
  144.     /* Save the variable value procedure pointer in a global */
  145.     var_proc = proc;
  146.     
  147.     /* Save the expression string */
  148.     strcpy(temp_string, expression);    
  149.  
  150.     /* Convert the equation to lower case, and strip all spaces */
  151.     i = 0;
  152.     while (expression[i])
  153.         {
  154.         
  155.         /* Convert this character to lower case */
  156.         expression[i] = tolower(expression[i]);
  157.         
  158.         if (expression[i] == ' ')
  159.             strcpy (expression + i, expression + i + 1);
  160.         else
  161.             i++;
  162.         }
  163.  
  164.     /* Find the value of this equation, catch error if any */
  165.     error = get_expression_value(&expression_ptr, value);
  166.  
  167.     /* Restore the original expression string */
  168.     strcpy(expression, temp_string);    
  169.  
  170.     return error;
  171.     
  172. }    /* evaluate_equation() */
  173.  
  174.  
  175.  
  176. /*****************************************************************************\
  177. * procedure get_error_message                                                 *
  178. *                                                                             *
  179. * Purpose: This procedure takes an error code, as returned by                 *
  180. *          evaluate_equation, and returns a error message string.             *
  181. *                                                                             *
  182. * Parameters: error: the error code.                                          *
  183. *             returns error message string.                                   *
  184. *                                                                             *
  185. * Created by: Greg Ferrar                                                     *
  186. * Created on: September 9, 1992                                               *
  187. * Modified:                                                                   *
  188. \*****************************************************************************/
  189.  
  190. char *get_error_message(short error)
  191. {
  192.  
  193.     /* return the error message */
  194.     return (error_messages[error]);
  195.  
  196. }    /* get_error_message() */
  197.  
  198.  
  199. /*****************************************************************************\
  200. * procedure get_expression_value                                              *
  201. *                                                                             *
  202. * Purpose: This procedure takes a handle to a string containing an expression *
  203. *          and evaluates it, returning the floating point value.              *
  204. *                                                                             *
  205. * Parameters: expression: handle to expression, after execution handle to     *
  206. *                         character after expression.                         *
  207. *             returns floating point value of expression                      *
  208. *                                                                             *
  209. * Created by: Greg Ferrar                                                     *
  210. * Created on: September 9, 1992                                               *
  211. * Modified:                                                                   *
  212. \*****************************************************************************/
  213.  
  214. short get_expression_value(char **expression, double *sum)
  215. {
  216.  
  217.     char    operator;
  218.     double    addend;
  219.     short    error;
  220.     Boolean    done = FALSE;
  221.     
  222.     /* Find the value of the first addend, trap error */
  223.     if (error = get_addend_value(expression, sum))
  224.         return error;
  225.  
  226.     while (!done)
  227.         {
  228.         
  229.         /* Get the operator */
  230.         operator = **expression;
  231.         
  232.         /* Perform the operation */
  233.         switch (operator)
  234.             {
  235.             case '+':
  236.             
  237.                 /* Move pointer to token after * */
  238.                 (*expression)++;
  239.                 
  240.                 /* Get next factor, pass along error if any */
  241.                 if (error = get_addend_value(expression, &addend))
  242.                     return error;
  243.                 
  244.                 /* Add it to the partial sum */
  245.                 *sum += addend;
  246.                 
  247.                 break;
  248.             
  249.             case '-':
  250.             
  251.                 /* Move pointer to token after * */
  252.                 (*expression)++;
  253.                 
  254.                 /* Get next factor, pass along error if any */
  255.                 if (error = get_addend_value(expression, &addend))
  256.                     return error;
  257.                 
  258.                 /* Subtract it from the partial sum */
  259.                 *sum -= addend;
  260.                 
  261.                 break;
  262.             
  263.             default:
  264.                 done = TRUE;
  265.                 
  266.             }
  267.         }
  268.  
  269.     /* no error */
  270.     return NO_ERROR;
  271.  
  272. }    /* get_expression_value() */
  273.  
  274.  
  275.  
  276. /*****************************************************************************\
  277. * procedure get_addend_value                                                  *
  278. *                                                                             *
  279. * Purpose: This procedure takes a handle to a string containing an addend and *
  280. *          evaluates it, returning the floating point value.                  *
  281. *                                                                             *
  282. * Parameters: addend: handle to addend, after execution handle to             *
  283. *                     character after addend.                                 *
  284. *             returns floating point value of addend                          *
  285. *                                                                             *
  286. * Created by: Greg Ferrar                                                     *
  287. * Created on: September 9, 1992                                               *
  288. * Modified:                                                                   *
  289. \*****************************************************************************/
  290.  
  291. short get_addend_value(char **addend, double *product)
  292. {
  293.  
  294.     char    operator;
  295.     double    factor;
  296.     short    error;
  297.     Boolean    done = FALSE;
  298.     
  299.     /* Find the value of the first factor, trap error */
  300.     if (error = get_factor_value(addend, product))
  301.         return error;
  302.  
  303.     while (!done)
  304.         {
  305.         
  306.         /* Get the operator */
  307.         operator = **addend;
  308.         
  309.         /* Perform the operation */
  310.         switch (operator)
  311.             {
  312.             case '*':
  313.                 
  314.                 /* Move pointer to token after * */
  315.                 (*addend)++;
  316.                 
  317.                 /* Get next factor, pass along error if any */
  318.                 if (error = get_factor_value(addend, &factor))
  319.                     return error;
  320.                 
  321.                 /* Multiply it with the partial product */
  322.                 *product *= factor;
  323.                 
  324.                 break;
  325.             
  326.             case '/':
  327.                 
  328.                 /* Move pointer to token after * */
  329.                 (*addend)++;
  330.                 
  331.                 /* Get next factor, pass along error if any */
  332.                 if (error = get_factor_value(addend, &factor))
  333.                     return error;
  334.                 
  335.                 /* Divide the partial product by the factor */
  336.                 *product /= factor;
  337.                 
  338.                 break;
  339.             
  340.             default:
  341.                 done = TRUE;
  342.                 
  343.             }
  344.         }
  345.     
  346.     return (NO_ERROR);
  347.  
  348. }    /* get_addend_value() */
  349.  
  350.  
  351.  
  352. /*****************************************************************************\
  353. * procedure get_factor_value                                                  *
  354. *                                                                             *
  355. * Purpose: This procedure takes a pointer to a containing a factor and        *
  356. *          evaluates it, returning the floating point value.                  *
  357. *                                                                             *
  358. * Parameters: factor: handle to factor, after execution handle to             *
  359. *                     character after factor.                                 *
  360. *             returns floating point value of factor                          *
  361. *                                                                             *
  362. * Created by: Greg Ferrar                                                     *
  363. * Created on: September 9, 1992                                               *
  364. * Modified:                                                                   *
  365. \*****************************************************************************/
  366.  
  367. short get_factor_value(char **factor, double *total)
  368. {
  369.  
  370.     double    power_fact;
  371.     char    operator;
  372.     short    error;
  373.     Boolean    done = FALSE;
  374.     
  375.     /* Find the value of the first power factor, trap error */
  376.     if (error = get_power_factor_value(factor, total))
  377.         return error;
  378.  
  379.     while (!done)
  380.         {
  381.         
  382.         /* Get the operator */
  383.         operator = **factor;
  384.         
  385.         /* Perform the operation */
  386.         switch (operator)
  387.             {
  388.             case '^':
  389.                 
  390.                 /* Move pointer to token after * */
  391.                 (*factor)++;
  392.                 
  393.                 /* Get next factor, pass along error if any */
  394.                 if (error = get_power_factor_value(factor, &power_fact))
  395.                     return error;
  396.                 
  397.                 /* Raise the partial result to the power_fact power */
  398.                 *total = pow(*total, power_fact);
  399.                 
  400.                 break;
  401.             
  402.             default:
  403.                 
  404.                 done = TRUE;
  405.                 
  406.             }
  407.         }
  408.         
  409.     return (NO_ERROR);
  410.  
  411. }    /* get_factor_value() */
  412.  
  413.  
  414.  
  415. /*****************************************************************************\
  416. * procedure get_power_factor_value                                            *
  417. *                                                                             *
  418. * Purpose: This procedure takes a pointer to a containing a power factor and  *
  419. *          evaluates it, returning the floating point value.                  *
  420. *                                                                             *
  421. * Parameters: base: handle to power factor, after execution handle to         *
  422. *                   character after power factor.                             *
  423. *             returns floating point value of power factor                    *
  424. *                                                                             *
  425. * Created by: Greg Ferrar                                                     *
  426. * Created on: September 9, 1992                                               *
  427. * Modified:                                                                   *
  428. \*****************************************************************************/
  429.  
  430. short get_power_factor_value(char **power_factor, double *value)
  431. {
  432.     
  433.     short    error;
  434.     
  435.     /* If the first token is a parenthesis, evaluate the expression inside */
  436.     if (**power_factor == '(')
  437.         {
  438.         
  439.         /* evaluate the expression right after the left parenthesis */
  440.         (*power_factor)++;
  441.         if (error = get_expression_value(power_factor, value))
  442.             return error;
  443.         
  444.         /* Skip the ) */
  445.         if (**power_factor != ')')
  446.             return MISSING_RIGHT_PARENTHESIS;
  447.         else
  448.             (*power_factor)++;
  449.  
  450.         
  451.         }
  452.  
  453.     /* Not a parenthesis-- is it a variable or a function? */
  454.     else if (isalpha(**power_factor) || (**power_factor == 'π'))
  455.         {
  456.         if (error = get_variable_or_function_value(power_factor, value))
  457.             return error;
  458.         }
  459.         
  460.     /* It must be a number */
  461.     else
  462.         {
  463.         
  464.         /* Convert it to a floating point number, trap error */
  465.         if (error = get_number(power_factor, value))
  466.             return error;
  467.     
  468.         }    
  469.  
  470.     return (NO_ERROR);
  471.  
  472. }    /* get_power_factor_value() */
  473.  
  474.  
  475.  
  476. /*****************************************************************************\
  477. * procedure get_variable_or_function_value                                    *
  478. *                                                                             *
  479. * Purpose: This procedure takes a pointer to a variable name or a function    *
  480. *          name, and returns the value of that variable or the function.      *
  481. *                                                                             *
  482. * Parameters: name: handle to variable/function name.                         *
  483. *             returns floating point value of variable/function               *
  484. *                                                                             *
  485. * Created by: Greg Ferrar                                                     *
  486. * Created on: September 9, 1992                                               *
  487. * Modified:                                                                   *
  488. \*****************************************************************************/
  489.  
  490. short get_variable_or_function_value(char **name, double *value)
  491. {
  492.  
  493.     char    *var_name = *name;    /* find start of the name */
  494.     short    error;
  495.     char    next_token;
  496.     short    i;
  497.  
  498.     /* find the end of the name */
  499.     while (isalnum(**name) || (**name == 'π'))
  500.         (*name)++;
  501.         
  502.     /* Remember the token after the name */
  503.     next_token = **name;
  504.     
  505.     /* Change the token after the name to an end-of-string token */
  506.     **name = '\0';
  507.  
  508.     /* If the next token is a (, this must be a function */
  509.     if (next_token == '(')
  510.         {
  511.         
  512.         /* Move to the token after the ( */
  513.         (*name)++;
  514.  
  515.         /* Find which built-in function it is */
  516.         i = SIN;
  517.         for (i = SIN; i <= TANH; i++)
  518.             if (!strcmp(var_name, built_in_functions[i]))
  519.                 break;
  520.  
  521.         /* If it's not a valid function, generate an error */
  522.         if (i > TANH)
  523.             return (UNKNOWN_FUNCTION);
  524.         
  525.         /* Get the value of the expression in the parentheses, check error */
  526.         if (error = get_expression_value(name, value))
  527.             return error;
  528.  
  529.         /* apply the function to the expression */
  530.         switch (i)
  531.             {
  532.             case SIN:
  533.                 *value = sin(*value);
  534.                 break;
  535.  
  536.             case COS:
  537.                 *value = cos(*value);
  538.                 break;
  539.  
  540.             case TAN:
  541.                 *value = tan(*value);
  542.                 break;
  543.  
  544.             case EXP:
  545.                 *value = exp(*value);
  546.                 break;
  547.  
  548.             case SQRT:
  549.                 *value = sqrt(*value);
  550.                 break;
  551.  
  552.             case ABS:
  553.                 *value = abs(*value);
  554.                 break;
  555.  
  556.             case LN:
  557.                 *value = log(*value);
  558.                 break;
  559.  
  560.             case LOG:
  561.                 *value = log10(*value);
  562.                 break;
  563.  
  564.             case INT:
  565.                 *value = floor(*value);
  566.                 break;
  567.  
  568.             case ATAN:
  569.                 *value = atan(*value);
  570.                 break;
  571.  
  572.             case ACOS:
  573.                 *value = acos(*value);
  574.                 break;
  575.  
  576.             case ASIN:
  577.                 *value = asin(*value);
  578.                 break;
  579.  
  580.             case COSH:
  581.                 *value = cosh(*value);
  582.                 break;
  583.  
  584.             case SINH:
  585.                 *value = sinh(*value);
  586.                 break;
  587.  
  588.             case TANH:
  589.                 *value = tanh(*value);
  590.                 break;
  591.             }
  592.  
  593.         /* Skip the ) */
  594.         if (**name != ')')
  595.             return MISSING_RIGHT_PARENTHESIS;
  596.         else
  597.             (*name)++;
  598.  
  599.         }
  600.     
  601.     else    /* it's a variable */
  602.         {
  603.         
  604.         /* check for pi */
  605.         if ((!strcmp(var_name, "pi")) || (!strcmp(var_name, "π")))
  606.             *value = 3.14159265358979323846;
  607.         
  608.         /* check for e */
  609.         else if (!strcmp(var_name, "e"))
  610.             *value = 2.71828182846;
  611.         
  612.         /* otherwise, request the value from the caller */
  613.         else if ((*var_proc)(var_name, value))
  614.             return INVALID_VARIABLE;
  615.         
  616.         /* Restore the token after the name */
  617.         **name = next_token;
  618.     
  619.         }
  620.  
  621.     /* Return error, if any */
  622.     return NO_ERROR;
  623.  
  624. }    /* get_variable_or_function_value() */
  625.  
  626.  
  627.  
  628. /*****************************************************************************\
  629. * procedure get_number                                                        *
  630. *                                                                             *
  631. * Purpose: This procedure gets the value of a number in the expression.       *
  632. *                                                                             *
  633. * Parameters: number_string: handle to number in the expression string.       *
  634. *             value:         receives floating point value of number          *
  635. *             returns error code                                              *
  636. *                                                                             *
  637. * Created by: Greg Ferrar                                                     *
  638. * Created on: September 9, 1992                                               *
  639. * Modified:                                                                   *
  640. \*****************************************************************************/
  641.  
  642. short get_number(char **number, double *value)
  643. {
  644.  
  645.     char    *number_string = *number;    /* find beginning of number */
  646.     char    next_token;
  647.     short    error;
  648.  
  649.     /* accept unary - at beginning */
  650.     if (**number == '-')
  651.         (*number)++;
  652.     
  653.     /* there should be a sequence of 0 or more digits next */
  654.     while (isdigit(**number))
  655.         (*number)++;
  656.     
  657.     /* next there could be a decimal point... */
  658.     if (**number == '.')
  659.         {
  660.         
  661.         /* Go to next token */
  662.         (*number)++;
  663.         
  664.         /* Read 0 or more digits after the decimal point */
  665.         while (isdigit(**number))
  666.             (*number)++;
  667.         
  668.         }
  669.     
  670.     /* next there could be an exponent */
  671.     if ((**number == 'e') || (**number == 'E'))
  672.         {
  673.         
  674.         /* Go to next token */
  675.         (*number)++;
  676.         
  677.         /* there could be an unary - before the exponent */
  678.         if (**number == '-')
  679.             (*number)++;
  680.  
  681.         /* Read 1 or more digits after the decimal point */
  682.         if (!isdigit(**number))
  683.             error = INVALID_NUMBER;
  684.         do
  685.             (*number)++;
  686.         while (isdigit(**number));
  687.         
  688.         }
  689.     
  690.     /* Save the token right after the number */
  691.     next_token = **number;
  692.     
  693.     /* Replace the token with end-of-string character */
  694.     **number = 0;
  695.  
  696.     /* Convert the number to a floating point number */
  697.     *value = atof(number_string);
  698.  
  699.     /* Restore the token */
  700.     **number = next_token;
  701.  
  702.     /* no error encountered */
  703.     return NO_ERROR;
  704.  
  705. }    /* get_number() */
  706.  
  707.  
  708.