Adding a primitive expression parser. It will parse simple

expressions such as a + b/(c+(d+f)) correctly, but mucks up
things like a+ b/c/d as it doesn't look too hard for places
to put brackets in.  A fully parenthesised expression should
be fine.

It also doesn't have good error checking.

All thing improve with time...  (well most, anyway 8-)

Tom


git-svn-id: http://svn.cactuscode.org/arrangements/CactusConnect/HTTPD/trunk@51 1faa4e14-9dd3-4be0-9f0e-ffe519881164

3 files changed, 851 insertions, 1 deletions

diff --git a/src/Expression.c b/src/Expression.c
new file mode 100644
index 0000000..44b0872
--- /dev/null
+++ b/src/Expression.c
@@ -0,0 +1,823 @@
+ /*@@
+   @file      Expression.c
+   @date      Tue Sep 19 13:25:39 2000
+   @author    Tom Goodale
+   @desc 
+   Expression evaluator.
+   @enddesc
+   @version $Header$
+ @@*/
+
+#include "cctk.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+static char *rcsid = "$Header$";
+
+#ifdef CCTK_FILEVERSION
+CCTK_FILEVERSION(DevThorns_httpd_Expression_c)
+#endif
+
+/********************************************************************
+ *********************     Local Data Types   ***********************
+ ********************************************************************/
+
+typedef struct PToken
+{
+  struct PToken *last;
+  struct PToken *next;
+  char *token;
+} pToken;
+
+/********************************************************************
+ ********************* Local Routine Prototypes *********************
+ ********************************************************************/
+
+static pToken *Tokenise(const char *expression);
+static pToken *ParenthesiseList(pToken *list);
+static char *RPParse(pToken **current, char *stack, int *stacklength);
+static double Evaluate(double val1, const char *operator, double val2);
+
+static int isoperator(const char *token);
+
+static pToken *newtoken(const char *tokenstart, const char *tokenend);
+
+static void insertbefore(pToken *base, pToken *this);
+static void insertafter(pToken *base, pToken *this);
+static void FreeTokens(pToken *list);
+
+static void printtokens(pToken *start);
+
+/********************************************************************
+ ********************* Other Routine Prototypes *********************
+ ********************************************************************/
+
+/********************************************************************
+ *********************     Local Data   *****************************
+ ********************************************************************/
+
+#define INITIAL_BUFFER_LENGTH 1000
+#define MAX_STACK_SIZE 256
+
+/********************************************************************
+ *********************     External Routines   **********************
+ ********************************************************************/
+
+ /*@@
+   @routine    HTTP_ExpressionParse
+   @date       Tue Sep 19 21:23:08 2000
+   @author     Tom Goodale
+   @desc 
+   Parses an expression returning a predigested string in RPN.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+char *HTTP_ExpressionParse(const char *expression)
+{
+  pToken *list;
+  pToken *temp;
+
+  char *buffer;
+  int buffer_length;
+
+  buffer_length = INITIAL_BUFFER_LENGTH;
+
+  buffer = (char *)malloc(buffer_length);
+
+  if(buffer)
+  {
+    /* Split the list into tokens */
+    list = Tokenise(expression);
+
+    /* Add any extra parentheses to the list */
+    list = ParenthesiseList(list);
+    
+#ifdef TEST_HTTP_EVALUATE    
+    printtokens(list);
+#endif
+
+    temp = list;
+
+    /* Convert the list into a string in RPN order */
+    buffer = RPParse(&temp, buffer, &buffer_length);
+
+    FreeTokens(list);
+  }
+
+  return buffer;
+}
+
+ /*@@
+   @routine    HTTP_ExpressionEvaluate
+   @date       Tue Sep 19 21:23:40 2000
+   @author     Tom Goodale
+   @desc 
+   Evaluates an parsed expression string created by HTTP_ExpressionParse.
+   The user passes in a function which is used to evaluate all operands.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+double HTTP_ExpressionEvaluate(char *buffer, double (*eval)(const char *))
+{
+  char *first;
+  char *token;
+  double stack[MAX_STACK_SIZE];
+  int stackpointer;
+
+
+  first = buffer;
+  stackpointer = 0;
+
+  /* Tokens are seperated by @ signs */
+  while((token = strtok(first,"@")))
+  {
+    first = NULL;
+
+    if(!isoperator(token))
+    {
+      /* Evaluate and put on stack */
+      stack[stackpointer] = eval(token);
+      stackpointer++;
+    }
+    else
+    {
+#ifdef TEST_HTTP_EVALUATE
+      printf("Stackpointer is %d, %f %s %f = ", 
+             stackpointer, stack[stackpointer-2], token, stack[stackpointer-1]);
+#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_HTTP_EVALUATE
+      printf("%f\n", stack[stackpointer-1]); 
+#endif
+    }
+  }
+  
+  return stack[stackpointer-1];
+}
+
+
+/********************************************************************
+ *********************     Local Routines   *************************
+ ********************************************************************/
+
+ /*@@
+   @routine    Tokenise
+   @date       Tue Sep 19 21:25:18 2000
+   @author     Tom Goodale
+   @desc 
+   Split an expression into tokens
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static pToken *Tokenise(const char *expression)
+{
+  pToken *start;
+  pToken *current;
+  pToken *new;
+
+  const char *tokenstart;
+  const char *tokenend;
+  const char *position;
+
+  start   = NULL;
+  current = NULL;
+
+  tokenstart = expression;
+
+  while(*tokenstart)
+  {
+    /* Remove leading whitespace */ 
+    for(; *tokenstart == ' ' || *tokenstart == '\t'; tokenstart++);
+
+    tokenend = NULL;
+
+    position = tokenstart;
+
+    for(position=tokenstart; *position && *(position+1); position++)
+    {
+      switch(*(position+1))
+      {
+        case '+' :
+        case '-' :
+        case '/' :
+        case '*' :
+        case '(' :
+        case ')' :
+        case '<' :
+        case '>' :
+          tokenend = position; break;
+        case '=' :
+          if(*position != '<' && *position != '>')
+          {
+            tokenend = position; 
+          }
+          break;
+        case '&' :
+          if(*position != '&')
+          {
+            tokenend = position;
+          }
+          break;
+        case '|' :
+          if(*position != '|')
+          {
+            tokenend = position;
+          }
+          break;
+        default  :
+          switch(*(position))
+          {
+            case '+' :
+            case '-' :
+            case '/' :
+            case '*' :
+            case '(' :
+            case ')' :
+            case '=' :
+            case '&' :
+            case '|' :
+              tokenend = position; break;
+            case '<' :
+            case '>' :
+              if(*(position+1) && *(position+1) != '=')
+              {
+                tokenend = position;
+              }
+              break;
+            default  :
+          }
+      }
+
+      if(tokenend)
+      {
+        break;
+      }
+    }
+
+    /* Have we reached the end of the string ? */
+    if(!tokenend)
+    {
+      tokenend = position;
+    }
+    
+    /* Create a new token */
+    new = newtoken(tokenstart, tokenend);
+
+    /* Insert on list */
+    if(current)
+    {
+      insertafter(current, new);
+    }
+    current = new;
+
+    if(!start)
+    {
+      start = current;
+    }
+
+    if(*tokenend)
+    {
+      tokenstart = tokenend+1;
+    }
+    else
+    {
+      break;
+    }
+  }
+    
+  return start;
+}
+
+ /*@@
+   @routine    ParenthesiseList
+   @date       Tue Sep 19 21:25:56 2000
+   @author     Tom Goodale
+   @desc 
+   Makes a first stab at putting in extra parentheses where necessary.
+   Doesn't do a good job of a+b+c/d/e, as it comes up with (a+b+(c/d))/e
+   rather than a+b+((c/d)/e).
+   Basically this is extremely primitive, and needs to be done properly with
+   a parse tree.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static pToken *ParenthesiseList(pToken *list)
+{
+  pToken *token;
+  pToken *current;
+  pToken *new;
+  char *openbracket = "(";
+  char *closebracket = ")";
+  int level;
+
+  for(token = list; token; token = token->next)
+  {
+    if(!strcmp(token->token, "*") ||
+       !strcmp(token->token, "/"))
+    {
+      /* OK it's a * or a /, so should attempt to
+       * put some extra brackets in */
+      if(token->last && token->next)
+      {
+        if(strcmp(token->last->token, ")"))
+        {
+          /* last token wasn't a bracket, so 
+           * put an opening bracket before it 
+           */
+          new = newtoken(openbracket,openbracket);
+          insertbefore(token->last, new);
+          if(!token->last->last)
+          {
+            list = new;
+          }
+          if(!strcmp(token->next->token, "("))
+          {
+            /* Next token is a bracket, so need to find
+             * matching end bracket.
+             */
+            level = 1;
+            
+            for(current=token->next->next; current && level > 0; current=current->next)
+            {
+              if(!strcmp(current->token, "("))
+              {
+                level++;
+              }
+              else if(!strcmp(current->token, ")"))
+              {
+                level--;
+              }
+            }
+            if(current)
+            {
+              current=current->last;
+            }
+          }
+          else
+          {
+            current = token;
+          }
+          if(current)
+          {
+            /* Now add the bracket. */
+            new = newtoken(closebracket,closebracket);
+            insertafter(current, new);
+          }
+        }
+      }
+    }
+  }
+  
+  return list;
+}
+
+ /*@@
+   @routine    RPParse
+   @date       Tue Sep 19 21:28:36 2000
+   @author     Tom Goodale
+   @desc 
+   Parses an toke list into Reverse Polish Notation (RPN).
+   This routine knows nothing about precedence, so parentheses 
+   must have been inserted in appropriate places beforehand.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+#define PUSH(stack, stacklength, value) do                        \
+{                                                                 \
+  if(strlen(stack)+strlen(value)+3 > (stacklength))               \
+  {                                                               \
+    stack = (char *)realloc(stack, strlen(stack)+strlen(value)+3);\
+  }                                                               \
+  sprintf(stack,"%s@%s",stack,value);                             \
+} while(0)
+
+
+static char *RPParse(pToken **current, char *stack, int *stacklength)
+{
+  char *retval;
+  pToken *this;
+  char *operator;
+
+  this = *current;
+
+  retval = stack;
+
+  operator = NULL;
+
+  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);
+      /* Now push the operator if there is one */
+      if(operator)
+      {
+        PUSH(retval, *stacklength, operator);
+        operator = NULL;
+      }
+      if(! this)
+      {
+        break;
+      }
+    }
+    else
+    {
+      /* Just a normal token - either an operator or a value */
+      if(!isoperator(this->token))
+      {
+        PUSH(retval, *stacklength, this->token);
+
+        /* Now push the operator, if there is one */
+        if(operator)
+        {
+          PUSH(retval, *stacklength, operator);
+          operator = NULL;
+        }
+      }
+      else
+      {
+        operator = this->token;
+      }
+    }
+  }
+
+  *current=this;
+
+  return retval;
+}
+
+
+ /*@@
+   @routine    Evaluate
+   @date       Tue Sep 19 21:35:34 2000
+   @author     Tom Goodale
+   @desc 
+   Evaluates val1 op val2 
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static double Evaluate(double val1, const char *operator, double val2)
+{
+  double 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);
+  }
+  else if(!strcmp(operator, "<="))
+  {
+    retval = (val1 <= val2);
+  }
+  else if(!strcmp(operator, ">"))
+  {
+    retval = (val1 > val2);
+  }
+  else if(!strcmp(operator, ">="))
+  {
+    retval = (val1 >= val2);
+  }
+  else
+  {
+    fprintf(stderr, "Unknown operation %s", operator);
+    retval = 0;
+  }
+
+  return retval;
+}
+  
+ /*@@
+   @routine    FreeTokens
+   @date       Tue Sep 19 21:39:07 2000
+   @author     Tom Goodale
+   @desc 
+   Frees a list of tokens.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+void FreeTokens(pToken *list)
+{
+  pToken *token;
+  pToken *next;
+
+  for(token = list; token; token = next)
+  {
+    next = token->next;
+    free(token->token);
+    free(token);
+  }
+}  
+
+
+ /*@@
+   @routine    isoperator
+   @date       Tue Sep 19 21:30:20 2000
+   @author     Tom Goodale
+   @desc 
+   Tests if a string is an operator or not.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+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
+  {
+    retval = 0;
+  }
+
+  return retval;
+}
+ 
+ /*@@
+   @routine    newtoken
+   @date       Tue Sep 19 21:30:42 2000
+   @author     Tom Goodale
+   @desc 
+   Creates a new token item.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static pToken *newtoken(const char *tokenstart, const char *tokenend)
+{
+  pToken *this;
+  const char *position;
+  char *newpos;
+
+  this = (pToken *)malloc(sizeof(pToken *));
+
+  if(this)
+  {
+    this->last = NULL;
+    this->next = NULL;
+
+    this->token = (char *)malloc(tokenend-tokenend+2);
+    if(this->token)
+    {
+      for(position=tokenstart, newpos=this->token; 
+          position <= tokenend; 
+          position++, newpos++)
+      {
+        *newpos = *position;
+      }
+      /* Just in case not already null terminated */
+      *(newpos+1) = 0;
+
+      /* Strip off any trailing spaces */
+      for(; newpos >= this->token && 
+            (*newpos == 0 || *newpos == ' ' || *newpos == '\t'); newpos--)
+      {
+        *newpos = 0;
+      }
+    }
+  }
+
+  return this;
+}
+
+ /*@@
+   @routine    insertbefore
+   @date       Tue Sep 19 21:33:39 2000
+   @author     Tom Goodale
+   @desc 
+   Inserts a token before another one in a list.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static void insertbefore(pToken *base, pToken *this)
+{
+  if(base && this)
+  {
+    this->next = base;
+    this->last = base->last;
+    base->last = this;
+
+    if(this->last)
+    {
+      this->last->next = this;
+    }
+  }
+}
+    
+ /*@@
+   @routine    insertafter
+   @date       Tue Sep 19 21:34:02 2000
+   @author     Tom Goodale
+   @desc 
+   Inserts a token after another one in a list.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static void insertafter(pToken *base, pToken *this)
+{
+  if(base && this)
+  {
+    this->last = base;
+    this->next = base->next;
+    base->next = this;
+    
+    if(this->next)
+    {
+      this->next->last = this;
+    }
+  }
+}
+  
+ /*@@
+   @routine    printtokens
+   @date       Tue Sep 19 21:34:24 2000
+   @author     Tom Goodale
+   @desc 
+   Debugging function to print out the tokens.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static void printtokens(pToken *start)
+{
+  pToken *token;
+
+  for(token = start; token; token = token->next)
+  {
+    printf("->%s", token->token);
+  }
+
+  printf("\n");
+}
+
+ /*@@
+   @routine    printstack
+   @date       Tue Sep 19 21:34:48 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.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static void printstack(char *stack)
+{
+  char *first;
+  char *token;
+
+  first = stack;
+
+  while((token = strtok(first,"@")))
+  {
+    first = NULL;
+    printf("Token is %s\n", token);
+  }
+}
+
+
+/********************************************************************
+ *********************     TEST FUNCTIONS   *************************
+ ********************************************************************/
+
+#ifdef TEST_HTTP_EVALUATE
+
+double evaluator(const char *token)
+{
+  double retval;
+
+  retval = strtod(token, NULL);
+
+  //  fprintf(stderr, "Evaluated '%s' to %f\n", token,retval);
+
+  return retval;
+}
+
+
+int main(int argc, char *argv[])
+{
+  char *buffer;
+
+  if(argc < 2)
+  {
+    printf("Usage: %s \"string\"\n", argv[0]);
+    exit(0);
+  }
+
+  buffer = HTTP_ExpressionParse(argv[1]);
+
+  printf("Value is %f\n", HTTP_ExpressionEvaluate(buffer, evaluator)); 
+  
+  free(buffer);
+
+  return 0;
+}
+  
+#endif /* TEST_HTTP_EVALUATE */    
diff --git a/src/http_Expression.h b/src/http_Expression.h
new file mode 100644
index 0000000..ccb3de3
--- /dev/null
+++ b/src/http_Expression.h
@@ -0,0 +1,27 @@
+ /*@@
+   @header    http_Expression.h
+   @date      Tue Sep 19 22:02:45 2000
+   @author    Tom Goodale
+   @desc 
+   Header for expression stuff.
+   @enddesc
+   @version $Header$
+ @@*/
+
+#ifndef __HTTP_EXPRESSION_H__
+#define __HTTP_EXPRESSION_H__ 1
+
+#ifdef __cplusplus
+extern "C" 
+{
+#endif
+
+char *HTTP_ExpressionParse(const char *expression);
+
+double HTTP_ExpressionEvaluate(char *buffer, double (*eval)(const char *));
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* __HTTP_EXPRESSION_H__ */
diff --git a/src/make.code.defn b/src/make.code.defn
index 65d2b04..b0eac4f 100644
--- a/src/make.code.defn
+++ b/src/make.code.defn
@@ -3,7 +3,7 @@
 
 # Source files in this directory
 
-MISC_SRC = Startup.c
+MISC_SRC = Startup.c Expression.c
 
 SERVER_SRC = Server.c Sockets.c http.c