diff options
author | goodale <goodale@17b73243-c579-4c4c-a9d2-2d5706c11dac> | 2001-11-06 11:17:21 +0000 |
---|---|---|
committer | goodale <goodale@17b73243-c579-4c4c-a9d2-2d5706c11dac> | 2001-11-06 11:17:21 +0000 |
commit | 5fac77c5f9720a01487184df09f5d944b539808a (patch) | |
tree | 0108fec88eef09f6ab032e1490678aa2fcaeae43 /src/util | |
parent | 08dfcb0ca55b252b80364a38623f8787616b1c58 (diff) |
Moved verification out of evalaution and into parsing stage to speed up
evaluation.
Tom
git-svn-id: http://svn.cactuscode.org/flesh/trunk@2454 17b73243-c579-4c4c-a9d2-2d5706c11dac
Diffstat (limited to 'src/util')
-rw-r--r-- | src/util/Expression.c | 202 |
1 files changed, 147 insertions, 55 deletions
diff --git a/src/util/Expression.c b/src/util/Expression.c index 0233a4fe..b79b4706 100644 --- a/src/util/Expression.c +++ b/src/util/Expression.c @@ -46,7 +46,8 @@ typedef struct PToken ********************************************************************/ static pToken *Tokenise(const char *expression); -int RPParse(pToken **current,uExpressionInternals *buffer); +static int RPParse(pToken **current,uExpressionInternals *buffer); +static int VerifyParsedExpression(const uExpressionInternals *buffer); static int EvaluateBinary(uExpressionValue *retval, const uExpressionValue *val1, uExpressionOpcode opcode, @@ -185,9 +186,23 @@ uExpression Util_ExpressionParse(const char *expression) temp = list; /* Convert the list into a string in RPN order */ - RPParse(&temp, buffer); + if(!RPParse(&temp, buffer)) + { + /* Check if it is a valid expression */ + if(!VerifyParsedExpression(buffer)) + { + Util_ExpressionFree(buffer); + buffer = NULL; + } + } + else + { + Util_ExpressionFree(buffer); + buffer = NULL; + } FreeTokens(list); + } return buffer; @@ -238,8 +253,9 @@ uExpression Util_ExpressionParse(const char *expression) @returntype int @returndesc - +ve - success but there were this number of remaining operation on the stack. 0 - success + The below used to be returned, but now expression is pre-verified. + +ve - success but there were this number of remaining operation on the stack. -ve - the number of remaining items on the expression stack when an error was encountered @endreturndesc @@ -314,55 +330,33 @@ int Util_ExpressionEvaluate(const uExpression buffer, 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; - } + EvaluateBinary(&(stack[stackpointer-2]), + &(stack[stackpointer-2]), + buffer->tokens[position].token.opcode, + &(stack[stackpointer-1])); + stackpointer--; 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) { - 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: - ; - } + 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; - } } if(varvals) @@ -370,15 +364,13 @@ int Util_ExpressionEvaluate(const uExpression buffer, free(varvals); } - if(retcode) - { - retcode = -1-stackpointer; - } - else - { - *retval=stack[stackpointer-1]; - retcode = stackpointer-1; - } + *retval=stack[0]; + + /* stackpointer should be 1 at this point if VerifyExpression + * was called on the expression. + */ + + retcode = stackpointer-1; return retcode; } @@ -627,7 +619,7 @@ static pToken *Tokenise(const char *expression) (stack)->tokens[(stack)->ntokens-1].token.varnum = value; break; \ } while(0) -int RPParse(pToken **current, uExpressionInternals *buffer) +static int RPParse(pToken **current, uExpressionInternals *buffer) { int retcode; pToken *this; @@ -653,8 +645,9 @@ int RPParse(pToken **current, uExpressionInternals *buffer) /* This is a sub-group, so parse recursively */ this = this->next; retcode = RPParse(&this, buffer); - if(! this) + if(retcode || ! this || strcmp(this->token,")")) { + retcode = -1; break; } } @@ -723,6 +716,98 @@ int RPParse(pToken **current, uExpressionInternals *buffer) return retcode; } + /*@@ + @routine VerifyParsedExpression + @date Tue Nov 6 10:53:12 2001 + @author Tom Goodale + @desc + Verifies that an expression would complete successfully. + @enddesc + @calls + @calledby + @history + + @endhistory + @var buffer + @vdesc An expression buffer + @vtype const uExpressionInternals * + @vio in + @vcomment + + @endvar + + @returntype int + @returndesc + 1 - success + 0 - invalid expression + @endreturndesc +@@*/ +static int VerifyParsedExpression(const uExpressionInternals *buffer) +{ + int retcode; + int stackpointer; + int position; + + stackpointer = 0; + + retcode = 0; + + for(position = 0; position < buffer->ntokens; position++) + { + if(buffer->tokens[position].type == val) + { + stackpointer++; + } + else + { + /* Evaluate operation, clear operands from stack and add the result to the stack. */ + switch(buffer->tokens[position].type) + { + case binary: + if(stackpointer > 1) + { + stackpointer--; + } + else + { + retcode = -1; + } + break; + case unary: + if(stackpointer == 0) + { + retcode = -1; + } + break; + default: + ; + } + } + if(stackpointer < 0 || stackpointer > MAX_STACK_SIZE || retcode ) + { + retcode = -1; + break; + } + } + + if(! retcode) + { + if(stackpointer == 1) + { + retcode = 1; + } + else + { + retcode = 0; + } + } + else + { + retcode = 0; + } + + return retcode; +} /*@@ @routine EvaluateBinary @@ -1470,19 +1555,26 @@ int main(int argc, char *argv[]) buffer = Util_ExpressionParse(argv[1]); - Util_ExpressionEvaluate(buffer, &value,evaluator,NULL); - - if(value.type==ival) + if(buffer) { - printf("Value is %d\n", value.value.ival); + 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); } else { - printf("Value is %f\n", value.value.rval); + printf("Invalid expression : '%s'\n", argv[1]); } - Util_ExpressionFree(buffer); - return 0; } |