home *** CD-ROM | disk | FTP | other *** search
/ Power Programming / powerprogramming1994.iso / progtool / irit / drawfuns.arc / EXPR2TRE.C < prev    next >
C/C++ Source or Header  |  1989-07-29  |  48KB  |  1,458 lines
  1. /*****************************************************************************
  2. *   Module to convert infix expression given as    a string into a    binary tree. *
  3. * Evaluate trees, and make symbolic derivation of such trees.             *
  4. *                                         *
  5. * Main routines:                                 *
  6. * 1. ExprNode *Expr2Tree(s) - main routine to perform conversion.         *
  7. *    int ParserError()        - return error number (expr2trg.h), 0 o.k.         *
  8. * 2. PrintTree(Root, Str)   - routine to print in infix form content of tree *
  9. * 3. ExprNode *CopyTree(Root) - returns a new copy of root pointed tree.     *
  10. * 4. double EvalTree(Root)  - evaluate expression for a given t.         *
  11. *    int EvalError()        - return error number (expr2trg.h), 0 o.k.         *
  12. * 5. ExprNode *DerivTree(Root, Param) - returns new tree - its derivative    *
  13. *                according to parameter Param. Define         *
  14. *                    DERIVATIVE for the preprocessor for this     *
  15. *                routine (see Expr2TrG.h file).             *
  16. *    int DerivError()        - return error number (expr2trg.h), 0 o.k.         *
  17. *                  Also needs definition of DERIVATIVE.         *
  18. * 6. SetParamValue(Value, Number) - set that parameter value...             *
  19. *                                         *
  20. * In addition:                                     *
  21. * 7. int CmpTree(Root1, Root2) - compere symbolically two trees.         *
  22. * 8. int ParamInTree(Root, parameter) - return TRUE if parameter in tree.    *
  23. * 9. FreeTree(Root) - release memory allocated for tree    root.             *
  24. *                                         *
  25. *                                         *
  26. * Written by:  Gershon Elber                   ver 1.2,    June 1988    *
  27. *                                         *
  28. * Ver 0.2 modifications: replace old inc. notation (=+)    with new (+=).         *
  29. * Ver 0.3 modifications: parameter can be T or X (was only T).             *
  30. *             PrintTree(root, String) print the tree into String  *
  31. *             or to screen (as it was) if String address is null. *
  32. *             setparamchar(c) - set the parameter char, t default *
  33. * Ver 0.4 modifications: split expr2tre.h into local and globals consts.     *
  34. * Ver 1.0 modifications: multiple variables is now supported, meaning         *
  35. *             functions of few variables can    new be evaluated and *
  36. *             derivated!. Note that for some    of the functions,    *
  37. *             the parameter of them were modified/added.         *
  38. *             Now integer power of negative numbers is supported. *
  39. * Ver 1.1 modifications: minor changes,    added function definitions to the    *
  40. *             global    constant file -    expr2trg.h             *
  41. * Ver 1.2 modifications: add EvalError() function for div by zero error.     *
  42. * Ver 2.0 modifications: change the parser to operator preceedings.         *
  43. * Ver 2.1 modifications: adding min, max, and modulu (%) operators.         *
  44. *****************************************************************************/
  45.  
  46. #include <stdio.h>
  47. #include <ctype.h>
  48. #include <math.h>
  49. #include <string.h>
  50. #include <alloc.h>
  51. #include "Expr2TrG.h"
  52. #include "Expr2TrL.h"
  53.  
  54. static int GlblLastToken, GlblParsingError;       /* Globals used by parser */
  55. static int GlblEvalError;             /* Global used by eval_tree */
  56. static double GlobalParam[PARAMETER_Z1];     /* The parameters are save here */
  57. #ifdef DERIVATIVE
  58. static int GlblDerivError;               /* Global used by derivations */
  59. #endif DERIVATIVE
  60.  
  61. /*****************************************************************************
  62. *  Routine to return one expression node from free list    or allocate new    one: *
  63. *****************************************************************************/
  64. static ExprNode *MyExprMalloc(void)
  65. {
  66.     return (ExprNode *) malloc(sizeof(ExprNode));
  67. }
  68.  
  69. /*****************************************************************************
  70. *  Routine to return one expression node:                     *
  71. *****************************************************************************/
  72. static void MyExprFree(ExprNode *Ptr)
  73. {
  74.     free((char *) Ptr);
  75. }
  76.  
  77. /*****************************************************************************
  78. *  Routine to convert lower case chars into upper one in the given string:   *
  79. *****************************************************************************/
  80. static void MakeUpper(char *s)
  81. {
  82.     int    i = 0;
  83.  
  84.     while (s[i]    != NULL) {
  85.     if (islower(s[i])) s[i] = toupper(s[i]);
  86.     i++;
  87.     }
  88. }
  89.  
  90. /*****************************************************************************
  91. *   Routine to convert the expression in string S into a binary tree.        *
  92. * Algorithm: Using operator precedence with the following grammer:           *
  93. * EXPR    ::= EXPR    |  EXPR + EXPR    |  EXPR - EXPR                       *
  94. * EXPR    ::= EXPR    |  EXPR * EXPR    |  EXPR / EXPR                       *
  95. * EXPR    ::= EXPR    |  EXPR ^ EXPR                                         *
  96. * EXPR    ::= NUMBER  |  -EXPR          |  (EXPR)        |  FUNCTION         *
  97. * FUCTION ::= SIN(EXPR)       | COS(EXPR)       | TAN(EXPR) |             *
  98. *             ARCSIN(EXPR)    | ARCCOS(EXPR)    | ARCTAN(EXPR) |         *
  99. *             SQRT(EXPR)      | SQR(EXPR)       | ABS(EXPR) |             *
  100. *             LN(EXPR)        | LOG(EXPR)       | EXP(EXPR)             *
  101. *                                         *
  102. * And Left associativity for +, -, *, /, %, ^.                     *
  103. * Precedence of operators is as usual:                                       *
  104. *     <Highest> {unar minus}   {^}   {*, /, %, min, max}   {+, -} <Lowest>   *
  105. *                                         *
  106. * Returns NULL if an error was found, and error is in GlblParsingError       *
  107. *****************************************************************************/
  108. ExprNode *Expr2Tree(char *s)
  109. {
  110.     ExprNode *Root;
  111.     int i = 0;
  112.  
  113.     MakeUpper(s);
  114.     GlblLastToken = 0;         /* Used to hold last token read from stream */
  115.     GlblParsingError = 0;                 /* No errors so far ... */
  116.  
  117.     Root = OperatorPrecedence(s, &i);
  118.  
  119.     if (GlblParsingError) return (ExprNode *) NULL;          /* Error ! */
  120.     else return Root;
  121. }
  122.  
  123. /*****************************************************************************
  124. *   Routine to actually parse using operator precedence:                     *
  125. * Few Notes:                                                                 *
  126. * 1. Parse the string s with the help of GetToken routine. i holds current   *
  127. *    position in string s.                                                   *
  128. * 2. All tokens must be in the range of 0..999 as we use the numbers above   *
  129. *    it (adding 1000) to deactivate them in the handle searching (i.e. when  *
  130. *    they were reduced to sub.-expression).                                  *
  131. * 3. Returns NULL pointer in case of an error (see Expr2TrG.h for errors     *
  132. * 4. See "Compilers - principles, techniques and tools" by Aho, Sethi &      *
  133. *    Ullman,   pages 207-210.                                                *
  134. *****************************************************************************/
  135. static ExprNode *OperatorPrecedence(char *s, int *i)
  136. {
  137.     int Token, low_handle, Temp1, Temp2, StackPointer = 0, LoopOnEnd = 0;
  138.     double Data;
  139.     ExprNode *stack[MAX_PARSER_STACK];
  140.  
  141.     /* Push the start symbol on stack (node pointer points on tos): */
  142.     stack[StackPointer] = MyExprMalloc();
  143.     stack[StackPointer] -> NodeKind = TOKENSTART;
  144.     stack[StackPointer] -> Right =
  145.     stack[StackPointer] -> Left = (ExprNode *) NULL;
  146.     Token = GetToken(s, i, &Data); /* Get one look ahead token to start with */
  147.     do {
  148.     if (GlblParsingError) return (ExprNode *) NULL;
  149.     Temp1 = StackPointer;       /* Find top active token (less than 1000) */
  150.         while (stack[Temp1] -> NodeKind >= 1000) Temp1--;
  151.         /* Now test to see if the new token completes an handle: */
  152.         if (TestPreceeding(stack[Temp1] -> NodeKind, Token) > 0) {
  153.             switch (Token) {
  154.         case CLOSPARA:
  155.                     if (stack[Temp1] -> NodeKind == OPENPARA) {
  156.                         if (StackPointer-Temp1 != 1) {
  157.                             GlblParsingError = P_ERR_ParaMatch;
  158.                 return (ExprNode *) NULL;
  159.             }
  160.                         switch (stack[Temp1-1] -> NodeKind) {
  161.                 case ABS:     /* If it is of the form Func(Expr) */
  162.                 case ARCCOS:  /* Then reduce it directly to that */
  163.                 case ARCSIN:  /* function, else (default) reduce */
  164.                 case ARCTAN:  /* to sub-expression.              */
  165.                 case COS:
  166.                 case EXP:
  167.                 case LN:
  168.                 case LOG:
  169.                 case SIN:
  170.                 case SQR:
  171.                 case SQRT:
  172.                 case TAN:
  173.                 free(stack[Temp1]);  /* Free the open paran. */
  174.                 stack[StackPointer] -> NodeKind -= 1000;
  175.                 stack[Temp1-1] -> NodeKind += 1000;
  176.                     stack[Temp1-1] -> Right = stack[StackPointer];
  177.                 StackPointer -= 2;
  178.                 break;
  179.                 default:
  180.                 free(stack[Temp1]);  /* Free the open paran. */
  181.                                 stack[Temp1] = stack[StackPointer--];
  182.                 break;
  183.             }
  184.             Token = GetToken(s, i, &Data);    /* Get another token */
  185.                         continue;
  186.             }
  187.                     else if (stack[Temp1] -> NodeKind == TOKENSTART) {
  188.             /* No match for this one! */
  189.                         GlblParsingError = P_ERR_ParaMatch;
  190.             return (ExprNode *) NULL;
  191.             }
  192.             break;
  193.         case TOKENEND:
  194.             LoopOnEnd++;
  195.                     if (stack[Temp1] -> NodeKind == TOKENSTART) {
  196.                         if (StackPointer != 1) {
  197.                             GlblParsingError = P_ERR_WrongSyntax;
  198.                 return (ExprNode *) NULL;
  199.             }
  200.             stack[1] -> NodeKind -= 1000;
  201.             return stack[1];
  202.             }
  203.         }
  204.  
  205.         Temp2 = Temp1-1;           /* Find the lower bound of handle */
  206.             while (stack[Temp2] -> NodeKind >= 1000) Temp2--;
  207.             low_handle = Temp2 + 1;
  208.         if (low_handle < 1 ||           /* No low bound was found */
  209.         LoopOnEnd > 1000) {    /* We are looping on EOS for ever... */
  210.                 GlblParsingError = P_ERR_WrongSyntax;
  211.         return (ExprNode *) NULL;      /* We ignore data till now */
  212.             }
  213.         switch (StackPointer - low_handle + 1) {
  214.         case 1:        /* Its a scalar one - mark it as used (add 1000) */
  215.             switch (stack[StackPointer] -> NodeKind) {
  216.             case NUMBER:
  217.             case PARAMETER:
  218.                     stack[StackPointer] -> NodeKind += 1000;
  219.                 break;
  220.             default:
  221.                 GlblParsingError = P_ERR_ParamExpect;
  222.                 return (ExprNode *) NULL;
  223.             }
  224.             break;
  225.         case 2:          /* Its a monadic operator - create the subtree */
  226.             switch (stack[StackPointer-1] -> NodeKind) {
  227.                 case UNARMINUS:
  228.                     stack[StackPointer-1] -> Right =
  229.                                                         stack[StackPointer];
  230.                     stack[StackPointer] -> NodeKind -= 1000;
  231.                     stack[StackPointer-1] -> NodeKind += 1000;
  232.                     StackPointer --;
  233.                     break;
  234.                 case OPENPARA:
  235.                 GlblParsingError = P_ERR_ParaMatch;
  236.                 return (ExprNode *) NULL;
  237.                 default:
  238.                 GlblParsingError = P_ERR_OneOperand;
  239.                 return (ExprNode *) NULL;
  240.             }
  241.             break;
  242.         case 3:           /* Its a diadic operator - create the subtree */
  243.             switch (stack[StackPointer-1] -> NodeKind) {
  244.                 case PLUS:
  245.                 case MINUS:
  246.                 case MULT:
  247.                 case DIV:
  248.             case MODULU:
  249.             case MINIMUM:
  250.             case MAXIMUM:
  251.                 case POWER:
  252.                     stack[StackPointer-1] -> Right =
  253.                                   stack[StackPointer];
  254.                             stack[StackPointer-1] -> Left =
  255.                                   stack[StackPointer-2];
  256.                     stack[StackPointer-2] -> NodeKind -= 1000;
  257.                     stack[StackPointer] -> NodeKind -= 1000;
  258.                     stack[StackPointer-1] -> NodeKind += 1000;
  259.                     stack[StackPointer-2] = stack[StackPointer-1];
  260.                     StackPointer -= 2;
  261.                             break;
  262.                         default:
  263.                 GlblParsingError = P_ERR_TwoOperand;
  264.                 return (ExprNode *) NULL;
  265.             }
  266.             break;
  267.         }
  268.         }
  269.     else {          /* Push that token on stack - it is not handle yet */
  270.         stack[++StackPointer] = MyExprMalloc();
  271.             if (StackPointer == MAX_PARSER_STACK-1) {
  272.                 GlblParsingError = P_ERR_StackOV;
  273.         return (ExprNode *) NULL;      /* We ignore data till now */
  274.         }
  275.             stack[StackPointer] -> NodeKind = Token;
  276.         stack[StackPointer] -> Data = Data;        /* We might need that... */
  277.         stack[StackPointer] -> Right =
  278.         stack[StackPointer] -> Left = (ExprNode *) NULL;
  279.         Token = GetToken(s, i, &Data);  /* And get new token from stream */
  280.     }
  281.     }
  282.     while (TRUE);
  283. }
  284.  
  285. /*****************************************************************************
  286. *   Routine to test precedence of two tokens. returns 0, <0 or >0 according  *
  287. * to comparison results:                                                     *
  288. *****************************************************************************/
  289. static int TestPreceeding(int Token1, int Token2)
  290. {
  291.     int Preced1, Preced2;
  292.  
  293.     if ((Token1 >= 1000) || (Token2 >= 1000)) return 0;   /* Ignore sub-expr */
  294.  
  295.     switch (Token1) {
  296.     case ABS:
  297.     case ARCCOS:
  298.     case ARCSIN:
  299.     case ARCTAN:
  300.     case COS:
  301.     case EXP:
  302.     case LN:
  303.     case LOG:
  304.     case SIN:
  305.     case SQR:
  306.     case SQRT:
  307.     case TAN:        Preced1 =100; break;
  308.     case NUMBER:
  309.     case PARAMETER:  Preced1 =120; break;
  310.     case PLUS:
  311.     case MINUS:      Preced1 = 20; break;
  312.     case MULT:
  313.     case DIV:
  314.     case MODULU:
  315.     case MINIMUM:
  316.     case MAXIMUM:    Preced1 = 40; break;
  317.     case POWER:      Preced1 = 60; break;
  318.     case UNARMINUS:  Preced1 = 65; break;
  319.     case OPENPARA:   Preced1 =  5; break;
  320.     case CLOSPARA:   Preced1 =120; break;
  321.     case TOKENSTART:
  322.     case TOKENEND:   Preced1 =  5; break;
  323.     }
  324.  
  325.     switch (Token2) {
  326.     case ABS:
  327.     case ARCCOS:
  328.     case ARCSIN:
  329.     case ARCTAN:
  330.     case COS:
  331.     case EXP:
  332.     case LN:
  333.     case LOG:
  334.     case SIN:
  335.     case SQR:
  336.     case SQRT:
  337.     case TAN:        Preced2 = 90; break;
  338.     case NUMBER:
  339.     case PARAMETER:  Preced2 =110; break;
  340.     case PLUS:
  341.     case MINUS:      Preced2 = 10; break;
  342.     case MULT:
  343.     case DIV:
  344.     case MODULU:
  345.     case MINIMUM:
  346.     case MAXIMUM:    Preced2 = 30; break;
  347.     case POWER:      Preced2 = 50; break;
  348.     case UNARMINUS:  Preced2 = 70; break;
  349.     case OPENPARA:   Preced2 =110; break;
  350.     case CLOSPARA:   Preced2 =  0; break;
  351.     case TOKENSTART:
  352.     case TOKENEND:   Preced2 =  0; break;
  353.     }
  354.  
  355.     return Preced1-Preced2;
  356. }
  357.  
  358. /*****************************************************************************
  359. *   Routine to get the next token out of the expression.                     *
  360. * Gets the expression in S, and current position in i.                       *
  361. * Returns the next token found, set data to the returned value (if any),     *
  362. * and update i to one char ofter the new token found.                        *
  363. *   Note that in minus sign case, it is determined whether it is monadic or  *
  364. * diadic minus by the last token - if the last token was operator or '('     *
  365. * it is monadic minus.                                                       *
  366. *****************************************************************************/
  367. static int GetToken(char *s, int *i, double *Data)
  368. {
  369.     int j;
  370.     char Number[LINE_LEN], c;
  371.  
  372.     while ((s[*i] == ' ') || (s[*i] == TAB)) (*i)++;
  373.     if (*i >= strlen(s)) return TOKENEND;   /* No more tokens around here... */
  374.  
  375.     /* Check is next token is one char - if so its a parameter */
  376.     if ((islower(s[*i]) || isupper(s[*i])) &&
  377.        !(islower(s[(*i)+1]) || isupper(s[(*i)+1]))) {
  378.     if (islower(c = s[(*i)++])) c = toupper(c); /* make parameter upcase */
  379.     *Data = c - 'A';                /* A = 0, B = 1, ... */
  380.         GlblLastToken = PARAMETER;
  381.         return PARAMETER;
  382.     }
  383.  
  384.     if (isdigit(s[*i]) || (s[*i] == '.')) {
  385.         j=0;
  386.     while (isdigit(s[*i]) || (s[*i] == '.')) Number[j++] = s[(*i)++];
  387.         Number[j] = NULL;
  388.     sscanf(Number, "%lf", Data);
  389.         GlblLastToken = NUMBER;
  390.         return NUMBER;
  391.     }
  392.  
  393.     switch (s[(*i)++]) {
  394.     case NULL: GlblLastToken = 0; return 0;
  395.     case '+': GlblLastToken = PLUS; return PLUS;
  396.     case '-':
  397.         switch (GlblLastToken) {
  398.         case NULL:           /* If first token (no last token yet) */
  399.         case PLUS:
  400.             case MINUS:
  401.             case MULT:
  402.             case DIV:
  403.         case MODULU:
  404.         case MINIMUM:
  405.         case MAXIMUM:
  406.             case POWER:
  407.             case UNARMINUS:
  408.             case OPENPARA:
  409.                     GlblLastToken= UNARMINUS; return UNARMINUS;
  410.         default:
  411.                     GlblLastToken= MINUS; return MINUS;
  412.         }
  413.     case '*': GlblLastToken = MULT; return MULT;
  414.     case '/': GlblLastToken = DIV; return DIV;
  415.     case '%': GlblLastToken = MODULU; return MODULU;
  416.     case '^': GlblLastToken = POWER; return POWER;
  417.     case '(': GlblLastToken = OPENPARA; return OPENPARA;
  418.     case ')': GlblLastToken = CLOSPARA; return CLOSPARA;
  419.     case 'A':
  420.         if ((s[*i] == 'R') && (s[*i+1] == 'C')) {
  421.         (*i) += 2;
  422.         switch (GetToken(s, i, Data)) {
  423.                     case SIN: GlblLastToken = ARCSIN; return ARCSIN;
  424.                     case COS: GlblLastToken = ARCCOS; return ARCCOS;
  425.                     case TAN: GlblLastToken = ARCTAN; return ARCTAN;
  426.                     default:
  427.                 GlblParsingError = P_ERR_UndefToken;
  428.                         return TOKENERROR;
  429.                 }
  430.             }
  431.         else if ((s[*i] == 'B') && (s[*i+1] == 'S')) {
  432.         (*i) += 2;
  433.                 GlblLastToken = ABS;
  434.                 return ABS;
  435.             }
  436.             else {
  437.                 GlblParsingError = P_ERR_UndefToken;
  438.                 return TOKENERROR;
  439.             }
  440.     case 'C':
  441.         if ((s[*i] == 'O') && (s[*i+1] == 'S')) {
  442.         (*i) += 2;
  443.                 GlblLastToken = COS;
  444.                 return COS;
  445.             }
  446.             else {
  447.                 GlblParsingError = P_ERR_UndefToken;
  448.                 return TOKENERROR;
  449.             }
  450.     case 'E':
  451.         if ((s[*i] == 'X') && (s[*i+1] == 'P')) {
  452.         (*i) += 2;
  453.                 GlblLastToken = EXP;
  454.                 return EXP;
  455.             }
  456.             else {
  457.                 GlblParsingError = P_ERR_UndefToken;
  458.                 return TOKENERROR;
  459.             }
  460.     case 'L':
  461.         if ((s[*i] == 'O') && (s[*i+1] == 'G')) {
  462.         (*i) += 2;
  463.                 GlblLastToken = LOG;
  464.                 return LOG;
  465.             }
  466.         else if (s[*i] == 'N') {
  467.                 (*i)++;
  468.                 GlblLastToken = LN;
  469.                 return LN;
  470.             }
  471.             else {
  472.                 GlblParsingError = P_ERR_UndefToken;
  473.                 return TOKENERROR;
  474.             }
  475.     case 'M':
  476.         if ((s[*i] == 'I') && (s[*i+1] == 'N')) {
  477.         (*i) += 2;
  478.         GlblLastToken = MINIMUM;
  479.         return MINIMUM;
  480.             }
  481.         else if ((s[*i]=='A') && (s[*i+1] == 'X')) {
  482.         (*i) += 2;
  483.         GlblLastToken = MAXIMUM;
  484.         return MAXIMUM;
  485.             }
  486.             else {
  487.                 GlblParsingError = P_ERR_UndefToken;
  488.                 return TOKENERROR;
  489.             }
  490.     case 'S':
  491.         if ((s[*i] == 'I') && (s[*i+1] == 'N')) {
  492.         (*i) += 2;
  493.                 GlblLastToken = SIN;
  494.                 return SIN;
  495.             }
  496.         else if ((s[*i] == 'Q') && (s[*i+1] == 'R')) {
  497.         (*i) += 2;
  498.         if (s[*i] == 'T') {
  499.                     (*i)++;
  500.                     GlblLastToken = SQRT;
  501.                     return SQRT;
  502.                 }
  503.                 else {
  504.                     GlblLastToken = SQR;
  505.                     return SQR;
  506.         }
  507.             }
  508.             else {
  509.                 GlblParsingError = P_ERR_UndefToken;
  510.                 return TOKENERROR;
  511.             }
  512.     case 'T':
  513.         if ((s[*i] == 'A') && (s[*i+1] == 'N')) {
  514.         (*i) += 2;
  515.                 GlblLastToken = TAN;
  516.                 return TAN;
  517.             }
  518.             else return TOKENERROR;
  519.     default:
  520.         GlblParsingError = P_ERR_UndefToken;
  521.             return TOKENERROR;
  522.     }
  523. }
  524.  
  525. /*****************************************************************************
  526. *   Routine to print a content of ROOT (using inorder traversal) :         *
  527. * Level holds: 0 for lowest level +/-, 1 for *, /, 2 for ^ operations.         *
  528. * If *str = NULL print on stdout, else on given    string Str.             *
  529. *****************************************************************************/
  530. void PrintTree(ExprNode *Root, char *Str)
  531. {
  532.     char LocalStr[255];
  533.  
  534.     strcpy(LocalStr, "");                /* Make the string empty */
  535.  
  536.     if (Str == NULL) {
  537.     LocalPrintTree(Root, 0, LocalStr);           /* Copy to local str. */
  538.     printf(LocalStr);                     /* and print... */
  539.     }
  540.     else {
  541.     strcpy(Str, "");                /* Make the string empty */
  542.     LocalPrintTree(Root, 0, Str);  /* Dont print to stdout - copy to str */
  543.     }
  544. }
  545.  
  546. /*****************************************************************************
  547. *   Routine to print a content of ROOT (using inorder traversal):         *
  548. * Level holds: 0 for lowest level +/-, 1 for *, /, 2 for ^ operations.         *
  549. *****************************************************************************/
  550. static void LocalPrintTree(ExprNode *Root, int Level, char *Str)
  551. {
  552.     int    CloseFlag = FALSE;
  553.  
  554.     if (!Root) return;
  555.  
  556.     switch (Root->NodeKind) {
  557.     case ABS:
  558.         strcat(Str, "abs(");
  559.         Level = 0;                   /* Paranthesis are opened */
  560.         CloseFlag = TRUE;               /* must close paranthesis */
  561.         break;
  562.     case ARCCOS:
  563.         strcat(Str, "arccos(");
  564.         Level = 0;
  565.         CloseFlag = TRUE;
  566.         break;
  567.     case ARCSIN:
  568.         strcat(Str, "arcsin(");
  569.         Level = 0;
  570.         CloseFlag = TRUE;
  571.         break;
  572.     case ARCTAN:
  573.         strcat(Str, "arctan(");
  574.         Level = 0;
  575.         CloseFlag = TRUE;
  576.         break;
  577.     case COS:
  578.         strcat(Str, "cos(");
  579.         Level = 0;
  580.         CloseFlag = TRUE;
  581.         break;
  582.     case EXP:
  583.         strcat(Str, "exp(");
  584.         Level = 0;
  585.         CloseFlag = TRUE;
  586.         break;
  587.     case LN:
  588.         strcat(Str, "ln(");
  589.         Level = 0;
  590.         CloseFlag = TRUE;
  591.         break;
  592.     case LOG:
  593.         strcat(Str, "log(");
  594.         Level = 0;
  595.         CloseFlag = TRUE;
  596.         break;
  597.     case SIN:
  598.         strcat(Str, "sin(");
  599.         Level = 0;
  600.         CloseFlag = TRUE;
  601.         break;
  602.     case SQR:
  603.         strcat(Str, "sqr(");
  604.         Level = 0;
  605.         CloseFlag = TRUE;
  606.         break;
  607.     case SQRT:
  608.         strcat(Str, "sqrt(");
  609.         Level = 0;
  610.         CloseFlag = TRUE;
  611.         break;
  612.     case TAN:
  613.         strcat(Str, "tan(");
  614.         Level = 0;
  615.         CloseFlag = TRUE;
  616.         break;
  617.     case PLUS:
  618.         if (Level >= 0) {
  619.         strcat(Str, "(");
  620.         CloseFlag = TRUE;
  621.         }
  622.         Level = 0;                           /* Plus Level */
  623.         LocalPrintTree(Root->Left, Level, Str);
  624.         strcat(Str, "+");
  625.         break;
  626.     case MINUS:
  627.         if (Level >= 0) {
  628.         strcat(Str, "(");
  629.         CloseFlag = TRUE;
  630.         }
  631.         Level = 0;                          /* Minus Level */
  632.         LocalPrintTree(Root->Left, Level, Str);
  633.         strcat(Str, "-");
  634.         break;
  635.     case MULT:
  636.         if (Level >= 1) {
  637.         strcat(Str, "(");
  638.         CloseFlag = TRUE;
  639.         }
  640.         Level = 1;                        /* Mul Level */
  641.         LocalPrintTree(Root->Left, Level, Str);
  642.         strcat(Str, "*");
  643.         break;
  644.     case DIV:
  645.         if (Level >= 1) {
  646.          strcat(Str, "(");
  647.         CloseFlag = TRUE;
  648.         }
  649.         Level = 1;                              /* Div Level */
  650.         LocalPrintTree(Root->Left, Level, Str);
  651.         strcat(Str, "/");
  652.         break;
  653.     case MODULU:
  654.         if (Level >= 1) {
  655.         strcat(Str, "(");
  656.         CloseFlag = TRUE;
  657.         }
  658.         Level = 1;                        /* Mod Level */
  659.         LocalPrintTree(Root->Left, Level, Str);
  660.         strcat(Str, "%");
  661.         break;
  662.     case MINIMUM:
  663.         if (Level >= 1) {
  664.         strcat(Str, "(");
  665.         CloseFlag = TRUE;
  666.         }
  667.         Level = 1;                        /* Min Level */
  668.         LocalPrintTree(Root->Left, Level, Str);
  669.         strcat(Str, " min ");
  670.         break;
  671.     case MAXIMUM:
  672.         if (Level >= 1) {
  673.         strcat(Str, "(");
  674.         CloseFlag = TRUE;
  675.         }
  676.         Level = 1;                        /* Max Level */
  677.         LocalPrintTree(Root->Left, Level, Str);
  678.         strcat(Str, " max ");
  679.         break;
  680.     case POWER:
  681.         Level = 2;                          /* Power Level */
  682.         LocalPrintTree(Root->Left, Level, Str);
  683.         strcat(Str, "^");
  684.         break;
  685.     case UNARMINUS:
  686.         strcat(Str, "(-");
  687.         Level = 0;                     /* Unarminus Level! */
  688.         CloseFlag = TRUE;
  689.         break;
  690.     case NUMBER:
  691.         sprintf(&Str[strlen(Str)], "%lg", Root->Data);
  692.         break;
  693.     case PARAMETER:
  694.         sprintf(&Str[strlen(Str)], "%c", (int) (Root->Data + 'A'));
  695.         break;
  696.     }
  697.     LocalPrintTree(Root->Right, Level, Str);
  698.     if (CloseFlag) strcat(Str, ")");
  699. }
  700.  
  701. /*****************************************************************************
  702. *  Routine to create a new copy    of a given tree:                 *
  703. *****************************************************************************/
  704. ExprNode *CopyTree(ExprNode *Root)
  705. {
  706.     ExprNode *Node;
  707.  
  708.     if (!Root) return NULL;
  709.  
  710.     Node = MyExprMalloc();
  711.     switch (Root->NodeKind) {
  712.     case ABS:
  713.     case ARCSIN:
  714.     case ARCCOS:
  715.     case ARCTAN:
  716.     case COS:
  717.     case EXP:
  718.     case LN:
  719.     case LOG:
  720.     case SIN:
  721.     case SQR:
  722.     case SQRT:
  723.     case TAN:
  724.         Node -> NodeKind = Root -> NodeKind;
  725.         Node -> Right = CopyTree(Root -> Right);
  726.         Node -> Left = NULL;
  727.         return Node;
  728.     case PLUS:
  729.     case MINUS:
  730.     case MULT:
  731.     case DIV:
  732.     case MODULU:
  733.     case POWER:
  734.     case MINIMUM:
  735.     case MAXIMUM:
  736.     case NUMBER:
  737.     case PARAMETER:
  738.     case UNARMINUS:
  739.         Node -> NodeKind = Root -> NodeKind;
  740.         if ((Root -> NodeKind == PARAMETER) ||
  741.         (Root -> NodeKind == NUMBER)) Node -> Data = Root -> Data;
  742.         Node -> Right = CopyTree(Root -> Right);
  743.         Node -> Left  = CopyTree(Root -> Left);
  744.         return Node;
  745.     }
  746.     return NULL;                    /* Should never get here */
  747. }
  748.  
  749. /*****************************************************************************
  750. *   Routine to evaluate    a value    of a given tree    root and parameter.         *
  751. *****************************************************************************/
  752. double EvalTree(ExprNode *Root)
  753. {
  754.     int ITemp;
  755.     double Temp;
  756.  
  757.     switch (Root->NodeKind) {
  758.     case ABS:
  759.         Temp = EvalTree(Root->Right);
  760.         return Temp > 0 ? Temp : -Temp;
  761.     case ARCSIN: return asin(EvalTree(Root->Right));
  762.     case ARCCOS: return acos(EvalTree(Root->Right));
  763.     case ARCTAN: return atan(EvalTree(Root->Right));
  764.     case COS: return cos(EvalTree(Root->Right));
  765.     case EXP: return exp(EvalTree(Root->Right));
  766.     case LN: return log(EvalTree(Root->Right));
  767.     case LOG: return log10(EvalTree(Root->Right));
  768.     case SIN: return sin(EvalTree(Root->Right));
  769.     case SQR: Temp = EvalTree(Root->Right);    return Temp*Temp;
  770.     case SQRT: return sqrt(EvalTree(Root->Right));
  771.     case TAN: return tan(EvalTree(Root->Right));
  772.     case MODULU:
  773.         ITemp = (int) EvalTree(Root->Right);
  774.         if (ITemp != 0)
  775.         return    (double) (((int) EvalTree(Root->Left)) % ITemp);
  776.         else {
  777.         GlblEvalError = E_ERR_DivByZero;
  778.         return EvalTree(Root->Left) * 1.0;
  779.         }
  780.     case DIV:
  781.         Temp = EvalTree(Root->Right);
  782.         if (Temp != 0.0)
  783.         return    EvalTree(Root->Left) / Temp;
  784.         else {
  785.         GlblEvalError = E_ERR_DivByZero;
  786.         return    EvalTree(Root->Left) * INFINITY;
  787.         }
  788.     case MINUS: return EvalTree(Root->Left) - EvalTree(Root->Right);
  789.     case MULT: return EvalTree(Root->Left) * EvalTree(Root->Right);
  790.     case PLUS: return EvalTree(Root->Left) + EvalTree(Root->Right);
  791.     case POWER: return pow(EvalTree(Root->Left), EvalTree(Root->Right));
  792.     case UNARMINUS: return -EvalTree(Root->Right);
  793.     case MINIMUM: return MIN(EvalTree(Root->Left), EvalTree(Root->Right));
  794.     case MAXIMUM: return MAX(EvalTree(Root->Left), EvalTree(Root->Right));
  795.     case NUMBER: return Root->Data;
  796.     case PARAMETER: return GlobalParam[(int) (Root->Data)];
  797.     }
  798.     return 0; /* Never get here    (only make lint    quite...) */
  799. }
  800.  
  801. #ifdef DERIVATIVE
  802.  
  803. /*****************************************************************************
  804. *  Routine to generate the tree    represent the derivative of tree root:         *
  805. *****************************************************************************/
  806. ExprNode *DerivTree(ExprNode *Root, int Param)
  807. {
  808.     int    i, Flag = TRUE;
  809.     ExprNode *Node, *NewNode;
  810.  
  811.     Node = DerivTree1(Root, Param);
  812.     if (!GlblDerivError) {
  813.     while (Flag) {
  814.         Flag = FALSE;
  815.         NewNode = Optimize(Node, &Flag);
  816.         FreeTree(Node);                /* Release old tree area */
  817.         Node = NewNode;
  818.     }
  819.     for (i=0; i<10;    i++) {      /* Do more loops - might optimize by shift */
  820.         Flag = FALSE;
  821.         NewNode = Optimize(Node, &Flag);
  822.         FreeTree(Node);                /* Release old tree area */
  823.         Node = NewNode;
  824.     }
  825.     }
  826.     return NewNode;
  827. }
  828.  
  829. /*****************************************************************************
  830. *  Routine to generate non optimal derivative of the tree root :         *
  831. *****************************************************************************/
  832. static ExprNode *DerivTree1(ExprNode *Root, int Param)
  833. {
  834.     ExprNode *Node1, *Node2, *Node3, *Node4, *NodeMul;
  835.  
  836.     NodeMul = MyExprMalloc();
  837.     NodeMul -> NodeKind = MULT;
  838.  
  839.     switch (Root->NodeKind) {
  840.     case ABS:
  841.         GlblDerivError = D_ERR_NoAbsDeriv;
  842.         return NULL;                  /* No derivative ! */
  843.     case ARCSIN:
  844.         NodeMul->Left = Gen1u2Tree(PLUS, MINUS, -0.5,
  845.                             CopyTree(Root->Right));
  846.         NodeMul->Right = DerivTree1(Root->Right, Param);
  847.         return NodeMul;
  848.     case ARCCOS:
  849.         NodeMul->Left = Gen1u2Tree(MINUS, MINUS, -0.5,
  850.                             CopyTree(Root->Right));
  851.         NodeMul->Right = DerivTree1(Root->Right, Param);
  852.         return NodeMul;
  853.     case ARCTAN:
  854.         NodeMul->Left = Gen1u2Tree(PLUS, PLUS, -1.0,
  855.                             CopyTree(Root->Right));
  856.         NodeMul->Right = DerivTree1(Root->Right, Param);
  857.         return NodeMul;
  858.     case COS:
  859.         Node1 = MyExprMalloc();
  860.         Node2 = MyExprMalloc();
  861.         Node1 -> NodeKind = UNARMINUS;
  862.         Node2 -> NodeKind = SIN;
  863.         Node2 -> Right = CopyTree(Root->Right);
  864.         Node1 -> Left = Node2 -> Left = NULL;
  865.         Node1 -> Right = Node2;
  866.         NodeMul -> Left = Node1;
  867.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  868.         return NodeMul;
  869.     case EXP:
  870.         Node1 = MyExprMalloc();
  871.         Node1 -> NodeKind = EXP;
  872.         Node1 -> Right = CopyTree(Root->Right);
  873.         NodeMul -> Left = Node1;
  874.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  875.         return NodeMul;
  876.     case LN:
  877.         NodeMul -> NodeKind = DIV;
  878.         NodeMul -> Right = CopyTree(Root->Right);
  879.         NodeMul -> Left = DerivTree1(Root->Right, Param);
  880.         return NodeMul;
  881.     case LOG:
  882.         Node1 = MyExprMalloc();
  883.         Node2 = MyExprMalloc();
  884.         Node1 -> NodeKind = DIV;
  885.         Node1 -> Right = CopyTree(Root->Right);
  886.         Node1 -> Left = DerivTree1(Root->Right, Param);
  887.         Node2 -> NodeKind = NUMBER;;
  888.         Node2 -> Data = log10(exp(1.0));
  889.         NodeMul -> Left = Node1;
  890.         NodeMul -> Right = Node2;
  891.         return NodeMul;
  892.     case SIN:
  893.         Node1 = MyExprMalloc();
  894.         Node1 -> NodeKind = COS;
  895.         Node1 -> Right = CopyTree(Root->Right);
  896.         Node1 -> Left = NULL;
  897.         NodeMul -> Left = Node1;
  898.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  899.         return NodeMul;
  900.     case SQR:
  901.         Node1 = MyExprMalloc();
  902.         Node2 = MyExprMalloc();
  903.         Node1 -> NodeKind = NUMBER;
  904.         Node1 -> Right = Node1 -> Left = NULL;
  905.         Node1 -> Data = 2.0;
  906.         Node2 -> NodeKind = MULT;;
  907.         Node2 -> Right = DerivTree1(Root->Right, Param);
  908.         Node2 -> Left = CopyTree(Root->Right);
  909.         NodeMul -> Left = Node1;
  910.         NodeMul -> Right = Node2;
  911.         return NodeMul;
  912.     case SQRT:
  913.         Node1 = MyExprMalloc();
  914.         Node2 = MyExprMalloc();
  915.         Node3 = MyExprMalloc();
  916.         Node4 = MyExprMalloc();
  917.         Node1 -> NodeKind = NUMBER;
  918.         Node1 -> Right = Node1 -> Left = NULL;
  919.         Node1 -> Data = -0.5;
  920.         Node2 -> NodeKind = POWER;
  921.         Node2 -> Right = Node1;
  922.         Node2 -> Left = CopyTree(Root->Right);
  923.         Node3 -> NodeKind = NUMBER;
  924.         Node3 -> Right = Node3 -> Left = NULL;
  925.         Node3 -> Data = 0.5;
  926.         Node4 -> NodeKind = MULT;
  927.         Node4 -> Right = Node2;
  928.         Node4 -> Left  = Node3;
  929.         NodeMul -> Left = Node4;
  930.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  931.         return NodeMul;
  932.     case TAN:
  933.         Node1 = MyExprMalloc();
  934.         Node2 = MyExprMalloc();
  935.         Node1 -> NodeKind = COS;
  936.         Node1 -> Left = NULL;
  937.         Node1 -> Right = CopyTree(Root->Right);
  938.         Node2 -> NodeKind = SQR;
  939.         Node2 -> Left = NULL;
  940.         Node2 -> Right = Node1;
  941.         NodeMul -> NodeKind = DIV;
  942.         NodeMul -> Right = Node2;
  943.         NodeMul -> Left = DerivTree1(Root->Right, Param);
  944.         return NodeMul;
  945.     case PLUS:
  946.         NodeMul -> NodeKind = PLUS;
  947.         NodeMul -> Left = DerivTree1(Root->Left, Param);
  948.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  949.         return NodeMul;
  950.     case MINUS:
  951.         NodeMul -> NodeKind = MINUS;
  952.         NodeMul -> Left = DerivTree1(Root->Left, Param);
  953.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  954.         return NodeMul;
  955.     case MULT:
  956.         Node1 = MyExprMalloc();
  957.         Node2 = MyExprMalloc();
  958.         Node1 -> NodeKind = MULT;
  959.         Node1 -> Left = CopyTree(Root->Left);
  960.         Node1 -> Right = DerivTree1(Root->Right, Param);
  961.         Node2 -> NodeKind = MULT;
  962.         Node2 -> Left = DerivTree1(Root->Left, Param);
  963.         Node2 -> Right = CopyTree(Root->Right);
  964.         NodeMul -> NodeKind = PLUS;
  965.         NodeMul -> Left = Node1;
  966.         NodeMul -> Right = Node2;
  967.         return NodeMul;
  968.     case DIV:
  969.         Node1 = MyExprMalloc();
  970.         Node2 = MyExprMalloc();
  971.         Node3 = MyExprMalloc();
  972.         Node4 = MyExprMalloc();
  973.         Node1 -> NodeKind = MULT;
  974.         Node1 -> Left = CopyTree(Root->Left);
  975.         Node1 -> Right = DerivTree1(Root->Right, Param);
  976.         Node2 -> NodeKind = MULT;
  977.         Node2 -> Left = DerivTree1(Root->Left, Param);
  978.         Node2 -> Right = CopyTree(Root->Right);
  979.         Node3 -> NodeKind = MINUS;
  980.         Node3 -> Right = Node1;
  981.         Node3 -> Left = Node2;
  982.         Node4 -> NodeKind = SQR;
  983.         Node4 -> Right = CopyTree(Root->Right);
  984.         Node4 -> Left  = NULL;
  985.         NodeMul -> NodeKind = DIV;
  986.         NodeMul -> Left = Node3;
  987.         NodeMul -> Right = Node4;
  988.         return NodeMul;
  989.     case MODULU:
  990.         GlblDerivError = D_ERR_NoModDeriv;
  991.         return NULL;                   /* No derivative! */
  992.     case POWER:
  993.         if (Root -> Right -> NodeKind != NUMBER) {
  994.         GlblDerivError = D_ERR_NoneConstExp;
  995.         return NULL;
  996.         }
  997.         Node1 = MyExprMalloc();
  998.         Node2 = MyExprMalloc();
  999.         Node3 = MyExprMalloc();
  1000.         Node4 = MyExprMalloc();
  1001.         Node1 -> NodeKind = NUMBER;
  1002.         Node1 -> Left = Node1 -> Right = NULL;
  1003.         Node1 -> Data = Root -> Right -> Data - 1;
  1004.         Node2 -> NodeKind = POWER;
  1005.         Node2 -> Left = CopyTree(Root->Left);
  1006.         Node2 -> Right = Node1;
  1007.         Node3 -> NodeKind = NUMBER;
  1008.         Node3 -> Left = Node3 -> Right = NULL;
  1009.         Node3 -> Data = Root -> Right -> Data;
  1010.         Node4 -> NodeKind = MULT;
  1011.         Node4 -> Right = Node2;
  1012.         Node4 -> Left = Node3;
  1013.         NodeMul -> Left = Node4;
  1014.         NodeMul -> Right = DerivTree1(Root->Left, Param);
  1015.         return NodeMul;
  1016.     case MINIMUM: GlblDerivError = D_ERR_NoMinDeriv;
  1017.         return NULL;                   /* No derivative! */
  1018.     case MAXIMUM: GlblDerivError = D_ERR_NoMaxDeriv;
  1019.         return NULL;                    /* No derivative! */
  1020.     case UNARMINUS:
  1021.         NodeMul -> NodeKind = UNARMINUS;
  1022.         NodeMul -> Right = DerivTree1(Root->Right, Param);
  1023.         NodeMul -> Left  = NULL;
  1024.         return NodeMul;
  1025.     case NUMBER:
  1026.         NodeMul -> NodeKind = NUMBER;
  1027.         NodeMul -> Left = NodeMul -> Right = NULL;
  1028.         NodeMul -> Data = 0.0;
  1029.         return NodeMul;
  1030.     case PARAMETER:
  1031.         NodeMul -> NodeKind = NUMBER;
  1032.         NodeMul -> Left = NodeMul -> Right = NULL;
  1033.         if ((int) (Root->Data) == Param)
  1034.          NodeMul -> Data = 1.0;
  1035.         else NodeMul -> Data = 0.0;
  1036.         return NodeMul;
  1037.     }
  1038.     return NULL;                    /* Should never get here */
  1039. }
  1040.  
  1041. /*****************************************************************************
  1042. *  Routine to generate a tree to the expression:                 *
  1043. *      SIGN1(1 SIGN2 SQR (EXPR)) ^ EXPONENT                     *
  1044. *****************************************************************************/
  1045. static ExprNode *Gen1u2Tree(int Sign1, int Sign2, double Exponent,
  1046.                                 ExprNode *Expr)
  1047. {
  1048.     ExprNode *Node1, *Node2, *Node3, *Node4, *Node5, *Node6;
  1049.  
  1050.     Node1 = MyExprMalloc();
  1051.     Node2 = MyExprMalloc();
  1052.     Node3 = MyExprMalloc();
  1053.     Node4 = MyExprMalloc();
  1054.     Node5 = MyExprMalloc();
  1055.     Node1 -> NodeKind = NUMBER;
  1056.     Node1 -> Left = Node1 -> Right = NULL;
  1057.     Node1 -> Data = 1.0;
  1058.     Node2 -> NodeKind = SQR;
  1059.     Node2 -> Right = CopyTree(Expr);
  1060.     Node2 -> Left = NULL;
  1061.     Node3 -> NodeKind = Sign2;
  1062.     Node3 -> Left = Node1;
  1063.     Node3 -> Right = Node2;
  1064.     Node4 -> NodeKind = NUMBER;
  1065.     Node4 -> Data = Exponent;
  1066.     Node4 -> Right = Node4 -> Left = NULL;
  1067.     Node5 -> NodeKind = POWER;
  1068.     Node5 -> Right = Node4;
  1069.     Node5 -> Left = Node3;
  1070.     if (Sign1 == PLUS) return Node5;
  1071.     else {                            /* Must be MINUS */
  1072.     Node6 =    MyExprMalloc();
  1073.     Node6 -> NodeKind = UNARMINUS;
  1074.     Node6 -> Left =    NULL;
  1075.     Node6 -> Right = Node5;
  1076.     return Node6;
  1077.     }
  1078. }
  1079.  
  1080. /*****************************************************************************
  1081. *  Routine to optimize the binary tree :                     *
  1082. * Note:    the old    tree is    NOT modified. flag returns TRUE    if optimized.         *
  1083. *****************************************************************************/
  1084. static ExprNode *Optimize(ExprNode *Root, int *Flag)
  1085. {
  1086.     ExprNode *Node;
  1087.  
  1088.     if (!Root) return NULL;
  1089.     if ((Root -> NodeKind != NUMBER) &&
  1090.     (!ParamInTree(Root, PARAMETER_ALL))) { /* The expression is constant */
  1091.     *Flag =    TRUE;
  1092.     Node = MyExprMalloc();
  1093.     Node ->    NodeKind = NUMBER;
  1094.     Node ->    Data = EvalTree(Root);
  1095.     Node ->    Right =    Node ->    Left = NULL;
  1096.     return Node;
  1097.     }
  1098.     /* Shift in    Mult or    Plus: A+(B+C) -->  C+(A+B) */
  1099.     if ((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))
  1100.     if ((Root -> NodeKind == Root -> Right -> NodeKind) &&
  1101.        ((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))) {
  1102.     Node = Root -> Left;
  1103.     Root ->    Left = Root -> Right ->    Right;
  1104.     Root ->    Right -> Right = Root -> Right -> Left;
  1105.     Root ->    Right -> Left =    Node;
  1106.     }
  1107.  
  1108.     /* Shift in    Mult or    Plus: (A+B)+C -->  (C+A)+B */
  1109.     if ((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))
  1110.     if ((Root -> NodeKind == Root -> Left -> NodeKind) &&
  1111.        ((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))) {
  1112.     Node = Root -> Right;
  1113.     Root ->    Right =    Root ->    Left ->    Left;
  1114.     Root ->    Left ->    Left = Root -> Left -> Right;
  1115.     Root ->    Left ->    Right =    Node;
  1116.     }
  1117.  
  1118.     switch (Root->NodeKind) {
  1119.     case DIV:
  1120.         if ((Root -> Right -> NodeKind == NUMBER) &&
  1121.         (Root -> Right -> Data == 1.0)) {
  1122.         *Flag = TRUE;
  1123.         return Optimize(Root -> Left, Flag);         /* Div by 1 */
  1124.         }
  1125.         if ((Root -> Left  -> NodeKind == NUMBER) &&
  1126.         (Root -> Left  -> Data == 0.0)) {
  1127.         *Flag = TRUE;
  1128.         return Optimize(Root -> Left, Flag);     /* Div 0 - return 0 */
  1129.         }
  1130.         if (CmpTree(Root -> Left, Root -> Right)) {
  1131.         *Flag = TRUE;
  1132.         Node = MyExprMalloc();
  1133.         Node -> NodeKind = NUMBER;
  1134.         Node -> Data = 1.0;
  1135.         Node -> Right = Node -> Left = NULL;
  1136.         return Node;                     /* f/f == 1 */
  1137.         }
  1138.         break;
  1139.     case MINUS:
  1140.         if ((Root -> Right -> NodeKind == NUMBER) &&
  1141.         (Root -> Right -> Data == 0.0)) {
  1142.         *Flag = TRUE;
  1143.         return Optimize(Root -> Left, Flag);            /* X - 0 */
  1144.         }
  1145.         if ((Root -> Left -> NodeKind == NUMBER) &&
  1146.         (Root -> Left -> Data == 0.0)) {
  1147.         Node = MyExprMalloc();
  1148.         Node -> NodeKind = UNARMINUS;
  1149.         Node -> Left = NULL;
  1150.         Node -> Right = Optimize(Root -> Right, Flag);
  1151.         *Flag = TRUE;
  1152.         return Node;                   /* (0 - X) --> -X */
  1153.         }
  1154.         if (CmpTree(Root -> Left, Root -> Right)) {
  1155.         *Flag = TRUE;
  1156.         Node = MyExprMalloc();
  1157.         Node -> NodeKind = NUMBER;
  1158.         Node -> Data = 0.0;
  1159.         Node -> Right = Node -> Left = NULL;
  1160.         return Node;                       /* f-f == 0.0 */
  1161.         }
  1162.         if (Root -> Right -> NodeKind == UNARMINUS) {
  1163.         *Flag = TRUE;
  1164.         Node = MyExprMalloc();
  1165.         Node -> NodeKind = PLUS;
  1166.         Node -> Left = Optimize(Root -> Left, Flag);
  1167.         Node -> Right = Optimize(Root -> Right -> Right, Flag);
  1168.         return Optimize(Node, Flag);           /* a-(-b) --> a+b */
  1169.         }
  1170.         break;
  1171.     case MULT:
  1172.         if ((Root -> Right -> NodeKind == NUMBER) &&
  1173.         ((Root -> Right -> Data == 1.0) ||
  1174.          (Root -> Right -> Data == 0.0))) {
  1175.         *Flag = TRUE;
  1176.         if (Root -> Right -> Data == 1.0)
  1177.             return Optimize(Root -> Left, Flag);     /* Mul by 1 */
  1178.         else return Optimize(Root -> Right, Flag);     /* Mul by 0 */
  1179.         }
  1180.         if ((Root -> Left -> NodeKind == NUMBER) &&
  1181.         ((Root -> Left -> Data == 1.0) ||
  1182.          (Root -> Left -> Data == 0.0))) {
  1183.         *Flag = TRUE;
  1184.         if (Root -> Left -> Data == 1.0)
  1185.             return Optimize(Root -> Right, Flag);     /* Mul by 1 */
  1186.             else return Optimize(Root -> Left, Flag);     /* Mul by 0 */
  1187.         }
  1188.         if (CmpTree(Root -> Left, Root -> Right)) {
  1189.         *Flag = TRUE;
  1190.         Node = MyExprMalloc();
  1191.         Node -> NodeKind = SQR;
  1192.         Node -> Right = Optimize(Root -> Right, Flag);
  1193.         Node -> Left = NULL;
  1194.         return Node;                    /* f*f = f^2 */
  1195.         }
  1196.         break;
  1197.     case PLUS:
  1198.         if ((Root -> Right -> NodeKind == NUMBER) &&
  1199.         (Root -> Right -> Data == 0.0)) {
  1200.         *Flag = TRUE;
  1201.         return Optimize(Root -> Left, Flag);            /* Add 0 */
  1202.         }
  1203.         if ((Root -> Left  -> NodeKind == NUMBER) &&
  1204.         (Root -> Left  -> Data == 0.0)) {
  1205.         *Flag = TRUE;
  1206.         return Optimize(Root -> Right, Flag);            /* Add 0 */
  1207.         }
  1208.         if (CmpTree(Root -> Left, Root -> Right)) {
  1209.         *Flag = TRUE;
  1210.         Node = MyExprMalloc();
  1211.         Node -> NodeKind = MULT;
  1212.         Node -> Left = Optimize(Root -> Right, Flag);
  1213.         Node -> Right = MyExprMalloc();
  1214.         Node -> Right -> NodeKind    = NUMBER;
  1215.         Node -> Right -> Data = 2.0;
  1216.         Node -> Right -> Left = Node -> Right -> Right = NULL;
  1217.         return Node;                    /* f+f = f*2 */
  1218.         }
  1219.         if (Root -> Right  -> NodeKind == UNARMINUS) {
  1220.         *Flag = TRUE;
  1221.         Node = MyExprMalloc();
  1222.         Node -> NodeKind = MINUS;
  1223.         Node -> Left = Optimize(Root -> Left, Flag);
  1224.         Node -> Right = Optimize(Root -> Right -> Right, Flag);
  1225.         return Optimize(Node, Flag);           /* a+(-b) --> a-b */
  1226.         }
  1227.         if (Root -> Left -> NodeKind == UNARMINUS) {
  1228.         *Flag = TRUE;
  1229.         Node = MyExprMalloc();
  1230.         Node -> NodeKind = MINUS;
  1231.         Node -> Left = Optimize(Root -> Right, Flag);
  1232.         Node -> Right = Optimize(Root -> Left -> Right, Flag);
  1233.         return Optimize(Node, Flag);           /* (-a)+b --> b-a */
  1234.         }
  1235.         break;
  1236.     case POWER:
  1237.         if ((Root -> Right -> NodeKind == NUMBER) &&
  1238.         (Root -> Right -> Data == 0.0)) {
  1239.         *Flag = TRUE;
  1240.         Node = MyExprMalloc();
  1241.         Node -> NodeKind = NUMBER;
  1242.         Node -> Data = 1.0;
  1243.         Node -> Right = Node -> Left = NULL;
  1244.         return Node;                     /* f^0 == 1 */
  1245.         }
  1246.         if ((Root -> Right -> NodeKind == NUMBER) &&
  1247.         (Root -> Right -> Data == 1.0)) {
  1248.         *Flag = TRUE;
  1249.         return Optimize(Root -> Left, Flag);          /* f^1 = f */
  1250.         }
  1251.         break;
  1252.     case UNARMINUS:
  1253.         if (Root -> Right -> NodeKind == UNARMINUS) {
  1254.         *Flag = TRUE;
  1255.         return Optimize(Root -> Right -> Right, Flag);        /* --a=a */
  1256.         }
  1257.         if (Root -> Right -> NodeKind == NUMBER) {
  1258.         *Flag = TRUE;
  1259.         Node = MyExprMalloc();
  1260.         Node -> NodeKind = NUMBER;
  1261.         Node -> Data = (- Root -> Right -> Data);
  1262.         Node -> Right = Node -> Left  = NULL;
  1263.         return Node;               /* Convert -(x) into (-x) */
  1264.         }
  1265.         break;
  1266.     default:;
  1267.     }
  1268.  
  1269.     /* If we are here -    no optimization    took place : */
  1270.     Node = MyExprMalloc();
  1271.     Node -> NodeKind =    Root ->    NodeKind;
  1272.     if ((Root -> NodeKind == PARAMETER) ||
  1273.     (Root -> NodeKind == NUMBER)) Node -> Data = Root -> Data;
  1274.     Node -> Right = Optimize(Root -> Right, Flag);
  1275.     Node -> Left  = Optimize(Root -> Left,  Flag);
  1276.     return Node;
  1277. }
  1278.  
  1279. #endif DERIVATIVE
  1280.  
  1281. /*****************************************************************************
  1282. *   Routine to compere two trees - for equality:                 *
  1283. * The trees are    compered to be symbolically equal i.e. A*B == B*A !         *
  1284. *****************************************************************************/
  1285. int CmpTree(ExprNode *Root1, ExprNode *Root2)
  1286. {
  1287.     if (Root1->NodeKind != Root2->NodeKind) return FALSE;
  1288.  
  1289.     switch (Root1->NodeKind) {
  1290.     case ABS:
  1291.     case ARCSIN:
  1292.     case ARCCOS:
  1293.     case ARCTAN:
  1294.     case COS:
  1295.     case EXP:
  1296.     case LN:
  1297.     case LOG:
  1298.     case SIN:
  1299.     case SQR:
  1300.     case SQRT:
  1301.     case TAN:
  1302.     case UNARMINUS:
  1303.         return CmpTree(Root1->Right, Root2->Right);
  1304.     case MULT:                    /* Note that A*B = B*A ! */
  1305.     case PLUS:
  1306.     case MINIMUM:
  1307.     case MAXIMUM:
  1308.         return ((CmpTree(Root1->Right, Root2->Right) &&
  1309.              CmpTree(Root1->Left,  Root2->Left)) ||
  1310.             (CmpTree(Root1->Right, Root2->Left) &&
  1311.              CmpTree(Root1->Left,  Root2->Right)));
  1312.     case DIV:
  1313.     case MODULU:
  1314.     case MINUS:
  1315.     case POWER:
  1316.         return (CmpTree(Root1->Right, Root2->Right) &&
  1317.             CmpTree(Root1->Left,  Root2->Left));
  1318.     case NUMBER:
  1319.     case PARAMETER:
  1320.         return (Root1->Data == Root2->Data);
  1321.     }
  1322.     return FALSE;                    /* Should never get here */
  1323. }
  1324.  
  1325. /*****************************************************************************
  1326. *   Routine to test if the parameter is    in the tree :                 *
  1327. * If parameter == PARAMETER_ALL then any parameter return TRUE.             *
  1328. *****************************************************************************/
  1329. int ParamInTree(ExprNode *Root, int Param)
  1330. {
  1331.     if (!Root) return FALSE;
  1332.  
  1333.     switch (Root->NodeKind) {
  1334.     case ABS:
  1335.     case ARCSIN:
  1336.     case ARCCOS:
  1337.     case ARCTAN:
  1338.     case COS:
  1339.     case EXP:
  1340.     case LN:
  1341.     case LOG:
  1342.     case SIN:
  1343.     case SQR:
  1344.     case SQRT:
  1345.     case TAN:
  1346.     case UNARMINUS:
  1347.         return ParamInTree(Root->Right, Param);
  1348.     case PLUS:
  1349.     case MINUS:
  1350.     case MULT:
  1351.     case DIV:
  1352.     case MODULU:
  1353.     case MINIMUM:
  1354.     case MAXIMUM:
  1355.     case POWER:
  1356.         return ParamInTree(Root->Right, Param) ||
  1357.            ParamInTree(Root->Left, Param);
  1358.     case NUMBER:
  1359.         return FALSE;
  1360.     case PARAMETER:
  1361.         if (Param != PARAMETER_ALL)
  1362.          return ((int) (Root->Data) == Param);
  1363.         else return TRUE;
  1364.     }
  1365.     return FALSE;                    /* Should never get here */
  1366. }
  1367.  
  1368. /*****************************************************************************
  1369. *   Routine to free a tree - release all memory    allocated by it.         *
  1370. *****************************************************************************/
  1371. void FreeTree(ExprNode *Root)
  1372. {
  1373.     if (!Root) return;
  1374.  
  1375.     switch (Root->NodeKind) {
  1376.     case ABS:
  1377.     case ARCSIN:
  1378.     case ARCCOS:
  1379.     case ARCTAN:
  1380.     case COS:
  1381.     case EXP:
  1382.     case LN:
  1383.     case LOG:
  1384.     case SIN:
  1385.     case SQR:
  1386.     case SQRT:
  1387.     case TAN:
  1388.     case UNARMINUS:
  1389.         FreeTree(Root->Right);
  1390.         MyExprFree(Root);
  1391.         break;
  1392.     case PLUS:
  1393.     case MINUS:
  1394.     case MULT:
  1395.     case DIV:
  1396.     case MODULU:
  1397.     case MINIMUM:
  1398.     case MAXIMUM:
  1399.     case POWER:
  1400.         FreeTree(Root->Right);
  1401.         FreeTree(Root->Left);
  1402.         MyExprFree(Root);
  1403.         break;
  1404.     case NUMBER:
  1405.     case PARAMETER:
  1406.         MyExprFree(Root);
  1407.         break;
  1408.     }
  1409. }
  1410.  
  1411. /*****************************************************************************
  1412. *   Routine to return parsing error if happen one, zero    elsewhere         *
  1413. *****************************************************************************/
  1414. int ParserError(void)
  1415. {
  1416.     int    Temp;
  1417.  
  1418.     Temp = GlblParsingError;
  1419.     GlblParsingError = 0;
  1420.     return Temp;
  1421. }
  1422.  
  1423. #ifdef DERIVATIVE
  1424.  
  1425. /*****************************************************************************
  1426. *   Routine to return derivate error if    happen one, zero elsewhere         *
  1427. *****************************************************************************/
  1428. int DerivError(void)
  1429. {
  1430.     int    Temp;
  1431.  
  1432.     Temp = GlblDerivError;
  1433.     GlblDerivError = 0;
  1434.     return Temp;
  1435. }
  1436.  
  1437. #endif DERIVATIVE
  1438.  
  1439. /*****************************************************************************
  1440. *   Routine to return evaluation error if happen one, zero elsewhere         *
  1441. *****************************************************************************/
  1442. int EvalError(void)
  1443. {
  1444.     int    Temp;
  1445.  
  1446.     Temp = GlblEvalError;
  1447.     GlblEvalError = 0;
  1448.     return Temp;
  1449. }
  1450.  
  1451. /*****************************************************************************
  1452. *  Routine to set the value of a parameter before evaluating it.         *
  1453. *****************************************************************************/
  1454. void SetParamValue(double Value, int Number)
  1455. {
  1456.     if ((Number >= 0) && (Number <= PARAMETER_Z)) GlobalParam[Number] = Value;
  1457. }
  1458.