From c208b397b798910df4ad129fb13d562b4450034e Mon Sep 17 00:00:00 2001
From: Mike Buland <eichlan@xagasoft.com>
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(-)
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 <stdint.h>
+#include <math.h>
#include <stack>
#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<std::string, double> varHash;
+ varHash hVars;
+
+ typedef struct Func
+ {
+ double operator()( double x )
+ {
+ return 0.0;
+ }
+ } Func;
+
+ typedef Hash<std::string, Func> 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<Token> sToken;
- Token tLook;
- int nState;
- SBuffer sBuf;
+ std::stack<symType> sOper;
+ std::stack<double> 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