New improved, or at least more functional, expression parser and evaluator.

Now can deal with both floating point and integer values.
You can use the functions from the standard C maths library which take
one argument.
Evaluation should be faster, 'though parsing is probably a bit slower.
Now the user-supplied evaluation routine is called just once at the
beginning of the evaluation, so if any of the evaluations need a global
operation, these can all be done at once.

The routines have now been renamed as Util_ functions and the
header file cctki_Expression.h has been renamed as util_Expression.h.

IMPORTANT NOTE:

The above means you will need to

rm configs/*/build/Cactus/util/Expression.c.d
rm configs/*/build/Cactus/main/Groups.c.d

after updating to get rid of stale dependency files.

Tom


git-svn-id: http://svn.cactuscode.org/flesh/trunk@2449 17b73243-c579-4c4c-a9d2-2d5706c11dac

3 files changed, 976 insertions, 268 deletions

diff --git a/src/include/cctki_Expression.h b/src/include/cctki_Expression.h
deleted file mode 100644
index 2e01075c..00000000
--- a/src/include/cctki_Expression.h
+++ /dev/null
@@ -1,29 +0,0 @@
- /*@@
-   @header    cctki_Expression.h
-   @date      Tue Sep 19 22:02:45 2000
-   @author    Tom Goodale
-   @desc 
-   Header for expression stuff.
-   @enddesc
-   @version $Header$
- @@*/
-
-#ifndef __CCTKI_EXPRESSION_H__
-#define __CCTKI_EXPRESSION_H__ 1
-
-#ifdef __cplusplus
-extern "C" 
-{
-#endif
-
-char *CCTKi_ExpressionParse(const char *expression);
-
-int CCTKi_ExpressionEvaluate(char *buffer, 
-                             int (eval)(const char *, void *),
-                             void *data);
-
-#ifdef __cplusplus
-}
-#endif
-
-#endif /* __CCTKI_EXPRESSION_H__ */
diff --git a/src/include/util_Expression.h b/src/include/util_Expression.h
new file mode 100644
index 00000000..85ead356
--- /dev/null
+++ b/src/include/util_Expression.h
@@ -0,0 +1,107 @@
+ /*@@
+   @header    util_Expression.h
+   @date      Tue Sep 19 22:02:45 2000
+   @author    Tom Goodale
+   @desc 
+   Header for expression stuff.
+   @enddesc
+   @version $Header$
+ @@*/
+
+#ifndef __UTIL_EXPRESSION_H__
+#define __UTIL_EXPRESSION_H__ 1
+
+#ifdef __cplusplus
+extern "C" 
+{
+#endif
+
+  /* These data types are for internal use only. */
+
+  /* Defined operators */
+typedef enum {OP_NONE,
+              OP_EQUALS,
+              OP_LESS_THAN,
+              OP_GREATER_THAN,
+              OP_LEQUALS,
+              OP_GEQUALS,
+              OP_AND,
+              OP_OR,
+              OP_PLUS,
+              OP_MINUS,
+              OP_DIV,
+              OP_TIMES,
+              OP_POWER,
+              OP_ACOS,
+              OP_ASIN,
+              OP_ATAN,
+              OP_CEIL,
+              OP_COS, 
+              OP_COSH,
+              OP_EXP,
+              OP_FABS,
+              OP_FLOOR,
+              OP_LOG,
+              OP_LOG10,
+              OP_SIN,
+              OP_SINH,
+              OP_SQRT,
+              OP_TAN,
+              OP_TANH}
+  uExpressionOpcode;
+
+  /* What sort of expression types we have. */
+typedef enum {val,unary,binary} uExpressionType;
+
+  /* RPN object. */
+typedef struct 
+{
+  uExpressionType type;
+
+  union
+  {
+    uExpressionOpcode opcode;
+    int varnum;
+  } token;
+} uExpressionToken;
+
+  /* Parsed expression object. */
+typedef struct
+{
+  int ntokens;
+  uExpressionToken *tokens;
+  int nvars;
+  const char **vars;
+} uExpressionInternals;
+
+/* Beginning of externally useable objects. */
+
+  /* Structure to hold values. */
+typedef struct 
+{
+  enum {rval,ival} type;
+  
+  union 
+  {
+    double rval;
+    int    ival;
+  } value;
+} uExpressionValue;
+
+  /* Externally visible representation of the expression. */
+typedef uExpressionInternals *uExpression;
+
+uExpression Util_ExpressionParse(const char *expression);
+
+int Util_ExpressionEvaluate(const uExpression buffer,
+                            uExpressionValue *retval,
+                            int (*eval)(int, const char * const *, uExpressionValue *, void *),
+                            void *data);
+
+void Util_ExpressionFree(uExpression buffer);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __UTIL_EXPRESSION_H__ */
diff --git a/src/util/Expression.c b/src/util/Expression.c
index 6c9e2888..0233a4fe 100644
--- a/src/util/Expression.c
+++ b/src/util/Expression.c
@@ -4,11 +4,13 @@
    @author    Tom Goodale
    @desc 
    Expression evaluator.
+   Can cope with arithmetic expressions and ones involving the standard 
+   C library mathematical functions (or those taking only one argument).
    @enddesc
    @version $Header$
  @@*/
 
-#ifndef TEST_CCTKI_EVALUATE
+#ifndef TEST_EXPRESSION_PARSER
 #include "cctk.h"
 #endif
 
@@ -16,11 +18,17 @@
 #include <stdlib.h>
 #include <string.h>
 
-#include "cctki_Expression.h"
+#include <math.h>
+
+#include "util_Expression.h"
 
 static const char *rcsid = "$Header$";
 
+#ifndef TEST_EXPRESSION_PARSER
+#include "util_String.h"
 CCTK_FILEVERSION(util_Expression_c)
+#define strdup(a) Util_Strdup(a)
+#endif
 
 /********************************************************************
  *********************     Local Data Types   ***********************
@@ -38,24 +46,31 @@ typedef struct PToken
  ********************************************************************/
 
 static pToken *Tokenise(const char *expression);
-static char *RPParse(pToken **current, char *stack, int *stacklength);
-static int Evaluate(int val1, const char *operator, int val2);
+int RPParse(pToken **current,uExpressionInternals *buffer);
+static int EvaluateBinary(uExpressionValue *retval, 
+                          const uExpressionValue *val1, 
+                          uExpressionOpcode opcode, 
+                          const uExpressionValue *val2);
+
+static int EvaluateUnary(uExpressionValue *retval, 
+                         uExpressionOpcode opcode, 
+                         const uExpressionValue *value);
 
 static int isoperator(const char *token);
 static int cmpprecendence(const char *op1, const char *op2);
+static int opencode(const char *operator, uExpressionType *type, uExpressionOpcode *opcode);
 
-static pToken *newtoken(const char *tokenstart, const char *tokenend);
+static int StoreVar(uExpressionInternals *buffer, const char *var);
 
-#if 0
-static void insertbefore(pToken *base, pToken *this);
-#endif
+static pToken *newtoken(const char *tokenstart, const char *tokenend);
+static void FreeTokens(pToken *list);
+static void insertafter(pToken *base, pToken *this);
 
-#ifdef TEST_CCTKI_EVALUATE
+#ifdef TEST_EXPRESSION_PARSER
+static const char *opname(uExpressionOpcode opcode);
 static void printtokens(pToken *start);
 #endif
 
-static void insertafter(pToken *base, pToken *this);
-static void FreeTokens(pToken *list);
 
 /********************************************************************
  ********************* Other Routine Prototypes *********************
@@ -65,57 +80,112 @@ static void FreeTokens(pToken *list);
  *********************     Local Data   *****************************
  ********************************************************************/
 
-#define INITIAL_BUFFER_LENGTH 1000
-#define MAX_STACK_SIZE 256
 #define MAX_OPS 100
+#define MAX_STACK_SIZE 256
+
+static struct
+{
+  const char *operator;
+  uExpressionType type;
+  int precedence;
+  uExpressionOpcode opcode;
+} operators[] = {
+  /* Binary operators. */
+  {"=",  binary, 1,OP_EQUALS},
+  {"<",  binary, 1,OP_LESS_THAN},
+  {">",  binary, 1,OP_GREATER_THAN},
+  {"<=", binary, 1,OP_LEQUALS},
+  {">=", binary, 1,OP_GEQUALS},
+  {"&&", binary, 2,OP_AND},
+  {"||", binary, 2,OP_OR},
+  {"+",  binary, 3,OP_PLUS},
+  {"-",  binary, 3,OP_MINUS},
+  {"/",  binary, 4,OP_DIV},
+  {"*",  binary, 4,OP_TIMES},
+  {"^",  binary, 5,OP_POWER},
+  /* Unary Operators - these must have the highest precedence. */
+  {"acos",  unary, 6, OP_ACOS},
+  {"asin",  unary, 6, OP_ASIN},
+  {"atan",  unary, 6, OP_ATAN},
+  {"ceil",  unary, 6, OP_CEIL},
+  {"cos" ,  unary, 6, OP_COS},  
+  {"cosh",  unary, 6, OP_COSH},
+  {"exp",   unary, 6, OP_EXP},
+  {"fabs",  unary, 6, OP_FABS},  
+  {"floor", unary, 6, OP_FLOOR},  
+  {"log",   unary, 6, OP_LOG},  
+  {"log10", unary, 6, OP_LOG10},
+  {"sin",   unary, 6, OP_SIN},  
+  {"sinh",  unary, 6, OP_SINH},  
+  {"sqrt",  unary, 6, OP_SQRT},  
+  {"tan",   unary, 6, OP_TAN},  
+  {"tanh",  unary, 6, OP_TANH},  
+  {NULL, binary, -1,OP_NONE}
+};
+
 
 /********************************************************************
  *********************     External Routines   **********************
  ********************************************************************/
 
  /*@@
-   @routine    CCTKi_ExpressionParse
+   @routine    Util_ExpressionParse
    @date       Tue Sep 19 21:23:08 2000
    @author     Tom Goodale
    @desc 
-   Parses an expression returning a predigested string in RPN.
+   Parses an expression returning a predigested representation
+   suitable for passing to ExpressionEvaluate.
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
+   @var     expression
+   @vdesc   Expression to parse
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
 
+   @returntype uExpression
+   @returndesc
+   The parsed form of the expression or NULL on error.
+   @endreturndesc
 @@*/
-char *CCTKi_ExpressionParse(const char *expression)
+uExpression Util_ExpressionParse(const char *expression)
 {
   pToken *list;
   pToken *temp;
 
-  char *buffer;
-  int buffer_length;
+  uExpressionInternals *buffer;
 
-  buffer_length = INITIAL_BUFFER_LENGTH;
-
-  buffer = (char *)malloc(buffer_length);
+  buffer = (uExpressionInternals *)malloc(sizeof(uExpressionInternals));
 
   if(buffer)
   {
+    /* Initialise the buffer */
+    buffer->ntokens = 0;
+    buffer->tokens  = NULL;
+    buffer->nvars   = 0;
+    buffer->vars    = NULL;
+
     /* FIXME: Don't really need a two pass algorithm here -
      *        it can all be done in one step.
      */
-
+  
     /* Split the list into tokens */
     list = Tokenise(expression);
-
-#ifdef TEST_CCTKI_EVALUATE    
+    
+#ifdef TEST_EXPRESSION_PARSER    
     printtokens(list);
 #endif
 
     temp = list;
 
     /* Convert the list into a string in RPN order */
-    buffer = RPParse(&temp, buffer, &buffer_length);
+    RPParse(&temp, buffer);
 
     FreeTokens(list);
   }
@@ -124,11 +194,11 @@ char *CCTKi_ExpressionParse(const char *expression)
 }
 
  /*@@
-   @routine    CCTKi_ExpressionEvaluate
+   @routine    Util_ExpressionEvaluate
    @date       Tue Sep 19 21:23:40 2000
    @author     Tom Goodale
    @desc 
-   Evaluates an parsed expression string created by CCTKI_ExpressionParse.
+   Evaluates a parsed expression created by Util_ExpressionParse.
    The user passes in a function which is used to evaluate all operands.
    @enddesc 
    @calls     
@@ -136,48 +206,219 @@ char *CCTKi_ExpressionParse(const char *expression)
    @history 
  
    @endhistory 
+   @var     buffer
+   @vdesc   The parsed expression
+   @vtype   const uExpression
+   @vio     in
+   @vcomment 
+   This expression should have been created by Util_ExpressionParse
+   @endvar 
+   @var     retval
+   @vdesc   The return value
+   @vtype   uExpressionValue *
+   @vio     out
+   @vcomment 
+   On exit contains the answer if there were no errors
+   @endvar 
+   @var     eval
+   @vdesc   Variable evaluation function
+   @vtype   int (*eval)(int, const char * const *, uExpressionValue *, void *),
+   @vio     in
+   @vcomment 
+   This function is called with an array of variables to determine the values of
+   and should return the corresponding values.
+   @endvar 
+   @var     data
+   @vdesc   Arbitrary data to be passed to user supplied function.
+   @vtype   void *
+   @vio     in
+   @vcomment 
+   This cna be anything the user needs to evaluate things.
+   @endvar 
+
+   @returntype int
+   @returndesc
+   +ve - success but there were this number of remaining operation on the stack.
+   0   - success
+   -ve - the number of remaining items on the expression stack when an error was
+   encountered
+   @endreturndesc
 
 @@*/
-int CCTKi_ExpressionEvaluate(char *buffer, 
-                             int (*eval)(const char *, void *),
-                             void *data)
+int Util_ExpressionEvaluate(const uExpression buffer,
+                            uExpressionValue *retval,
+                            int (*eval)(int, const char * const *, uExpressionValue *, void *),
+                            void *data)
 {
-  char *first;
-  char *token;
-  int stack[MAX_STACK_SIZE];
+  int retcode;
+  uExpressionValue stack[MAX_STACK_SIZE];
   int stackpointer;
+  int position;
 
+  uExpressionValue *varvals;
 
-  first = buffer;
+  retcode = 0;
   stackpointer = 0;
 
-  /* Tokens are seperated by @ signs */
-  while((token = strtok(first,"@")))
+  /* Assign memory for array to contain all variable values */
+  varvals = (uExpressionValue *)malloc(buffer->nvars*sizeof(uExpressionValue));
+
+  if(varvals)
   {
-    first = NULL;
+    /* Evaluate the variables in one go to help people doing parallel ops. */
+    eval(buffer->nvars, buffer->vars, varvals, data);
+  }
 
-    if(!isoperator(token))
+  /* Tokens are seperated by @ signs */
+  for(position = 0; position < buffer->ntokens; position++)
+  {
+    if(buffer->tokens[position].type == val)
     {
-      /* Evaluate and put on stack */
-      stack[stackpointer] = eval(token, data);
+      /* Put value on stack */
+      stack[stackpointer] = varvals[buffer->tokens[position].token.varnum];
+
       stackpointer++;
     }
     else
     {
-#ifdef TEST_CCTKI_EVALUATE
-      printf("Stackpointer is %d, %f %s %f = ", 
-             stackpointer, stack[stackpointer-2], token, stack[stackpointer-1]);
+#ifdef TEST_EXPRESSION_PARSER
+      
+      printf("Stackpointer is %d, ", stackpointer); 
+      if(buffer->tokens[position].type == binary)
+      {
+        switch(stack[stackpointer-2].type)
+        {
+          case ival:
+            printf("%d " ,stack[stackpointer-2].value.ival); break;
+          case rval:
+            printf("%f " ,stack[stackpointer-2].value.rval); break;
+          default:
+            ;
+        }
+      }
+
+      printf("%s ", opname(buffer->tokens[position].token.opcode));
+      switch(stack[stackpointer-1].type)
+      {
+        case ival:
+          printf("%d " ,stack[stackpointer-1].value.ival); break;
+        case rval:
+          printf("%f " ,stack[stackpointer-1].value.rval); break;
+        default:
+          ;
+      }
+      printf(" = ");
+      fflush(stdout);
 #endif
       /* Evaluate operation, clear operands from stack and add the result to the stack. */
-      stack[stackpointer-2] = Evaluate(stack[stackpointer-2],token,stack[stackpointer-1]);
-      stackpointer--;
-#ifdef TEST_CCTKI_EVALUATE
-      printf("%f\n", stack[stackpointer-1]); 
+      switch(buffer->tokens[position].type)
+      {
+        case binary:
+          if(stackpointer > 1)
+          {
+            EvaluateBinary(&(stack[stackpointer-2]),
+                           &(stack[stackpointer-2]),
+                           buffer->tokens[position].token.opcode,
+                           &(stack[stackpointer-1]));
+            stackpointer--;
+          }
+          else
+          {
+            retcode = -1;
+          }
+          break;
+        case unary:
+          if(stackpointer > 0)
+          {
+            EvaluateUnary(&(stack[stackpointer-1]),
+                          buffer->tokens[position].token.opcode,
+                          &(stack[stackpointer-1]));
+          }
+          else
+          {
+            retcode = -1;
+          }
+          break;
+        default :
+          ;
+      }
+
+#ifdef TEST_EXPRESSION_PARSER
+      if(!retcode)
+      {
+        switch(stack[stackpointer-1].type)
+        {
+          case ival:
+            printf("%d\n" ,stack[stackpointer-1].value.ival); break;
+          case rval:
+            printf("%f\n" ,stack[stackpointer-1].value.rval); break;
+          default:
+            ;
+        }
+      }
 #endif
     }
+    if(stackpointer < 0 || stackpointer > MAX_STACK_SIZE || retcode )
+    {
+      retcode = -1;
+      break;
+    }
   }
   
-  return stack[stackpointer-1];
+  if(varvals)
+  {
+    free(varvals);
+  }
+
+  if(retcode)
+  {
+    retcode = -1-stackpointer;
+  }
+  else
+  {
+    *retval=stack[stackpointer-1];
+    retcode = stackpointer-1;
+  }
+
+  return retcode;
+}
+
+ /*@@
+   @routine    Util_ExpressionFree
+   @date       Sat Nov  3 11:56:04 2001
+   @author     Tom Goodale
+   @desc 
+   Frees an expression buffer
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+   @var     buffer
+   @vdesc   Expression buffer to be freed.
+   @vtype   uExpression
+   @vio     inout
+   @vcomment 
+ 
+   @endvar 
+
+@@*/
+void Util_ExpressionFree(uExpression buffer)
+{
+  int i;
+
+  if(buffer)
+  {
+    free(buffer->tokens);
+    
+    for(i = 0; i < buffer->nvars; i++)
+    {
+      free((char *)(buffer->vars[i]));
+    }
+    free(buffer->vars);
+  }
+  free(buffer);
 }
 
 
@@ -197,6 +438,18 @@ int CCTKi_ExpressionEvaluate(char *buffer,
    @history 
  
    @endhistory 
+   @var     expression
+   @vdesc   Expression to be tokenised.
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+
+   @returntype pToken *
+   @returndesc
+   Linked list of tokens.
+   @endreturndesc
 
 @@*/
 static pToken *Tokenise(const char *expression)
@@ -231,6 +484,7 @@ static pToken *Tokenise(const char *expression)
         case '-' :
         case '/' :
         case '*' :
+        case '^' :
         case '(' :
         case ')' :
         case '<' :
@@ -261,6 +515,7 @@ static pToken *Tokenise(const char *expression)
             case '-' :
             case '/' :
             case '*' :
+            case '^' :
             case '(' :
             case ')' :
             case '=' :
@@ -319,65 +574,85 @@ static pToken *Tokenise(const char *expression)
   return start;
 }
 
+
  /*@@
    @routine    RPParse
    @date       Tue Sep 19 21:28:36 2000
    @author     Tom Goodale
    @desc 
-   Parses an toke list into Reverse Polish Notation (RPN).
+   Parses a token list into Reverse Polish Notation (RPN).
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
-
+   @var     current
+   @vdesc   Current token
+   @vtype   pToken **
+   @vio     inout
+   @vcomment 
+   This is the current token on input, and the new current token on output. 
+   @endvar 
+   @var     buffer
+   @vdesc   Expression buffer
+   @vtype   uExpressionInternals *
+   @vio     inout
+   @vcomment 
+   This is the buffer in which to store the parse results.
+   @endvar 
+
+   @returntype int
+   @returndesc
+   0 - success
+   @endreturndesc
 @@*/
-#define PUSH(stack, stacklength, value) do                        \
-{                                                                 \
-  int len = strlen(stack)+strlen(value)+3;                        \
-                                                                  \
-  if(len > stacklength)                                           \
-  {                                                               \
-    stack = (char *)realloc(stack, len);                          \
-  }                                                               \
-  sprintf(stack,"%s@%s",stack,value);                             \
+
+#define RESIZE_STACK(stack)                                                                \
+  (stack)->ntokens++;                                                                      \
+  (stack)->tokens = (uExpressionToken *)realloc((stack)->tokens,                           \
+                                                (stack)->ntokens*sizeof(uExpressionToken));\
+
+#define PUSHOP(stack, xtype, value) do                                                     \
+{                                                                                          \
+  RESIZE_STACK(stack)                                                                      \
+  (stack)->tokens[(stack)->ntokens-1].type = xtype;                                        \
+  (stack)->tokens[(stack)->ntokens-1].token.opcode = value;                                \
 } while(0)
 
+#define PUSHTOK(stack, xtype, value) do                                                    \
+{                                                                                          \
+  RESIZE_STACK(stack)                                                                      \
+  (stack)->tokens[(stack)->ntokens-1].type = xtype;                                        \
+  (stack)->tokens[(stack)->ntokens-1].token.varnum = value;        break;                  \
+} while(0)
 
-static char *RPParse(pToken **current, char *stack, int *stacklength)
+int RPParse(pToken **current, uExpressionInternals *buffer)
 {
-  char *retval;
+  int retcode;
   pToken *this;
   char *operator;
   char *opstack[MAX_OPS];
   int numops;
   int precedence;
+  int varnum;
+  uExpressionType optype;
+  uExpressionOpcode opcode;
 
   numops = 0;
   this = *current;
 
-  retval = stack;
+  retcode = 0;
 
   operator = NULL;
 
-  if(*stacklength > 0)
-  {
-    stack[0] = 0;
-  }
-  else
-  {
-    stack = (char *)malloc(sizeof(char));
-    *stacklength = 1;
-  }
-
   for(this = *current; this && strcmp(this->token,")"); this = this->next)
   {
     if(!strcmp(this->token, "(") && this->next)
     {
       /* This is a sub-group, so parse recursively */
       this = this->next;
-      retval = RPParse(&this, retval, stacklength);
+      retcode = RPParse(&this, buffer);
       if(! this)
       {
         break;
@@ -385,7 +660,8 @@ static char *RPParse(pToken **current, char *stack, int *stacklength)
     }
     else if(!isoperator(this->token))
     {
-      PUSH(retval, *stacklength, this->token);
+      varnum = StoreVar(buffer, this->token);
+      PUSHTOK(buffer, val, varnum);
     }
     else
     {
@@ -405,14 +681,16 @@ static char *RPParse(pToken **current, char *stack, int *stacklength)
         else
         {
           /* Lower or equal precedence */
-          PUSH(retval, *stacklength, operator);
+          opencode(operator, &optype, &opcode);
+          PUSHOP(buffer, optype, opcode);
           operator = this->token;
           while(numops > 0)
           {
             if(cmpprecendence(opstack[numops-1], operator) <=0)
             {
               numops--;
-              PUSH(retval, *stacklength, opstack[numops]);
+              opencode(opstack[numops], &optype, &opcode);
+              PUSHOP(buffer, optype, opcode);
             }
             else
             {
@@ -430,119 +708,267 @@ static char *RPParse(pToken **current, char *stack, int *stacklength)
 
   if(operator)
   {
-    PUSH(retval, *stacklength, operator);
+    opencode(operator, &optype, &opcode);
+    PUSHOP(buffer, optype, opcode);
     while(numops > 0)
     {
       numops--;
-      PUSH(retval, *stacklength, opstack[numops]);
+      opencode(opstack[numops], &optype, &opcode);
+      PUSHOP(buffer, optype, opcode);
     }
   }
 
   *current=this;
 
-  return retval;
+  return retcode;
 }
 
 
  /*@@
-   @routine    Evaluate
+   @routine    EvaluateBinary
    @date       Tue Sep 19 21:35:34 2000
    @author     Tom Goodale
    @desc 
-   Evaluates val1 op val2 
+   Evaluates the binary operation val1 op val2 
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
+   @var     retval
+   @vdesc   The result
+   @vtype   uExpressionValue *
+   @vio     out
+   @vcomment 
+ 
+   @endvar 
+   @var     val1
+   @vdesc   The first operand
+   @vtype   const uExpressionValue *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+   @var     opcode
+   @vdesc   The opcode of the operator.
+   @vtype   uExpressionOpcode
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+   @var     val2
+   @vdesc   The second operand
+   @vtype   const uExpressionValue *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
 
+   @returntype int
+   @returndesc
+   0 - success
+   @endreturndesc
 @@*/
-static int Evaluate(int val1, const char *operator, int val2)
+static int EvaluateBinary(uExpressionValue *retval, 
+                          const uExpressionValue *val1, 
+                          uExpressionOpcode opcode, 
+                          const uExpressionValue *val2)
 {
-  int retval;
-
-  if(!strcmp(operator, "+"))
-  {
-    retval = (val1+val2);
-  }
-  else if(!strcmp(operator, "-"))
-  {
-    retval = (val1-val2);
-  }
-  else if(!strcmp(operator, "/"))
-  {
-    retval = (val1/val2);
-  }
-  else if(!strcmp(operator, "*"))
-  {
-    retval = (val1*val2);
-  }
-  else if(!strcmp(operator, "&&"))
-  {
-    retval = (val1 && val2);
-  }
-  else if(!strcmp(operator, "||"))
-  {
-    retval = (val1 || val2);
-  }
-  else if(!strcmp(operator, "="))
-  {
-    retval = ( val1 == val2);
-  }
-  else if(!strcmp(operator, "<"))
-  {
-    retval = (val1 < val2);
+  
+  /* Define a macro so only have to do this once 
+   * irrespective of operand types.
+   */
+  #define EVALUATEBINARY(retval,val1,val2)             \
+  switch(opcode)                                       \
+  {                                                    \
+    case OP_PLUS :                                     \
+      (retval) = ((val1)+(val2));                      \
+      break;                                           \
+    case OP_MINUS :                                    \
+      (retval) = ((val1)-(val2));                      \
+      break;                                           \
+    case OP_DIV :                                      \
+      (retval) = ((val1)/(val2));                      \
+      break;                                           \
+    case OP_TIMES :                                    \
+      (retval) = ((val1)*(val2));                      \
+      break;                                           \
+    case OP_POWER :                                    \
+      (retval) = pow(val1,val2);                       \
+      break;                                           \
+    case OP_AND :                                      \
+      (retval) = ((val1) && (val2));                   \
+      break;                                           \
+    case OP_OR :                                       \
+      (retval) = ((val1) || (val2));                   \
+      break;                                           \
+    case OP_EQUALS :                                   \
+      (retval) = ( (val1) == (val2));                  \
+      break;                                           \
+    case OP_LESS_THAN :                                \
+      (retval) = ((val1) < (val2));                    \
+      break;                                           \
+    case OP_LEQUALS :                                  \
+      (retval) = ((val1) <= (val2));                   \
+      break;                                           \
+    case OP_GREATER_THAN :                             \
+      (retval) = ((val1) > (val2));                    \
+      break;                                           \
+    case OP_GEQUALS :                                  \
+      (retval) = ((val1) >= (val2));                   \
+      break;                                           \
+    default :                                          \
+      fprintf(stderr, "Unknown operation %d", opcode); \
+      (retval) = 0;                                    \
   }
-  else if(!strcmp(operator, "<="))
+
+  /* Need to decide where to get operands from and where to put them. */
+  if(val1->type==ival && val2->type==ival)
   {
-    retval = (val1 <= val2);
+    retval->type=ival;
+    EVALUATEBINARY(retval->value.ival,val1->value.ival,val2->value.ival);
   }
-  else if(!strcmp(operator, ">"))
+  else if(val1->type==rval && val2->type==ival)
   {
-    retval = (val1 > val2);
+    retval->type=rval;
+    EVALUATEBINARY(retval->value.rval,val1->value.rval,val2->value.ival);
   }
-  else if(!strcmp(operator, ">="))
+  else if(val1->type==ival && val2->type==rval)
   {
-    retval = (val1 >= val2);
+    retval->type=rval;
+    EVALUATEBINARY(retval->value.rval,val1->value.ival,val2->value.rval);
   }
-  else
+  else /* if(val1->type==rval && val2->type==rval) */
   {
-    fprintf(stderr, "Unknown operation %s", operator);
-    retval = 0;
+    retval->type=rval;
+    EVALUATEBINARY(retval->value.rval,val1->value.rval,val2->value.rval);
   }
 
-  return retval;
+  return 0;
 }
-  
+
  /*@@
-   @routine    FreeTokens
-   @date       Tue Sep 19 21:39:07 2000
+   @routine    EvaluateUnary
+   @date       Sun Nov  4 22:18:50 2001
    @author     Tom Goodale
    @desc 
-   Frees a list of tokens.
+   Evaluates a unary operation on value
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
-
+   @var     retval
+   @vdesc   The result
+   @vtype   uExpressionValue *
+   @vio     out
+   @vcomment 
+ 
+   @endvar 
+ 
+   @endvar 
+   @var     opcode
+   @vdesc   The opcode of the operator.
+   @vtype   uExpressionOpcode
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+   @var     value
+   @vdesc   The operand
+   @vtype   const uExpressionValue *
+   @vio     in
+   @vcomment 
+
+   @returntype int
+   @returndesc
+   0 - success
+   @endreturndesc
 @@*/
-void FreeTokens(pToken *list)
+static int EvaluateUnary(uExpressionValue *retval, 
+                         uExpressionOpcode opcode, 
+                         const uExpressionValue *value)
 {
-  pToken *token;
-  pToken *next;
+  
+  #define UNARYMATHOPERATE(a) \
+    case OP_##a :             \
+      (retval) = a(val);      \
+      break;
 
-  for(token = list; token; token = next)
+  #define EVALUATEUNARY(retval, val)                   \
+  switch(opcode)                                       \
+  {                                                    \
+    case OP_ACOS :                                     \
+      (retval) = acos(val);                            \
+      break;                                           \
+    case OP_ASIN :                                     \
+      (retval) = asin(val);                            \
+      break;                                           \
+    case OP_ATAN :                                     \
+      (retval) = atan(val);                            \
+      break;                                           \
+    case OP_CEIL :                                     \
+      (retval) = ceil(val);                            \
+      break;                                           \
+    case OP_COS :                                      \
+      (retval) = cos(val);                             \
+      break;                                           \
+    case OP_COSH :                                     \
+      (retval) = cosh(val);                            \
+      break;                                           \
+    case OP_EXP :                                      \
+      (retval) = exp(val);                             \
+      break;                                           \
+    case OP_FABS :                                     \
+      (retval) = fabs(val);                            \
+      break;                                           \
+    case OP_FLOOR :                                    \
+      (retval) = floor(val);                           \
+      break;                                           \
+    case OP_LOG :                                      \
+      (retval) = log(val);                             \
+      break;                                           \
+    case OP_LOG10 :                                    \
+      (retval) = log10(val);                           \
+      break;                                           \
+    case OP_SIN :                                      \
+      (retval) = sin(val);                             \
+      break;                                           \
+    case OP_SINH :                                     \
+      (retval) = sinh(val);                            \
+      break;                                           \
+    case OP_SQRT :                                     \
+      (retval) = sqrt(val);                            \
+      break;                                           \
+    case OP_TAN :                                      \
+      (retval) = tan(val);                             \
+      break;                                           \
+    case OP_TANH :                                     \
+      (retval) = tanh(val);                            \
+      break;                                           \
+    default :                                          \
+      fprintf(stderr, "Unknown operation %d", opcode); \
+      (retval) = 0;                                    \
+  }
+
+  if(value->type==ival)
   {
-    next = token->next;
-    free(token->token);
-    free(token);
+    retval->type=rval;
+    EVALUATEUNARY(retval->value.rval,value->value.ival);
   }
+  else /* if(val->type==rval) */
+  {
+    retval->type=rval;
+    EVALUATEUNARY(retval->value.rval,value->value.rval);
+  }
+
+  return 0;
 }  
 
 
+
  /*@@
    @routine    isoperator
    @date       Tue Sep 19 21:30:20 2000
@@ -555,29 +981,35 @@ void FreeTokens(pToken *list)
    @history 
  
    @endhistory 
+   @var     token
+   @vdesc   Token to test.
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
 
+   @returntype int
+   @returndesc
+   1 - is an operator
+   0 - is not an operator
+   @endreturndesc
 @@*/
 static int isoperator(const char *token)
 {
   int retval;
   
-  if(!strcmp(token, "+") ||
-     !strcmp(token, "-") ||
-     !strcmp(token, "/") ||
-     !strcmp(token, "*") ||
-     !strcmp(token, "&&") ||
-     !strcmp(token, "||") ||
-     !strcmp(token, "=") ||
-     !strcmp(token, "<") ||
-     !strcmp(token, "<=") ||
-     !strcmp(token, ">") ||
-     !strcmp(token, ">="))
-  {
-    retval = 1;
-  }
-  else
+  int i;
+
+  retval = 0;
+
+  for(i=0; operators[i].operator; i++)
   {
-    retval = 0;
+    if(!strcmp(operators[i].operator,token))
+    {
+      retval = 1;
+      break;
+    }
   }
 
   return retval;
@@ -595,54 +1027,183 @@ static int isoperator(const char *token)
    @history 
  
    @endhistory 
-
+   @var     op1
+   @vdesc   First operator
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+   @var     op2
+   @vdesc   Second operator
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+
+   @returntype int
+   @returndesc
+   +ve - op1 is higher precedence than op2
+     0 - op1 and op2 are of equal precedence
+   -ve - op2 is higher precedence than op1
+   @endreturndesc
 @@*/
 static int cmpprecendence(const char *op1, const char *op2)
 {
   int retval;
-  const char *op;
+  int i;
   int op1prec;
   int op2prec;
-  int *prec;
 
-  /* Work out the precedence level for each operator */
-  for(op = op1, prec = &op1prec; 
-      op ; 
-      op = (op == op1 ) ? op2 : NULL, 
-      prec = (op == op1) ? &op1prec : &op2prec)
+  op1prec = -1;
+  op2prec = -1;
+
+  for(i=0; operators[i].operator; i++)
   {
-    if(!strcmp(op, "=") ||
-       !strcmp(op, "<") ||
-       !strcmp(op, "<=") ||
-       !strcmp(op, ">") ||
-       !strcmp(op, ">="))
+    if(!strcmp(operators[i].operator,op1))
     {
-      *prec = 1;
+      op1prec = operators[i].precedence;
     }
-    else if(!strcmp(op, "&&") ||
-       !strcmp(op, "||"))
+    if(!strcmp(operators[i].operator,op2))
     {
-      *prec = 2;
+      op2prec = operators[i].precedence;
     }
-    else if(!strcmp(op, "+") ||
-            !strcmp(op, "-"))
+
+    if(op1prec != -1 && op2prec != -1)
     {
-      *prec = 3;
+      break;
     }
-    else if(!strcmp(op, "/") ||
-            !strcmp(op, "*"))
+  }
+
+  /* Now see which has the higher precedence */
+  retval = op2prec-op1prec;
+
+  return retval;
+}
+
+ /*@@
+   @routine    opencode
+   @date       Sun Nov  4 22:05:36 2001
+   @author     Tom Goodale
+   @desc 
+   Finds the encoding for a given operator.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+   @var     operator
+   @vdesc   The operator to get info on.
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+   @var     type
+   @vdesc   Operator type
+   @vtype   uExpressionType *
+   @vio     out
+   @vcomment 
+ 
+   @endvar 
+   @var     opcode
+   @vdesc   The operator's opcode
+   @vtype   uExpressionOpcode
+   @vio     out
+   @vcomment 
+ 
+   @endvar 
+
+   @returntype int
+   @returndesc
+   0  - success
+   -1 - operator doesn't exist
+   @endreturndesc
+@@*/
+static int opencode(const char *operator, uExpressionType *type, uExpressionOpcode *opcode)
+{
+  int retcode;
+  int i;
+
+  retcode = -1;
+  for(i=0; operators[i].operator; i++)
+  {
+    if(!strcmp(operators[i].operator,operator))
     {
-      *prec = 4;
+      retcode = 0;
+      *type   = operators[i].type;
+      *opcode = operators[i].opcode;
+      break;
     }
-    else
+  }
+  return retcode;
+}
+
+
+ /*@@
+   @routine    StoreVar
+   @date       Sun Nov  4 22:09:34 2001
+   @author     Tom Goodale
+   @desc 
+   Stores a variable name in an expression buffer.
+   If the variable already exists, it returns the
+   old number, otherwise it saves the variable and
+   returns its new number.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+   @var     buffer
+   @vdesc   Buffer in which to store the name
+   @vtype   uExpressionInternals *
+   @vio     inout
+   @vcomment 
+ 
+   @endvar 
+   @var     var
+   @vdesc   The variable to be stored.
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+
+   @returntype int
+   @returndesc
+   The assigned variable number
+   @endreturndesc
+@@*/
+static int StoreVar(uExpressionInternals *buffer, const char *var)
+{
+  int retval;
+  int i;
+
+  retval = -1;
+
+  /* Look for old value. */
+  for(i = 0; i < buffer->nvars; i++)
+  {
+    if(!strcmp(buffer->vars[i],var))
     {
-      fprintf(stderr, "Unknown operator '%s'\n", op);
-      *prec = 0;
+      retval = i;
+      break;
     }
   }
 
-  /* Now see which has the higher precedence */
-  retval = op2prec-op1prec;
+  /* If the variable is new, resize list and add it. */
+  if(retval == -1)
+  {
+    buffer->nvars++;
+    buffer->vars = (const char **)realloc(buffer->vars,sizeof(const char *)*buffer->nvars);
+    
+    buffer->vars[buffer->nvars-1] = strdup(var);
+
+    retval = buffer->nvars-1;
+  }
 
   return retval;
 }
@@ -652,14 +1213,33 @@ static int cmpprecendence(const char *op1, const char *op2)
    @date       Tue Sep 19 21:30:42 2000
    @author     Tom Goodale
    @desc 
-   Creates a new token item.
+   Creates a new token item given the beginning and end of
+   the string containing the token.
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
+   @var     tokenstart
+   @vdesc   pointer to first charater in token
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
+   @var     tokenend
+   @vdesc   pointer to last charater in token
+   @vtype   const char *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
 
+   @returntype pToken *
+   @returndesc
+   The new token object
+   @endreturndesc
 @@*/
 static pToken *newtoken(const char *tokenstart, const char *tokenend)
 {
@@ -699,11 +1279,11 @@ static pToken *newtoken(const char *tokenstart, const char *tokenend)
 }
 
  /*@@
-   @routine    insertbefore
-   @date       Tue Sep 19 21:33:39 2000
+   @routine    FreeTokens
+   @date       Tue Sep 19 21:39:07 2000
    @author     Tom Goodale
    @desc 
-   Inserts a token before another one in a list.
+   Frees a list of tokens.
    @enddesc 
    @calls     
    @calledby   
@@ -712,23 +1292,19 @@ static pToken *newtoken(const char *tokenstart, const char *tokenend)
    @endhistory 
 
 @@*/
-#if 0
-static void insertbefore(pToken *base, pToken *this)
+void FreeTokens(pToken *list)
 {
-  if(base && this)
-  {
-    this->next = base;
-    this->last = base->last;
-    base->last = this;
+  pToken *token;
+  pToken *next;
 
-    if(this->last)
-    {
-      this->last->next = this;
-    }
+  for(token = list; token; token = next)
+  {
+    next = token->next;
+    free(token->token);
+    free(token);
   }
-}
-#endif
-    
+}  
+
  /*@@
    @routine    insertafter
    @date       Tue Sep 19 21:34:02 2000
@@ -741,6 +1317,20 @@ static void insertbefore(pToken *base, pToken *this)
    @history 
  
    @endhistory 
+   @var     base
+   @vdesc   The base of the list
+   @vtype   pToken *
+   @vio     inout
+   @vcomment 
+ 
+   @endvar 
+   @var     this
+   @vdesc   Token to add to list.
+   @vtype   pToken *
+   @vio     inout
+   @vcomment 
+ 
+   @endvar 
 
 @@*/
 static void insertafter(pToken *base, pToken *this)
@@ -758,102 +1348,142 @@ static void insertafter(pToken *base, pToken *this)
   }
 }
   
+#if TEST_EXPRESSION_PARSER
+
  /*@@
-   @routine    printtokens
-   @date       Tue Sep 19 21:34:24 2000
+   @routine    opname
+   @date       Sun Nov  4 22:08:10 2001
    @author     Tom Goodale
    @desc 
-   Debugging function to print out the tokens.
+   Finds the name of an operator.
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
+   @var     opcode
+   @vdesc   The operator's opcode
+   @vtype   uExpressionOpcode
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
 
+   @returntype const char *
+   @returndesc
+   The operator's name or NULL if it doesn't exist.
+   @endreturndesc
 @@*/
-#if TEST_CCTKI_EVALUATE
-static void printtokens(pToken *start)
+static const char *opname(uExpressionOpcode opcode)
 {
-  pToken *token;
+  const char *retval;
+  int i;
 
-  for(token = start; token; token = token->next)
+  retval = NULL;
+
+  for(i=0; operators[i].operator; i++)
   {
-    printf("->%s", token->token);
+    if(operators[i].opcode == opcode)
+    {
+      retval = operators[i].operator;
+      break;
+    }
   }
-
-  printf("\n");
+  return retval;
 }
-#endif /* TEST_CCTKI_EVALUATE */
-
  /*@@
-   @routine    printstack
-   @date       Tue Sep 19 21:34:48 2000
+   @routine    printtokens
+   @date       Tue Sep 19 21:34:24 2000
    @author     Tom Goodale
    @desc 
-   Debugging function to print out a predigested string.
-   Note that is modifies the string, so it should be passed
-   a copy.
+   Debugging function to print out the tokens.
    @enddesc 
    @calls     
    @calledby   
    @history 
  
    @endhistory 
+   @var     start
+   @vdesc   First token in list
+   @vtype   pToken *
+   @vio     in
+   @vcomment 
+ 
+   @endvar 
 
 @@*/
-#if 0
-static void printstack(char *stack)
+static void printtokens(pToken *start)
 {
-  char *first;
-  char *token;
-
-  first = stack;
+  pToken *token;
 
-  while((token = strtok(first,"@")))
+  for(token = start; token; token = token->next)
   {
-    first = NULL;
-    printf("Token is %s\n", token);
+    printf("->%s", token->token);
   }
+
+  printf("\n");
 }
-#endif
+#endif /* TEST_EXPRESSION_PARSER */
 
 
 /********************************************************************
  *********************     TEST FUNCTIONS   *************************
  ********************************************************************/
 
-#ifdef TEST_CCTKI_EVALUATE
+#ifdef TEST_EXPRESSION_PARSER
 
-int evaluator(const char *token, void *data)
+int evaluator(int nvars, const char * const *vars, uExpressionValue *vals, void *data)
 {
-  int retval;
-
-  retval = strtod(token, NULL);
+  int i;
 
-  /*  fprintf(stderr, "Evaluated '%s' to %f\n", token,retval); */
+  for(i = 0; i < nvars; i++)
+  {
+    if(strchr(vars[i],'.'))
+    {
+      vals[i].type = rval;
+      vals[i].value.rval = strtod(vars[i], NULL);
+    }
+    else
+    {
+      vals[i].type = ival;
+      vals[i].value.ival = strtol(vars[i], NULL,0);
+    }    
+  }
 
-  return retval;
+  return 0;
 }
 
 
 int main(int argc, char *argv[])
 {
-  char *buffer;
+  uExpression buffer;
+  uExpressionValue value;
 
+  value.type = ival;
+  
   if(argc < 2)
   {
     printf("Usage: %s \"string\"\n", argv[0]);
     exit(0);
   }
 
-  buffer = CCTKi_ExpressionParse(argv[1]);
+  buffer = Util_ExpressionParse(argv[1]);
 
-  printf("Value is %f\n", CCTKi_ExpressionEvaluate(buffer, evaluator,NULL)); 
-  
-  free(buffer);
+  Util_ExpressionEvaluate(buffer, &value,evaluator,NULL);
+
+  if(value.type==ival)
+  {
+    printf("Value is %d\n", value.value.ival); 
+  }
+  else
+  {
+    printf("Value is %f\n", value.value.rval); 
+  }
+
+  Util_ExpressionFree(buffer);
 
   return 0;
 }
   
-#endif /* TEST_CCTKI_EVALUATE */    
+#endif /* TEST_EXPRESSION_PARSER */