home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Power Programming
/
powerprogramming1994.iso
/
progtool
/
irit
/
drawfuns.arc
/
EXPR2TRE.C
< prev
next >
Wrap
C/C++ Source or Header
|
1989-07-29
|
48KB
|
1,458 lines
/*****************************************************************************
* Module to convert infix expression given as a string into a binary tree. *
* Evaluate trees, and make symbolic derivation of such trees. *
* *
* Main routines: *
* 1. ExprNode *Expr2Tree(s) - main routine to perform conversion. *
* int ParserError() - return error number (expr2trg.h), 0 o.k. *
* 2. PrintTree(Root, Str) - routine to print in infix form content of tree *
* 3. ExprNode *CopyTree(Root) - returns a new copy of root pointed tree. *
* 4. double EvalTree(Root) - evaluate expression for a given t. *
* int EvalError() - return error number (expr2trg.h), 0 o.k. *
* 5. ExprNode *DerivTree(Root, Param) - returns new tree - its derivative *
* according to parameter Param. Define *
* DERIVATIVE for the preprocessor for this *
* routine (see Expr2TrG.h file). *
* int DerivError() - return error number (expr2trg.h), 0 o.k. *
* Also needs definition of DERIVATIVE. *
* 6. SetParamValue(Value, Number) - set that parameter value... *
* *
* In addition: *
* 7. int CmpTree(Root1, Root2) - compere symbolically two trees. *
* 8. int ParamInTree(Root, parameter) - return TRUE if parameter in tree. *
* 9. FreeTree(Root) - release memory allocated for tree root. *
* *
* *
* Written by: Gershon Elber ver 1.2, June 1988 *
* *
* Ver 0.2 modifications: replace old inc. notation (=+) with new (+=). *
* Ver 0.3 modifications: parameter can be T or X (was only T). *
* PrintTree(root, String) print the tree into String *
* or to screen (as it was) if String address is null. *
* setparamchar(c) - set the parameter char, t default *
* Ver 0.4 modifications: split expr2tre.h into local and globals consts. *
* Ver 1.0 modifications: multiple variables is now supported, meaning *
* functions of few variables can new be evaluated and *
* derivated!. Note that for some of the functions, *
* the parameter of them were modified/added. *
* Now integer power of negative numbers is supported. *
* Ver 1.1 modifications: minor changes, added function definitions to the *
* global constant file - expr2trg.h *
* Ver 1.2 modifications: add EvalError() function for div by zero error. *
* Ver 2.0 modifications: change the parser to operator preceedings. *
* Ver 2.1 modifications: adding min, max, and modulu (%) operators. *
*****************************************************************************/
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <alloc.h>
#include "Expr2TrG.h"
#include "Expr2TrL.h"
static int GlblLastToken, GlblParsingError; /* Globals used by parser */
static int GlblEvalError; /* Global used by eval_tree */
static double GlobalParam[PARAMETER_Z1]; /* The parameters are save here */
#ifdef DERIVATIVE
static int GlblDerivError; /* Global used by derivations */
#endif DERIVATIVE
/*****************************************************************************
* Routine to return one expression node from free list or allocate new one: *
*****************************************************************************/
static ExprNode *MyExprMalloc(void)
{
return (ExprNode *) malloc(sizeof(ExprNode));
}
/*****************************************************************************
* Routine to return one expression node: *
*****************************************************************************/
static void MyExprFree(ExprNode *Ptr)
{
free((char *) Ptr);
}
/*****************************************************************************
* Routine to convert lower case chars into upper one in the given string: *
*****************************************************************************/
static void MakeUpper(char *s)
{
int i = 0;
while (s[i] != NULL) {
if (islower(s[i])) s[i] = toupper(s[i]);
i++;
}
}
/*****************************************************************************
* Routine to convert the expression in string S into a binary tree. *
* Algorithm: Using operator precedence with the following grammer: *
* EXPR ::= EXPR | EXPR + EXPR | EXPR - EXPR *
* EXPR ::= EXPR | EXPR * EXPR | EXPR / EXPR *
* EXPR ::= EXPR | EXPR ^ EXPR *
* EXPR ::= NUMBER | -EXPR | (EXPR) | FUNCTION *
* FUCTION ::= SIN(EXPR) | COS(EXPR) | TAN(EXPR) | *
* ARCSIN(EXPR) | ARCCOS(EXPR) | ARCTAN(EXPR) | *
* SQRT(EXPR) | SQR(EXPR) | ABS(EXPR) | *
* LN(EXPR) | LOG(EXPR) | EXP(EXPR) *
* *
* And Left associativity for +, -, *, /, %, ^. *
* Precedence of operators is as usual: *
* <Highest> {unar minus} {^} {*, /, %, min, max} {+, -} <Lowest> *
* *
* Returns NULL if an error was found, and error is in GlblParsingError *
*****************************************************************************/
ExprNode *Expr2Tree(char *s)
{
ExprNode *Root;
int i = 0;
MakeUpper(s);
GlblLastToken = 0; /* Used to hold last token read from stream */
GlblParsingError = 0; /* No errors so far ... */
Root = OperatorPrecedence(s, &i);
if (GlblParsingError) return (ExprNode *) NULL; /* Error ! */
else return Root;
}
/*****************************************************************************
* Routine to actually parse using operator precedence: *
* Few Notes: *
* 1. Parse the string s with the help of GetToken routine. i holds current *
* position in string s. *
* 2. All tokens must be in the range of 0..999 as we use the numbers above *
* it (adding 1000) to deactivate them in the handle searching (i.e. when *
* they were reduced to sub.-expression). *
* 3. Returns NULL pointer in case of an error (see Expr2TrG.h for errors *
* 4. See "Compilers - principles, techniques and tools" by Aho, Sethi & *
* Ullman, pages 207-210. *
*****************************************************************************/
static ExprNode *OperatorPrecedence(char *s, int *i)
{
int Token, low_handle, Temp1, Temp2, StackPointer = 0, LoopOnEnd = 0;
double Data;
ExprNode *stack[MAX_PARSER_STACK];
/* Push the start symbol on stack (node pointer points on tos): */
stack[StackPointer] = MyExprMalloc();
stack[StackPointer] -> NodeKind = TOKENSTART;
stack[StackPointer] -> Right =
stack[StackPointer] -> Left = (ExprNode *) NULL;
Token = GetToken(s, i, &Data); /* Get one look ahead token to start with */
do {
if (GlblParsingError) return (ExprNode *) NULL;
Temp1 = StackPointer; /* Find top active token (less than 1000) */
while (stack[Temp1] -> NodeKind >= 1000) Temp1--;
/* Now test to see if the new token completes an handle: */
if (TestPreceeding(stack[Temp1] -> NodeKind, Token) > 0) {
switch (Token) {
case CLOSPARA:
if (stack[Temp1] -> NodeKind == OPENPARA) {
if (StackPointer-Temp1 != 1) {
GlblParsingError = P_ERR_ParaMatch;
return (ExprNode *) NULL;
}
switch (stack[Temp1-1] -> NodeKind) {
case ABS: /* If it is of the form Func(Expr) */
case ARCCOS: /* Then reduce it directly to that */
case ARCSIN: /* function, else (default) reduce */
case ARCTAN: /* to sub-expression. */
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN:
free(stack[Temp1]); /* Free the open paran. */
stack[StackPointer] -> NodeKind -= 1000;
stack[Temp1-1] -> NodeKind += 1000;
stack[Temp1-1] -> Right = stack[StackPointer];
StackPointer -= 2;
break;
default:
free(stack[Temp1]); /* Free the open paran. */
stack[Temp1] = stack[StackPointer--];
break;
}
Token = GetToken(s, i, &Data); /* Get another token */
continue;
}
else if (stack[Temp1] -> NodeKind == TOKENSTART) {
/* No match for this one! */
GlblParsingError = P_ERR_ParaMatch;
return (ExprNode *) NULL;
}
break;
case TOKENEND:
LoopOnEnd++;
if (stack[Temp1] -> NodeKind == TOKENSTART) {
if (StackPointer != 1) {
GlblParsingError = P_ERR_WrongSyntax;
return (ExprNode *) NULL;
}
stack[1] -> NodeKind -= 1000;
return stack[1];
}
}
Temp2 = Temp1-1; /* Find the lower bound of handle */
while (stack[Temp2] -> NodeKind >= 1000) Temp2--;
low_handle = Temp2 + 1;
if (low_handle < 1 || /* No low bound was found */
LoopOnEnd > 1000) { /* We are looping on EOS for ever... */
GlblParsingError = P_ERR_WrongSyntax;
return (ExprNode *) NULL; /* We ignore data till now */
}
switch (StackPointer - low_handle + 1) {
case 1: /* Its a scalar one - mark it as used (add 1000) */
switch (stack[StackPointer] -> NodeKind) {
case NUMBER:
case PARAMETER:
stack[StackPointer] -> NodeKind += 1000;
break;
default:
GlblParsingError = P_ERR_ParamExpect;
return (ExprNode *) NULL;
}
break;
case 2: /* Its a monadic operator - create the subtree */
switch (stack[StackPointer-1] -> NodeKind) {
case UNARMINUS:
stack[StackPointer-1] -> Right =
stack[StackPointer];
stack[StackPointer] -> NodeKind -= 1000;
stack[StackPointer-1] -> NodeKind += 1000;
StackPointer --;
break;
case OPENPARA:
GlblParsingError = P_ERR_ParaMatch;
return (ExprNode *) NULL;
default:
GlblParsingError = P_ERR_OneOperand;
return (ExprNode *) NULL;
}
break;
case 3: /* Its a diadic operator - create the subtree */
switch (stack[StackPointer-1] -> NodeKind) {
case PLUS:
case MINUS:
case MULT:
case DIV:
case MODULU:
case MINIMUM:
case MAXIMUM:
case POWER:
stack[StackPointer-1] -> Right =
stack[StackPointer];
stack[StackPointer-1] -> Left =
stack[StackPointer-2];
stack[StackPointer-2] -> NodeKind -= 1000;
stack[StackPointer] -> NodeKind -= 1000;
stack[StackPointer-1] -> NodeKind += 1000;
stack[StackPointer-2] = stack[StackPointer-1];
StackPointer -= 2;
break;
default:
GlblParsingError = P_ERR_TwoOperand;
return (ExprNode *) NULL;
}
break;
}
}
else { /* Push that token on stack - it is not handle yet */
stack[++StackPointer] = MyExprMalloc();
if (StackPointer == MAX_PARSER_STACK-1) {
GlblParsingError = P_ERR_StackOV;
return (ExprNode *) NULL; /* We ignore data till now */
}
stack[StackPointer] -> NodeKind = Token;
stack[StackPointer] -> Data = Data; /* We might need that... */
stack[StackPointer] -> Right =
stack[StackPointer] -> Left = (ExprNode *) NULL;
Token = GetToken(s, i, &Data); /* And get new token from stream */
}
}
while (TRUE);
}
/*****************************************************************************
* Routine to test precedence of two tokens. returns 0, <0 or >0 according *
* to comparison results: *
*****************************************************************************/
static int TestPreceeding(int Token1, int Token2)
{
int Preced1, Preced2;
if ((Token1 >= 1000) || (Token2 >= 1000)) return 0; /* Ignore sub-expr */
switch (Token1) {
case ABS:
case ARCCOS:
case ARCSIN:
case ARCTAN:
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN: Preced1 =100; break;
case NUMBER:
case PARAMETER: Preced1 =120; break;
case PLUS:
case MINUS: Preced1 = 20; break;
case MULT:
case DIV:
case MODULU:
case MINIMUM:
case MAXIMUM: Preced1 = 40; break;
case POWER: Preced1 = 60; break;
case UNARMINUS: Preced1 = 65; break;
case OPENPARA: Preced1 = 5; break;
case CLOSPARA: Preced1 =120; break;
case TOKENSTART:
case TOKENEND: Preced1 = 5; break;
}
switch (Token2) {
case ABS:
case ARCCOS:
case ARCSIN:
case ARCTAN:
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN: Preced2 = 90; break;
case NUMBER:
case PARAMETER: Preced2 =110; break;
case PLUS:
case MINUS: Preced2 = 10; break;
case MULT:
case DIV:
case MODULU:
case MINIMUM:
case MAXIMUM: Preced2 = 30; break;
case POWER: Preced2 = 50; break;
case UNARMINUS: Preced2 = 70; break;
case OPENPARA: Preced2 =110; break;
case CLOSPARA: Preced2 = 0; break;
case TOKENSTART:
case TOKENEND: Preced2 = 0; break;
}
return Preced1-Preced2;
}
/*****************************************************************************
* Routine to get the next token out of the expression. *
* Gets the expression in S, and current position in i. *
* Returns the next token found, set data to the returned value (if any), *
* and update i to one char ofter the new token found. *
* Note that in minus sign case, it is determined whether it is monadic or *
* diadic minus by the last token - if the last token was operator or '(' *
* it is monadic minus. *
*****************************************************************************/
static int GetToken(char *s, int *i, double *Data)
{
int j;
char Number[LINE_LEN], c;
while ((s[*i] == ' ') || (s[*i] == TAB)) (*i)++;
if (*i >= strlen(s)) return TOKENEND; /* No more tokens around here... */
/* Check is next token is one char - if so its a parameter */
if ((islower(s[*i]) || isupper(s[*i])) &&
!(islower(s[(*i)+1]) || isupper(s[(*i)+1]))) {
if (islower(c = s[(*i)++])) c = toupper(c); /* make parameter upcase */
*Data = c - 'A'; /* A = 0, B = 1, ... */
GlblLastToken = PARAMETER;
return PARAMETER;
}
if (isdigit(s[*i]) || (s[*i] == '.')) {
j=0;
while (isdigit(s[*i]) || (s[*i] == '.')) Number[j++] = s[(*i)++];
Number[j] = NULL;
sscanf(Number, "%lf", Data);
GlblLastToken = NUMBER;
return NUMBER;
}
switch (s[(*i)++]) {
case NULL: GlblLastToken = 0; return 0;
case '+': GlblLastToken = PLUS; return PLUS;
case '-':
switch (GlblLastToken) {
case NULL: /* If first token (no last token yet) */
case PLUS:
case MINUS:
case MULT:
case DIV:
case MODULU:
case MINIMUM:
case MAXIMUM:
case POWER:
case UNARMINUS:
case OPENPARA:
GlblLastToken= UNARMINUS; return UNARMINUS;
default:
GlblLastToken= MINUS; return MINUS;
}
case '*': GlblLastToken = MULT; return MULT;
case '/': GlblLastToken = DIV; return DIV;
case '%': GlblLastToken = MODULU; return MODULU;
case '^': GlblLastToken = POWER; return POWER;
case '(': GlblLastToken = OPENPARA; return OPENPARA;
case ')': GlblLastToken = CLOSPARA; return CLOSPARA;
case 'A':
if ((s[*i] == 'R') && (s[*i+1] == 'C')) {
(*i) += 2;
switch (GetToken(s, i, Data)) {
case SIN: GlblLastToken = ARCSIN; return ARCSIN;
case COS: GlblLastToken = ARCCOS; return ARCCOS;
case TAN: GlblLastToken = ARCTAN; return ARCTAN;
default:
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
}
else if ((s[*i] == 'B') && (s[*i+1] == 'S')) {
(*i) += 2;
GlblLastToken = ABS;
return ABS;
}
else {
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
case 'C':
if ((s[*i] == 'O') && (s[*i+1] == 'S')) {
(*i) += 2;
GlblLastToken = COS;
return COS;
}
else {
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
case 'E':
if ((s[*i] == 'X') && (s[*i+1] == 'P')) {
(*i) += 2;
GlblLastToken = EXP;
return EXP;
}
else {
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
case 'L':
if ((s[*i] == 'O') && (s[*i+1] == 'G')) {
(*i) += 2;
GlblLastToken = LOG;
return LOG;
}
else if (s[*i] == 'N') {
(*i)++;
GlblLastToken = LN;
return LN;
}
else {
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
case 'M':
if ((s[*i] == 'I') && (s[*i+1] == 'N')) {
(*i) += 2;
GlblLastToken = MINIMUM;
return MINIMUM;
}
else if ((s[*i]=='A') && (s[*i+1] == 'X')) {
(*i) += 2;
GlblLastToken = MAXIMUM;
return MAXIMUM;
}
else {
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
case 'S':
if ((s[*i] == 'I') && (s[*i+1] == 'N')) {
(*i) += 2;
GlblLastToken = SIN;
return SIN;
}
else if ((s[*i] == 'Q') && (s[*i+1] == 'R')) {
(*i) += 2;
if (s[*i] == 'T') {
(*i)++;
GlblLastToken = SQRT;
return SQRT;
}
else {
GlblLastToken = SQR;
return SQR;
}
}
else {
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
case 'T':
if ((s[*i] == 'A') && (s[*i+1] == 'N')) {
(*i) += 2;
GlblLastToken = TAN;
return TAN;
}
else return TOKENERROR;
default:
GlblParsingError = P_ERR_UndefToken;
return TOKENERROR;
}
}
/*****************************************************************************
* Routine to print a content of ROOT (using inorder traversal) : *
* Level holds: 0 for lowest level +/-, 1 for *, /, 2 for ^ operations. *
* If *str = NULL print on stdout, else on given string Str. *
*****************************************************************************/
void PrintTree(ExprNode *Root, char *Str)
{
char LocalStr[255];
strcpy(LocalStr, ""); /* Make the string empty */
if (Str == NULL) {
LocalPrintTree(Root, 0, LocalStr); /* Copy to local str. */
printf(LocalStr); /* and print... */
}
else {
strcpy(Str, ""); /* Make the string empty */
LocalPrintTree(Root, 0, Str); /* Dont print to stdout - copy to str */
}
}
/*****************************************************************************
* Routine to print a content of ROOT (using inorder traversal): *
* Level holds: 0 for lowest level +/-, 1 for *, /, 2 for ^ operations. *
*****************************************************************************/
static void LocalPrintTree(ExprNode *Root, int Level, char *Str)
{
int CloseFlag = FALSE;
if (!Root) return;
switch (Root->NodeKind) {
case ABS:
strcat(Str, "abs(");
Level = 0; /* Paranthesis are opened */
CloseFlag = TRUE; /* must close paranthesis */
break;
case ARCCOS:
strcat(Str, "arccos(");
Level = 0;
CloseFlag = TRUE;
break;
case ARCSIN:
strcat(Str, "arcsin(");
Level = 0;
CloseFlag = TRUE;
break;
case ARCTAN:
strcat(Str, "arctan(");
Level = 0;
CloseFlag = TRUE;
break;
case COS:
strcat(Str, "cos(");
Level = 0;
CloseFlag = TRUE;
break;
case EXP:
strcat(Str, "exp(");
Level = 0;
CloseFlag = TRUE;
break;
case LN:
strcat(Str, "ln(");
Level = 0;
CloseFlag = TRUE;
break;
case LOG:
strcat(Str, "log(");
Level = 0;
CloseFlag = TRUE;
break;
case SIN:
strcat(Str, "sin(");
Level = 0;
CloseFlag = TRUE;
break;
case SQR:
strcat(Str, "sqr(");
Level = 0;
CloseFlag = TRUE;
break;
case SQRT:
strcat(Str, "sqrt(");
Level = 0;
CloseFlag = TRUE;
break;
case TAN:
strcat(Str, "tan(");
Level = 0;
CloseFlag = TRUE;
break;
case PLUS:
if (Level >= 0) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 0; /* Plus Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, "+");
break;
case MINUS:
if (Level >= 0) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 0; /* Minus Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, "-");
break;
case MULT:
if (Level >= 1) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 1; /* Mul Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, "*");
break;
case DIV:
if (Level >= 1) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 1; /* Div Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, "/");
break;
case MODULU:
if (Level >= 1) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 1; /* Mod Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, "%");
break;
case MINIMUM:
if (Level >= 1) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 1; /* Min Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, " min ");
break;
case MAXIMUM:
if (Level >= 1) {
strcat(Str, "(");
CloseFlag = TRUE;
}
Level = 1; /* Max Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, " max ");
break;
case POWER:
Level = 2; /* Power Level */
LocalPrintTree(Root->Left, Level, Str);
strcat(Str, "^");
break;
case UNARMINUS:
strcat(Str, "(-");
Level = 0; /* Unarminus Level! */
CloseFlag = TRUE;
break;
case NUMBER:
sprintf(&Str[strlen(Str)], "%lg", Root->Data);
break;
case PARAMETER:
sprintf(&Str[strlen(Str)], "%c", (int) (Root->Data + 'A'));
break;
}
LocalPrintTree(Root->Right, Level, Str);
if (CloseFlag) strcat(Str, ")");
}
/*****************************************************************************
* Routine to create a new copy of a given tree: *
*****************************************************************************/
ExprNode *CopyTree(ExprNode *Root)
{
ExprNode *Node;
if (!Root) return NULL;
Node = MyExprMalloc();
switch (Root->NodeKind) {
case ABS:
case ARCSIN:
case ARCCOS:
case ARCTAN:
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN:
Node -> NodeKind = Root -> NodeKind;
Node -> Right = CopyTree(Root -> Right);
Node -> Left = NULL;
return Node;
case PLUS:
case MINUS:
case MULT:
case DIV:
case MODULU:
case POWER:
case MINIMUM:
case MAXIMUM:
case NUMBER:
case PARAMETER:
case UNARMINUS:
Node -> NodeKind = Root -> NodeKind;
if ((Root -> NodeKind == PARAMETER) ||
(Root -> NodeKind == NUMBER)) Node -> Data = Root -> Data;
Node -> Right = CopyTree(Root -> Right);
Node -> Left = CopyTree(Root -> Left);
return Node;
}
return NULL; /* Should never get here */
}
/*****************************************************************************
* Routine to evaluate a value of a given tree root and parameter. *
*****************************************************************************/
double EvalTree(ExprNode *Root)
{
int ITemp;
double Temp;
switch (Root->NodeKind) {
case ABS:
Temp = EvalTree(Root->Right);
return Temp > 0 ? Temp : -Temp;
case ARCSIN: return asin(EvalTree(Root->Right));
case ARCCOS: return acos(EvalTree(Root->Right));
case ARCTAN: return atan(EvalTree(Root->Right));
case COS: return cos(EvalTree(Root->Right));
case EXP: return exp(EvalTree(Root->Right));
case LN: return log(EvalTree(Root->Right));
case LOG: return log10(EvalTree(Root->Right));
case SIN: return sin(EvalTree(Root->Right));
case SQR: Temp = EvalTree(Root->Right); return Temp*Temp;
case SQRT: return sqrt(EvalTree(Root->Right));
case TAN: return tan(EvalTree(Root->Right));
case MODULU:
ITemp = (int) EvalTree(Root->Right);
if (ITemp != 0)
return (double) (((int) EvalTree(Root->Left)) % ITemp);
else {
GlblEvalError = E_ERR_DivByZero;
return EvalTree(Root->Left) * 1.0;
}
case DIV:
Temp = EvalTree(Root->Right);
if (Temp != 0.0)
return EvalTree(Root->Left) / Temp;
else {
GlblEvalError = E_ERR_DivByZero;
return EvalTree(Root->Left) * INFINITY;
}
case MINUS: return EvalTree(Root->Left) - EvalTree(Root->Right);
case MULT: return EvalTree(Root->Left) * EvalTree(Root->Right);
case PLUS: return EvalTree(Root->Left) + EvalTree(Root->Right);
case POWER: return pow(EvalTree(Root->Left), EvalTree(Root->Right));
case UNARMINUS: return -EvalTree(Root->Right);
case MINIMUM: return MIN(EvalTree(Root->Left), EvalTree(Root->Right));
case MAXIMUM: return MAX(EvalTree(Root->Left), EvalTree(Root->Right));
case NUMBER: return Root->Data;
case PARAMETER: return GlobalParam[(int) (Root->Data)];
}
return 0; /* Never get here (only make lint quite...) */
}
#ifdef DERIVATIVE
/*****************************************************************************
* Routine to generate the tree represent the derivative of tree root: *
*****************************************************************************/
ExprNode *DerivTree(ExprNode *Root, int Param)
{
int i, Flag = TRUE;
ExprNode *Node, *NewNode;
Node = DerivTree1(Root, Param);
if (!GlblDerivError) {
while (Flag) {
Flag = FALSE;
NewNode = Optimize(Node, &Flag);
FreeTree(Node); /* Release old tree area */
Node = NewNode;
}
for (i=0; i<10; i++) { /* Do more loops - might optimize by shift */
Flag = FALSE;
NewNode = Optimize(Node, &Flag);
FreeTree(Node); /* Release old tree area */
Node = NewNode;
}
}
return NewNode;
}
/*****************************************************************************
* Routine to generate non optimal derivative of the tree root : *
*****************************************************************************/
static ExprNode *DerivTree1(ExprNode *Root, int Param)
{
ExprNode *Node1, *Node2, *Node3, *Node4, *NodeMul;
NodeMul = MyExprMalloc();
NodeMul -> NodeKind = MULT;
switch (Root->NodeKind) {
case ABS:
GlblDerivError = D_ERR_NoAbsDeriv;
return NULL; /* No derivative ! */
case ARCSIN:
NodeMul->Left = Gen1u2Tree(PLUS, MINUS, -0.5,
CopyTree(Root->Right));
NodeMul->Right = DerivTree1(Root->Right, Param);
return NodeMul;
case ARCCOS:
NodeMul->Left = Gen1u2Tree(MINUS, MINUS, -0.5,
CopyTree(Root->Right));
NodeMul->Right = DerivTree1(Root->Right, Param);
return NodeMul;
case ARCTAN:
NodeMul->Left = Gen1u2Tree(PLUS, PLUS, -1.0,
CopyTree(Root->Right));
NodeMul->Right = DerivTree1(Root->Right, Param);
return NodeMul;
case COS:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node1 -> NodeKind = UNARMINUS;
Node2 -> NodeKind = SIN;
Node2 -> Right = CopyTree(Root->Right);
Node1 -> Left = Node2 -> Left = NULL;
Node1 -> Right = Node2;
NodeMul -> Left = Node1;
NodeMul -> Right = DerivTree1(Root->Right, Param);
return NodeMul;
case EXP:
Node1 = MyExprMalloc();
Node1 -> NodeKind = EXP;
Node1 -> Right = CopyTree(Root->Right);
NodeMul -> Left = Node1;
NodeMul -> Right = DerivTree1(Root->Right, Param);
return NodeMul;
case LN:
NodeMul -> NodeKind = DIV;
NodeMul -> Right = CopyTree(Root->Right);
NodeMul -> Left = DerivTree1(Root->Right, Param);
return NodeMul;
case LOG:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node1 -> NodeKind = DIV;
Node1 -> Right = CopyTree(Root->Right);
Node1 -> Left = DerivTree1(Root->Right, Param);
Node2 -> NodeKind = NUMBER;;
Node2 -> Data = log10(exp(1.0));
NodeMul -> Left = Node1;
NodeMul -> Right = Node2;
return NodeMul;
case SIN:
Node1 = MyExprMalloc();
Node1 -> NodeKind = COS;
Node1 -> Right = CopyTree(Root->Right);
Node1 -> Left = NULL;
NodeMul -> Left = Node1;
NodeMul -> Right = DerivTree1(Root->Right, Param);
return NodeMul;
case SQR:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node1 -> NodeKind = NUMBER;
Node1 -> Right = Node1 -> Left = NULL;
Node1 -> Data = 2.0;
Node2 -> NodeKind = MULT;;
Node2 -> Right = DerivTree1(Root->Right, Param);
Node2 -> Left = CopyTree(Root->Right);
NodeMul -> Left = Node1;
NodeMul -> Right = Node2;
return NodeMul;
case SQRT:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node3 = MyExprMalloc();
Node4 = MyExprMalloc();
Node1 -> NodeKind = NUMBER;
Node1 -> Right = Node1 -> Left = NULL;
Node1 -> Data = -0.5;
Node2 -> NodeKind = POWER;
Node2 -> Right = Node1;
Node2 -> Left = CopyTree(Root->Right);
Node3 -> NodeKind = NUMBER;
Node3 -> Right = Node3 -> Left = NULL;
Node3 -> Data = 0.5;
Node4 -> NodeKind = MULT;
Node4 -> Right = Node2;
Node4 -> Left = Node3;
NodeMul -> Left = Node4;
NodeMul -> Right = DerivTree1(Root->Right, Param);
return NodeMul;
case TAN:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node1 -> NodeKind = COS;
Node1 -> Left = NULL;
Node1 -> Right = CopyTree(Root->Right);
Node2 -> NodeKind = SQR;
Node2 -> Left = NULL;
Node2 -> Right = Node1;
NodeMul -> NodeKind = DIV;
NodeMul -> Right = Node2;
NodeMul -> Left = DerivTree1(Root->Right, Param);
return NodeMul;
case PLUS:
NodeMul -> NodeKind = PLUS;
NodeMul -> Left = DerivTree1(Root->Left, Param);
NodeMul -> Right = DerivTree1(Root->Right, Param);
return NodeMul;
case MINUS:
NodeMul -> NodeKind = MINUS;
NodeMul -> Left = DerivTree1(Root->Left, Param);
NodeMul -> Right = DerivTree1(Root->Right, Param);
return NodeMul;
case MULT:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node1 -> NodeKind = MULT;
Node1 -> Left = CopyTree(Root->Left);
Node1 -> Right = DerivTree1(Root->Right, Param);
Node2 -> NodeKind = MULT;
Node2 -> Left = DerivTree1(Root->Left, Param);
Node2 -> Right = CopyTree(Root->Right);
NodeMul -> NodeKind = PLUS;
NodeMul -> Left = Node1;
NodeMul -> Right = Node2;
return NodeMul;
case DIV:
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node3 = MyExprMalloc();
Node4 = MyExprMalloc();
Node1 -> NodeKind = MULT;
Node1 -> Left = CopyTree(Root->Left);
Node1 -> Right = DerivTree1(Root->Right, Param);
Node2 -> NodeKind = MULT;
Node2 -> Left = DerivTree1(Root->Left, Param);
Node2 -> Right = CopyTree(Root->Right);
Node3 -> NodeKind = MINUS;
Node3 -> Right = Node1;
Node3 -> Left = Node2;
Node4 -> NodeKind = SQR;
Node4 -> Right = CopyTree(Root->Right);
Node4 -> Left = NULL;
NodeMul -> NodeKind = DIV;
NodeMul -> Left = Node3;
NodeMul -> Right = Node4;
return NodeMul;
case MODULU:
GlblDerivError = D_ERR_NoModDeriv;
return NULL; /* No derivative! */
case POWER:
if (Root -> Right -> NodeKind != NUMBER) {
GlblDerivError = D_ERR_NoneConstExp;
return NULL;
}
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node3 = MyExprMalloc();
Node4 = MyExprMalloc();
Node1 -> NodeKind = NUMBER;
Node1 -> Left = Node1 -> Right = NULL;
Node1 -> Data = Root -> Right -> Data - 1;
Node2 -> NodeKind = POWER;
Node2 -> Left = CopyTree(Root->Left);
Node2 -> Right = Node1;
Node3 -> NodeKind = NUMBER;
Node3 -> Left = Node3 -> Right = NULL;
Node3 -> Data = Root -> Right -> Data;
Node4 -> NodeKind = MULT;
Node4 -> Right = Node2;
Node4 -> Left = Node3;
NodeMul -> Left = Node4;
NodeMul -> Right = DerivTree1(Root->Left, Param);
return NodeMul;
case MINIMUM: GlblDerivError = D_ERR_NoMinDeriv;
return NULL; /* No derivative! */
case MAXIMUM: GlblDerivError = D_ERR_NoMaxDeriv;
return NULL; /* No derivative! */
case UNARMINUS:
NodeMul -> NodeKind = UNARMINUS;
NodeMul -> Right = DerivTree1(Root->Right, Param);
NodeMul -> Left = NULL;
return NodeMul;
case NUMBER:
NodeMul -> NodeKind = NUMBER;
NodeMul -> Left = NodeMul -> Right = NULL;
NodeMul -> Data = 0.0;
return NodeMul;
case PARAMETER:
NodeMul -> NodeKind = NUMBER;
NodeMul -> Left = NodeMul -> Right = NULL;
if ((int) (Root->Data) == Param)
NodeMul -> Data = 1.0;
else NodeMul -> Data = 0.0;
return NodeMul;
}
return NULL; /* Should never get here */
}
/*****************************************************************************
* Routine to generate a tree to the expression: *
* SIGN1(1 SIGN2 SQR (EXPR)) ^ EXPONENT *
*****************************************************************************/
static ExprNode *Gen1u2Tree(int Sign1, int Sign2, double Exponent,
ExprNode *Expr)
{
ExprNode *Node1, *Node2, *Node3, *Node4, *Node5, *Node6;
Node1 = MyExprMalloc();
Node2 = MyExprMalloc();
Node3 = MyExprMalloc();
Node4 = MyExprMalloc();
Node5 = MyExprMalloc();
Node1 -> NodeKind = NUMBER;
Node1 -> Left = Node1 -> Right = NULL;
Node1 -> Data = 1.0;
Node2 -> NodeKind = SQR;
Node2 -> Right = CopyTree(Expr);
Node2 -> Left = NULL;
Node3 -> NodeKind = Sign2;
Node3 -> Left = Node1;
Node3 -> Right = Node2;
Node4 -> NodeKind = NUMBER;
Node4 -> Data = Exponent;
Node4 -> Right = Node4 -> Left = NULL;
Node5 -> NodeKind = POWER;
Node5 -> Right = Node4;
Node5 -> Left = Node3;
if (Sign1 == PLUS) return Node5;
else { /* Must be MINUS */
Node6 = MyExprMalloc();
Node6 -> NodeKind = UNARMINUS;
Node6 -> Left = NULL;
Node6 -> Right = Node5;
return Node6;
}
}
/*****************************************************************************
* Routine to optimize the binary tree : *
* Note: the old tree is NOT modified. flag returns TRUE if optimized. *
*****************************************************************************/
static ExprNode *Optimize(ExprNode *Root, int *Flag)
{
ExprNode *Node;
if (!Root) return NULL;
if ((Root -> NodeKind != NUMBER) &&
(!ParamInTree(Root, PARAMETER_ALL))) { /* The expression is constant */
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = NUMBER;
Node -> Data = EvalTree(Root);
Node -> Right = Node -> Left = NULL;
return Node;
}
/* Shift in Mult or Plus: A+(B+C) --> C+(A+B) */
if ((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))
if ((Root -> NodeKind == Root -> Right -> NodeKind) &&
((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))) {
Node = Root -> Left;
Root -> Left = Root -> Right -> Right;
Root -> Right -> Right = Root -> Right -> Left;
Root -> Right -> Left = Node;
}
/* Shift in Mult or Plus: (A+B)+C --> (C+A)+B */
if ((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))
if ((Root -> NodeKind == Root -> Left -> NodeKind) &&
((Root -> NodeKind == PLUS) || (Root -> NodeKind == MULT))) {
Node = Root -> Right;
Root -> Right = Root -> Left -> Left;
Root -> Left -> Left = Root -> Left -> Right;
Root -> Left -> Right = Node;
}
switch (Root->NodeKind) {
case DIV:
if ((Root -> Right -> NodeKind == NUMBER) &&
(Root -> Right -> Data == 1.0)) {
*Flag = TRUE;
return Optimize(Root -> Left, Flag); /* Div by 1 */
}
if ((Root -> Left -> NodeKind == NUMBER) &&
(Root -> Left -> Data == 0.0)) {
*Flag = TRUE;
return Optimize(Root -> Left, Flag); /* Div 0 - return 0 */
}
if (CmpTree(Root -> Left, Root -> Right)) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = NUMBER;
Node -> Data = 1.0;
Node -> Right = Node -> Left = NULL;
return Node; /* f/f == 1 */
}
break;
case MINUS:
if ((Root -> Right -> NodeKind == NUMBER) &&
(Root -> Right -> Data == 0.0)) {
*Flag = TRUE;
return Optimize(Root -> Left, Flag); /* X - 0 */
}
if ((Root -> Left -> NodeKind == NUMBER) &&
(Root -> Left -> Data == 0.0)) {
Node = MyExprMalloc();
Node -> NodeKind = UNARMINUS;
Node -> Left = NULL;
Node -> Right = Optimize(Root -> Right, Flag);
*Flag = TRUE;
return Node; /* (0 - X) --> -X */
}
if (CmpTree(Root -> Left, Root -> Right)) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = NUMBER;
Node -> Data = 0.0;
Node -> Right = Node -> Left = NULL;
return Node; /* f-f == 0.0 */
}
if (Root -> Right -> NodeKind == UNARMINUS) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = PLUS;
Node -> Left = Optimize(Root -> Left, Flag);
Node -> Right = Optimize(Root -> Right -> Right, Flag);
return Optimize(Node, Flag); /* a-(-b) --> a+b */
}
break;
case MULT:
if ((Root -> Right -> NodeKind == NUMBER) &&
((Root -> Right -> Data == 1.0) ||
(Root -> Right -> Data == 0.0))) {
*Flag = TRUE;
if (Root -> Right -> Data == 1.0)
return Optimize(Root -> Left, Flag); /* Mul by 1 */
else return Optimize(Root -> Right, Flag); /* Mul by 0 */
}
if ((Root -> Left -> NodeKind == NUMBER) &&
((Root -> Left -> Data == 1.0) ||
(Root -> Left -> Data == 0.0))) {
*Flag = TRUE;
if (Root -> Left -> Data == 1.0)
return Optimize(Root -> Right, Flag); /* Mul by 1 */
else return Optimize(Root -> Left, Flag); /* Mul by 0 */
}
if (CmpTree(Root -> Left, Root -> Right)) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = SQR;
Node -> Right = Optimize(Root -> Right, Flag);
Node -> Left = NULL;
return Node; /* f*f = f^2 */
}
break;
case PLUS:
if ((Root -> Right -> NodeKind == NUMBER) &&
(Root -> Right -> Data == 0.0)) {
*Flag = TRUE;
return Optimize(Root -> Left, Flag); /* Add 0 */
}
if ((Root -> Left -> NodeKind == NUMBER) &&
(Root -> Left -> Data == 0.0)) {
*Flag = TRUE;
return Optimize(Root -> Right, Flag); /* Add 0 */
}
if (CmpTree(Root -> Left, Root -> Right)) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = MULT;
Node -> Left = Optimize(Root -> Right, Flag);
Node -> Right = MyExprMalloc();
Node -> Right -> NodeKind = NUMBER;
Node -> Right -> Data = 2.0;
Node -> Right -> Left = Node -> Right -> Right = NULL;
return Node; /* f+f = f*2 */
}
if (Root -> Right -> NodeKind == UNARMINUS) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = MINUS;
Node -> Left = Optimize(Root -> Left, Flag);
Node -> Right = Optimize(Root -> Right -> Right, Flag);
return Optimize(Node, Flag); /* a+(-b) --> a-b */
}
if (Root -> Left -> NodeKind == UNARMINUS) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = MINUS;
Node -> Left = Optimize(Root -> Right, Flag);
Node -> Right = Optimize(Root -> Left -> Right, Flag);
return Optimize(Node, Flag); /* (-a)+b --> b-a */
}
break;
case POWER:
if ((Root -> Right -> NodeKind == NUMBER) &&
(Root -> Right -> Data == 0.0)) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = NUMBER;
Node -> Data = 1.0;
Node -> Right = Node -> Left = NULL;
return Node; /* f^0 == 1 */
}
if ((Root -> Right -> NodeKind == NUMBER) &&
(Root -> Right -> Data == 1.0)) {
*Flag = TRUE;
return Optimize(Root -> Left, Flag); /* f^1 = f */
}
break;
case UNARMINUS:
if (Root -> Right -> NodeKind == UNARMINUS) {
*Flag = TRUE;
return Optimize(Root -> Right -> Right, Flag); /* --a=a */
}
if (Root -> Right -> NodeKind == NUMBER) {
*Flag = TRUE;
Node = MyExprMalloc();
Node -> NodeKind = NUMBER;
Node -> Data = (- Root -> Right -> Data);
Node -> Right = Node -> Left = NULL;
return Node; /* Convert -(x) into (-x) */
}
break;
default:;
}
/* If we are here - no optimization took place : */
Node = MyExprMalloc();
Node -> NodeKind = Root -> NodeKind;
if ((Root -> NodeKind == PARAMETER) ||
(Root -> NodeKind == NUMBER)) Node -> Data = Root -> Data;
Node -> Right = Optimize(Root -> Right, Flag);
Node -> Left = Optimize(Root -> Left, Flag);
return Node;
}
#endif DERIVATIVE
/*****************************************************************************
* Routine to compere two trees - for equality: *
* The trees are compered to be symbolically equal i.e. A*B == B*A ! *
*****************************************************************************/
int CmpTree(ExprNode *Root1, ExprNode *Root2)
{
if (Root1->NodeKind != Root2->NodeKind) return FALSE;
switch (Root1->NodeKind) {
case ABS:
case ARCSIN:
case ARCCOS:
case ARCTAN:
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN:
case UNARMINUS:
return CmpTree(Root1->Right, Root2->Right);
case MULT: /* Note that A*B = B*A ! */
case PLUS:
case MINIMUM:
case MAXIMUM:
return ((CmpTree(Root1->Right, Root2->Right) &&
CmpTree(Root1->Left, Root2->Left)) ||
(CmpTree(Root1->Right, Root2->Left) &&
CmpTree(Root1->Left, Root2->Right)));
case DIV:
case MODULU:
case MINUS:
case POWER:
return (CmpTree(Root1->Right, Root2->Right) &&
CmpTree(Root1->Left, Root2->Left));
case NUMBER:
case PARAMETER:
return (Root1->Data == Root2->Data);
}
return FALSE; /* Should never get here */
}
/*****************************************************************************
* Routine to test if the parameter is in the tree : *
* If parameter == PARAMETER_ALL then any parameter return TRUE. *
*****************************************************************************/
int ParamInTree(ExprNode *Root, int Param)
{
if (!Root) return FALSE;
switch (Root->NodeKind) {
case ABS:
case ARCSIN:
case ARCCOS:
case ARCTAN:
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN:
case UNARMINUS:
return ParamInTree(Root->Right, Param);
case PLUS:
case MINUS:
case MULT:
case DIV:
case MODULU:
case MINIMUM:
case MAXIMUM:
case POWER:
return ParamInTree(Root->Right, Param) ||
ParamInTree(Root->Left, Param);
case NUMBER:
return FALSE;
case PARAMETER:
if (Param != PARAMETER_ALL)
return ((int) (Root->Data) == Param);
else return TRUE;
}
return FALSE; /* Should never get here */
}
/*****************************************************************************
* Routine to free a tree - release all memory allocated by it. *
*****************************************************************************/
void FreeTree(ExprNode *Root)
{
if (!Root) return;
switch (Root->NodeKind) {
case ABS:
case ARCSIN:
case ARCCOS:
case ARCTAN:
case COS:
case EXP:
case LN:
case LOG:
case SIN:
case SQR:
case SQRT:
case TAN:
case UNARMINUS:
FreeTree(Root->Right);
MyExprFree(Root);
break;
case PLUS:
case MINUS:
case MULT:
case DIV:
case MODULU:
case MINIMUM:
case MAXIMUM:
case POWER:
FreeTree(Root->Right);
FreeTree(Root->Left);
MyExprFree(Root);
break;
case NUMBER:
case PARAMETER:
MyExprFree(Root);
break;
}
}
/*****************************************************************************
* Routine to return parsing error if happen one, zero elsewhere *
*****************************************************************************/
int ParserError(void)
{
int Temp;
Temp = GlblParsingError;
GlblParsingError = 0;
return Temp;
}
#ifdef DERIVATIVE
/*****************************************************************************
* Routine to return derivate error if happen one, zero elsewhere *
*****************************************************************************/
int DerivError(void)
{
int Temp;
Temp = GlblDerivError;
GlblDerivError = 0;
return Temp;
}
#endif DERIVATIVE
/*****************************************************************************
* Routine to return evaluation error if happen one, zero elsewhere *
*****************************************************************************/
int EvalError(void)
{
int Temp;
Temp = GlblEvalError;
GlblEvalError = 0;
return Temp;
}
/*****************************************************************************
* Routine to set the value of a parameter before evaluating it. *
*****************************************************************************/
void SetParamValue(double Value, int Number)
{
if ((Number >= 0) && (Number <= PARAMETER_Z)) GlobalParam[Number] = Value;
}