Added precedence for operations - can now cope with nasty expressions.

Tom


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

1 files changed, 111 insertions, 107 deletions

diff --git a/src/Expression.c b/src/Expression.c
index 28f5251..2f8e56a 100644
--- a/src/Expression.c
+++ b/src/Expression.c
@@ -8,7 +8,7 @@
    @version $Header$
  @@*/
 
-#ifndef TEST_HTPP_EXPRESSION
+#ifndef TEST_HTTP_EVALUATE
 #include "cctk.h"
 #endif
 
@@ -38,11 +38,11 @@ typedef struct PToken
  ********************************************************************/
 
 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 int cmpprecendence(const char *op1, const char *op2);
 
 static pToken *newtoken(const char *tokenstart, const char *tokenend);
 
@@ -62,6 +62,7 @@ static void printtokens(pToken *start);
 
 #define INITIAL_BUFFER_LENGTH 1000
 #define MAX_STACK_SIZE 256
+#define MAX_OPS 100
 
 /********************************************************************
  *********************     External Routines   **********************
@@ -98,9 +99,6 @@ char *HTTP_ExpressionParse(const char *expression)
     /* 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
@@ -312,101 +310,11 @@ static pToken *Tokenise(const char *expression)
 }
 
  /*@@
-   @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   
@@ -430,7 +338,11 @@ static char *RPParse(pToken **current, char *stack, int *stacklength)
   char *retval;
   pToken *this;
   char *operator;
+  char *opstack[MAX_OPS];
+  int numops;
+  int precedence;
 
+  numops = 0;
   this = *current;
 
   retval = stack;
@@ -444,29 +356,47 @@ static char *RPParse(pToken **current, char *stack, int *stacklength)
       /* 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 if(!isoperator(this->token))
+    {
+      PUSH(retval, *stacklength, this->token);
+    }
     else
     {
-      /* Just a normal token - either an operator or a value */
-      if(!isoperator(this->token))
+      /* It's an operator */
+      if(operator)
       {
-        PUSH(retval, *stacklength, this->token);
+        /* We already have an operator */
+        precedence = cmpprecendence(operator, this->token);
 
-        /* Now push the operator, if there is one */
-        if(operator)
+        if(precedence > 0)
+        {
+          /* Higher precedence than previous one so store previous one */
+          numops++;
+          opstack[numops-1] = operator;
+          operator = this->token;
+        }
+        else
         {
+          /* Lower or equal precedence */
           PUSH(retval, *stacklength, operator);
-          operator = NULL;
+          operator = this->token;
+          while(numops > 0)
+          {
+            if(cmpprecendence(opstack[numops-1], operator) <=0)
+            {
+              numops--;
+              PUSH(retval, *stacklength, opstack[numops]);
+            }
+            else
+            {
+              break;
+            }
+          }
         }
       }
       else
@@ -476,6 +406,16 @@ static char *RPParse(pToken **current, char *stack, int *stacklength)
     }
   }
 
+  if(operator)
+  {
+    PUSH(retval, *stacklength, operator);
+    while(numops > 0)
+    {
+      numops--;
+      PUSH(retval, *stacklength, opstack[numops]);
+    }
+  }
+
   *current=this;
 
   return retval;
@@ -620,6 +560,70 @@ static int isoperator(const char *token)
 
   return retval;
 }
+
+ /*@@
+   @routine    cmpprecendence
+   @date       Wed Sep 20 09:05:59 2000
+   @author     Tom Goodale
+   @desc 
+   Compare the precedence of two operators.
+   @enddesc 
+   @calls     
+   @calledby   
+   @history 
+ 
+   @endhistory 
+
+@@*/
+static int cmpprecendence(const char *op1, const char *op2)
+{
+  int retval;
+  const char *op;
+  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)
+  {
+    if(!strcmp(op, "=") ||
+       !strcmp(op, "<") ||
+       !strcmp(op, "<=") ||
+       !strcmp(op, ">") ||
+       !strcmp(op, ">="))
+    {
+      *prec = 1;
+    }
+    else if(!strcmp(op, "&&") ||
+       !strcmp(op, "||"))
+    {
+      *prec = 2;
+    }
+    else if(!strcmp(op, "+") ||
+            !strcmp(op, "-"))
+    {
+      *prec = 3;
+    }
+    else if(!strcmp(op, "/") ||
+            !strcmp(op, "*"))
+    {
+      *prec = 4;
+    }
+    else
+    {
+      fprintf(stderr, "Unknown operator '%s'\n", op);
+      *prec = 0;
+    }
+  }
+
+  /* Now see which has the higher precedence */
+  retval = op2prec-op1prec;
+
+  return retval;
+}
  
  /*@@
    @routine    newtoken