From c208b397b798910df4ad129fb13d562b4450034e Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Mon, 19 Feb 2007 05:15:23 +0000 Subject: The formula system works just fine, just no functions yet, but I don't need them for quite a while. --- src/formula.cpp | 261 +++++++++++++++++++++++++++++++++++--------------- src/formula.h | 59 +++++++----- src/tests/formula.cpp | 2 +- 3 files changed, 221 insertions(+), 101 deletions(-) (limited to 'src') diff --git a/src/formula.cpp b/src/formula.cpp index 7cc1804..cf63cf3 100644 --- a/src/formula.cpp +++ b/src/formula.cpp @@ -4,99 +4,177 @@ subExceptionDef( ParseException ); Formula::Formula() { + hVars["pi"] = M_PI; + hVars["e"] = M_E; + + hFunc["sin"] = FuncSin(); } Formula::~Formula() { } -double Formula::run( const char *sFormula ) +double Formula::run( char *sFormula ) { - sBuf.write( sFormula, strlen( sFormula ) ); - sBuf.setPos( 0 ); - - nState = 0; for(;;) { - tLook = nextToken(); - if( tLook.nSym == symEOS ) + uint8_t tNum = nextToken( &sFormula ); + if( tNum == symEOS ) + break; + else if( tNum == symSubtract ) + { + tNum = nextToken( &sFormula ); + if( tNum != symNumber ) + throw ParseException("Unary minus must be followed by a number, " + "variable, function, or parenthesis."); + sValue.top() = -sValue.top(); + } + else if( tNum == symOpenParen ) + { + sOper.push( tNum ); + continue; + } + +oppart: uint8_t tOpr = nextToken( &sFormula ); + if( tOpr == symEOS ) + { + //printf("EOS "); + reduce(); + return sValue.top(); break; - state(); + } + if( !sOper.empty() && getPrec( sOper.top() ) > getPrec( tOpr ) ) + { + reduce(); + } + if( tOpr != symCloseParen ) + { + sOper.push( tOpr ); + } + else + { + reduce( true ); + goto oppart; + } } - printf("\n"); - return 0.0; + return sValue.top(); } -void Formula::state() +void Formula::reduce( bool bCloseParen ) { - switch( nState ) + while( !sOper.empty() ) { - case 0: // initial expr - switch( tLook.nSym ) - { - case symNumber: - push(); - nState = 1; - break; - } - break; + uint8_t nOpr = sOper.top(); + if( nOpr == symOpenParen ) + { + //printf("Found ( stopping reduction.\n"); + if( bCloseParen == true ) + sOper.pop(); + return; + } + sOper.pop(); - case 1: // binary operator - switch( tLook.nSym ) - { - case symAdd: - case symSubtract: - push(); - nState = 2; - break; - - case symMultiply: - case symDivide: - push(); - nState = 3; - break; - } - break; + double dTop = sValue.top(); + sValue.pop(); - case 2: // add/subtract - break; + switch( nOpr ) + { + case symAdd: + //printf("%f + %f = %f\n", sValue.top(), dTop, sValue.top()+dTop ); + sValue.top() += dTop; + break; + + case symSubtract: + //printf("%f - %f = %f\n", sValue.top(), dTop, sValue.top()-dTop ); + sValue.top() -= dTop; + break; + + case symMultiply: + //printf("%f * %f = %f\n", sValue.top(), dTop, sValue.top()*dTop ); + sValue.top() *= dTop; + break; + + case symDivide: + //printf("%f / %f = %f\n", sValue.top(), dTop, sValue.top()/dTop ); + sValue.top() /= dTop; + break; + + case symExponent: + //printf("%f ^ %f = %f\n", sValue.top(), dTop, pow(sValue.top(),dTop) ); + sValue.top() = pow( sValue.top(), dTop ); + break; + + case symModulus: + //printf("%f %% %f = %f\n", sValue.top(), dTop, fmod(sValue.top(),dTop) ); + sValue.top() = fmod( sValue.top(), dTop ); + break; + } + } + + if( bCloseParen == true ) + { + throw ParseException("Close-paren found without matching open-paren."); } } -void Formula::push() +uint8_t Formula::getPrec( uint8_t nOper ) { - printToken( tLook ); - sToken.push( tLook ); + switch( nOper ) + { + case symNumber: + case symVariable: + case symOpenParen: + case symCloseParen: + return 0; + + case symAdd: + case symSubtract: + return 1; + + case symMultiply: + case symDivide: + case symModulus: + return 2; + + case symExponent: + return 3; + + default: + return 0; + } } -Formula::Token Formula::nextToken() +uint8_t Formula::nextToken( char **sBuf ) { - char cbuf; for(;;) { - if( sBuf.isEOS() ) - return Token( symEOS ); - - sBuf.read( &cbuf, 1 ); + char cbuf = **sBuf; + ++(*sBuf); switch( cbuf ) { case '+': - return Token( symAdd ); + return symAdd; case '-': - return Token( symSubtract ); + return symSubtract; case '*': - return Token( symMultiply ); + return symMultiply; case '/': - return Token( symDivide ); + return symDivide; + + case '^': + return symExponent; + + case '%': + return symModulus; case '(': - return Token( symOpenParen ); + return symOpenParen; case ')': - return Token( symCloseParen ); + return symCloseParen; case ' ': case '\t': @@ -104,16 +182,19 @@ Formula::Token Formula::nextToken() case '\r': break; + case '\0': + return symEOS; + default: if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') ) { - char num[50]; - int nPos = 0; + char num[50]={cbuf}; + int nPos = 1; bool bDot = false; for(;;) { - num[nPos++] = cbuf; + cbuf = **sBuf; if( cbuf == '.' ) { if( bDot == false ) @@ -124,14 +205,54 @@ Formula::Token Formula::nextToken() ". in them." ); } - sBuf.read( &cbuf, 1 ); - if( (cbuf != '.' && (cbuf < '0' || cbuf > '9')) || - sBuf.isEOS() ) + if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') ) + { + num[nPos++] = cbuf; + } + else { - if( !sBuf.isEOS() ) sBuf.seek( -1 ); num[nPos] = '\0'; - return Token( symNumber, strtod( num, NULL ) ); + sValue.push( strtod( num, NULL ) ); + return symNumber; } + ++(*sBuf); + } + } + else if( (cbuf >= 'a' && cbuf <= 'z') || + (cbuf >= 'A' && cbuf <= 'Z') || + (cbuf == '_') ) + { + char tok[50]={cbuf}; + int nPos = 1; + + for(;;) + { + cbuf = **sBuf; + if( (cbuf >= 'a' && cbuf <= 'z') || + (cbuf >= 'A' && cbuf <= 'Z') || + (cbuf >= '0' && cbuf <= '9') || + cbuf == '_' || cbuf == '.' || cbuf == ':' ) + { + tok[nPos++] = cbuf; + } + else + { + tok[nPos] = '\0'; + //printf("Checking variable \"%s\"\n", tok ); + try + { + sValue.push( hVars[tok] ); + return symNumber; + } + catch( HashException &e ) + { + throw ParseException( + "No variable named \"%s\" exists.", + tok + ); + } + } + ++(*sBuf); } } break; @@ -139,19 +260,3 @@ Formula::Token Formula::nextToken() } } -void Formula::printToken( Token &tok ) -{ - switch( tok.nSym ) - { - case symEOS: printf("[EOS] "); break; - case symAdd: printf("+ "); break; - case symSubtract: printf("- "); break; - case symMultiply: printf("* "); break; - case symDivide: printf("/ "); break; - case symOpenParen: printf("( "); break; - case symCloseParen: printf(") "); break; - case symNumber: printf("%f ", tok.val.num ); break; - default: printf("??? "); break; - } -} - diff --git a/src/formula.h b/src/formula.h index 1eccd36..939eb09 100644 --- a/src/formula.h +++ b/src/formula.h @@ -3,15 +3,19 @@ #include +#include #include #include "sbuffer.h" #include "exceptionbase.h" +#include "hash.h" subExceptionDecl( ParseException ); /** - * + * Implements a very simple formula parser that allows use of variables and + * custom functions. This is based on a simple calculator-type parser that + * executes as it processes, accounting for operator precedence and grouping. */ class Formula { @@ -19,7 +23,29 @@ public: Formula(); virtual ~Formula(); - double run( const char *sFormula ); + double run( char *sFormula ); + + typedef Hash varHash; + varHash hVars; + + typedef struct Func + { + double operator()( double x ) + { + return 0.0; + } + } Func; + + typedef Hash funcHash; + funcHash hFunc; + + typedef struct FuncSin : Func + { + double operator()( double x ) + { + return sin( x ); + } + } FuncSin; private: enum @@ -32,31 +58,20 @@ private: symOpenParen, symCloseParen, symNumber, - symVariable + symVariable, + symExponent, + symModulus }; - typedef struct Token - { - Token() {} - Token( uint8_t nSym ) : nSym( nSym ) { } - Token( uint8_t nSym, double dNum ) : nSym( nSym ) { val.num = dNum; } - uint8_t nSym; - union - { - double num; - } val; - } Token; + typedef uint8_t symType; - std::stack sToken; - Token tLook; - int nState; - SBuffer sBuf; + std::stack sOper; + std::stack sValue; private: - void push(); - void state(); - Token nextToken(); - void printToken( Token &tok ); + symType getPrec( symType nOper ); + symType nextToken( char **sBuf ); + void reduce( bool bCloseParen = false ); }; #endif diff --git a/src/tests/formula.cpp b/src/tests/formula.cpp index 599a264..976b039 100644 --- a/src/tests/formula.cpp +++ b/src/tests/formula.cpp @@ -6,7 +6,7 @@ int main( int argc, char *argv[] ) Formula f; double dOut = f.run( argv[1] ); - printf("Final: %f\n", dOut ); + printf("%s = %f\n", argv[1], dOut ); return 0; } -- cgit v1.2.3