summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2007-02-19 05:15:23 +0000
committerMike Buland <eichlan@xagasoft.com>2007-02-19 05:15:23 +0000
commitc208b397b798910df4ad129fb13d562b4450034e (patch)
treedbc04e831163022e09c7a001b887ba3d7f82f7bd
parent89eeeff54f0b3ce30be5b046fc3899fdeb5ebb40 (diff)
downloadlibbu++-c208b397b798910df4ad129fb13d562b4450034e.tar.gz
libbu++-c208b397b798910df4ad129fb13d562b4450034e.tar.bz2
libbu++-c208b397b798910df4ad129fb13d562b4450034e.tar.xz
libbu++-c208b397b798910df4ad129fb13d562b4450034e.zip
The formula system works just fine, just no functions yet, but I don't need them
for quite a while.
Diffstat
-rw-r--r--src/formula.cpp261
-rw-r--r--src/formula.h59
-rw-r--r--src/tests/formula.cpp2
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 );
4 4
5Formula::Formula() 5Formula::Formula()
6{ 6{
7 hVars["pi"] = M_PI;
8 hVars["e"] = M_E;
9
10 hFunc["sin"] = FuncSin();
7} 11}
8 12
9Formula::~Formula() 13Formula::~Formula()
10{ 14{
11} 15}
12 16
13double Formula::run( const char *sFormula ) 17double Formula::run( char *sFormula )
14{ 18{
15 sBuf.write( sFormula, strlen( sFormula ) );
16 sBuf.setPos( 0 );
17
18 nState = 0;
19 for(;;) 19 for(;;)
20 { 20 {
21 tLook = nextToken(); 21 uint8_t tNum = nextToken( &sFormula );
22 if( tLook.nSym == symEOS ) 22 if( tNum == symEOS )
23 break;
24 else if( tNum == symSubtract )
25 {
26 tNum = nextToken( &sFormula );
27 if( tNum != symNumber )
28 throw ParseException("Unary minus must be followed by a number, "
29 "variable, function, or parenthesis.");
30 sValue.top() = -sValue.top();
31 }
32 else if( tNum == symOpenParen )
33 {
34 sOper.push( tNum );
35 continue;
36 }
37
38oppart: uint8_t tOpr = nextToken( &sFormula );
39 if( tOpr == symEOS )
40 {
41 //printf("EOS ");
42 reduce();
43 return sValue.top();
23 break; 44 break;
24 state(); 45 }
46 if( !sOper.empty() && getPrec( sOper.top() ) > getPrec( tOpr ) )
47 {
48 reduce();
49 }
50 if( tOpr != symCloseParen )
51 {
52 sOper.push( tOpr );
53 }
54 else
55 {
56 reduce( true );
57 goto oppart;
58 }
25 } 59 }
26 printf("\n"); 60 return sValue.top();
27 return 0.0;
28} 61}
29 62
30void Formula::state() 63void Formula::reduce( bool bCloseParen )
31{ 64{
32 switch( nState ) 65 while( !sOper.empty() )
33 { 66 {
34 case 0: // initial expr 67 uint8_t nOpr = sOper.top();
35 switch( tLook.nSym ) 68 if( nOpr == symOpenParen )
36 { 69 {
37 case symNumber: 70 //printf("Found ( stopping reduction.\n");
38 push(); 71 if( bCloseParen == true )
39 nState = 1; 72 sOper.pop();
40 break; 73 return;
41 } 74 }
42 break; 75 sOper.pop();
43 76
44 case 1: // binary operator 77 double dTop = sValue.top();
45 switch( tLook.nSym ) 78 sValue.pop();
46 {
47 case symAdd:
48 case symSubtract:
49 push();
50 nState = 2;
51 break;
52
53 case symMultiply:
54 case symDivide:
55 push();
56 nState = 3;
57 break;
58 }
59 break;
60 79
61 case 2: // add/subtract 80 switch( nOpr )
62 break; 81 {
82 case symAdd:
83 //printf("%f + %f = %f\n", sValue.top(), dTop, sValue.top()+dTop );
84 sValue.top() += dTop;
85 break;
86
87 case symSubtract:
88 //printf("%f - %f = %f\n", sValue.top(), dTop, sValue.top()-dTop );
89 sValue.top() -= dTop;
90 break;
91
92 case symMultiply:
93 //printf("%f * %f = %f\n", sValue.top(), dTop, sValue.top()*dTop );
94 sValue.top() *= dTop;
95 break;
96
97 case symDivide:
98 //printf("%f / %f = %f\n", sValue.top(), dTop, sValue.top()/dTop );
99 sValue.top() /= dTop;
100 break;
101
102 case symExponent:
103 //printf("%f ^ %f = %f\n", sValue.top(), dTop, pow(sValue.top(),dTop) );
104 sValue.top() = pow( sValue.top(), dTop );
105 break;
106
107 case symModulus:
108 //printf("%f %% %f = %f\n", sValue.top(), dTop, fmod(sValue.top(),dTop) );
109 sValue.top() = fmod( sValue.top(), dTop );
110 break;
111 }
112 }
113
114 if( bCloseParen == true )
115 {
116 throw ParseException("Close-paren found without matching open-paren.");
63 } 117 }
64} 118}
65 119
66void Formula::push() 120uint8_t Formula::getPrec( uint8_t nOper )
67{ 121{
68 printToken( tLook ); 122 switch( nOper )
69 sToken.push( tLook ); 123 {
124 case symNumber:
125 case symVariable:
126 case symOpenParen:
127 case symCloseParen:
128 return 0;
129
130 case symAdd:
131 case symSubtract:
132 return 1;
133
134 case symMultiply:
135 case symDivide:
136 case symModulus:
137 return 2;
138
139 case symExponent:
140 return 3;
141
142 default:
143 return 0;
144 }
70} 145}
71 146
72Formula::Token Formula::nextToken() 147uint8_t Formula::nextToken( char **sBuf )
73{ 148{
74 char cbuf;
75 for(;;) 149 for(;;)
76 { 150 {
77 if( sBuf.isEOS() ) 151 char cbuf = **sBuf;
78 return Token( symEOS ); 152 ++(*sBuf);
79
80 sBuf.read( &cbuf, 1 );
81 switch( cbuf ) 153 switch( cbuf )
82 { 154 {
83 case '+': 155 case '+':
84 return Token( symAdd ); 156 return symAdd;
85 157
86 case '-': 158 case '-':
87 return Token( symSubtract ); 159 return symSubtract;
88 160
89 case '*': 161 case '*':
90 return Token( symMultiply ); 162 return symMultiply;
91 163
92 case '/': 164 case '/':
93 return Token( symDivide ); 165 return symDivide;
166
167 case '^':
168 return symExponent;
169
170 case '%':
171 return symModulus;
94 172
95 case '(': 173 case '(':
96 return Token( symOpenParen ); 174 return symOpenParen;
97 175
98 case ')': 176 case ')':
99 return Token( symCloseParen ); 177 return symCloseParen;
100 178
101 case ' ': 179 case ' ':
102 case '\t': 180 case '\t':
@@ -104,16 +182,19 @@ Formula::Token Formula::nextToken()
104 case '\r': 182 case '\r':
105 break; 183 break;
106 184
185 case '\0':
186 return symEOS;
187
107 default: 188 default:
108 if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') ) 189 if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') )
109 { 190 {
110 char num[50]; 191 char num[50]={cbuf};
111 int nPos = 0; 192 int nPos = 1;
112 bool bDot = false; 193 bool bDot = false;
113 194
114 for(;;) 195 for(;;)
115 { 196 {
116 num[nPos++] = cbuf; 197 cbuf = **sBuf;
117 if( cbuf == '.' ) 198 if( cbuf == '.' )
118 { 199 {
119 if( bDot == false ) 200 if( bDot == false )
@@ -124,14 +205,54 @@ Formula::Token Formula::nextToken()
124 ". in them." 205 ". in them."
125 ); 206 );
126 } 207 }
127 sBuf.read( &cbuf, 1 ); 208 if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') )
128 if( (cbuf != '.' && (cbuf < '0' || cbuf > '9')) || 209 {
129 sBuf.isEOS() ) 210 num[nPos++] = cbuf;
211 }
212 else
130 { 213 {
131 if( !sBuf.isEOS() ) sBuf.seek( -1 );
132 num[nPos] = '\0'; 214 num[nPos] = '\0';
133 return Token( symNumber, strtod( num, NULL ) ); 215 sValue.push( strtod( num, NULL ) );
216 return symNumber;
134 } 217 }
218 ++(*sBuf);
219 }
220 }
221 else if( (cbuf >= 'a' && cbuf <= 'z') ||
222 (cbuf >= 'A' && cbuf <= 'Z') ||
223 (cbuf == '_') )
224 {
225 char tok[50]={cbuf};
226 int nPos = 1;
227
228 for(;;)
229 {
230 cbuf = **sBuf;
231 if( (cbuf >= 'a' && cbuf <= 'z') ||
232 (cbuf >= 'A' && cbuf <= 'Z') ||
233 (cbuf >= '0' && cbuf <= '9') ||
234 cbuf == '_' || cbuf == '.' || cbuf == ':' )
235 {
236 tok[nPos++] = cbuf;
237 }
238 else
239 {
240 tok[nPos] = '\0';
241 //printf("Checking variable \"%s\"\n", tok );
242 try
243 {
244 sValue.push( hVars[tok] );
245 return symNumber;
246 }
247 catch( HashException &e )
248 {
249 throw ParseException(
250 "No variable named \"%s\" exists.",
251 tok
252 );
253 }
254 }
255 ++(*sBuf);
135 } 256 }
136 } 257 }
137 break; 258 break;
@@ -139,19 +260,3 @@ Formula::Token Formula::nextToken()
139 } 260 }
140} 261}
141 262
142void Formula::printToken( Token &tok )
143{
144 switch( tok.nSym )
145 {
146 case symEOS: printf("[EOS] "); break;
147 case symAdd: printf("+ "); break;
148 case symSubtract: printf("- "); break;
149 case symMultiply: printf("* "); break;
150 case symDivide: printf("/ "); break;
151 case symOpenParen: printf("( "); break;
152 case symCloseParen: printf(") "); break;
153 case symNumber: printf("%f ", tok.val.num ); break;
154 default: printf("??? "); break;
155 }
156}
157
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 @@
3 3
4#include <stdint.h> 4#include <stdint.h>
5 5
6#include <math.h>
6#include <stack> 7#include <stack>
7#include "sbuffer.h" 8#include "sbuffer.h"
8 9
9#include "exceptionbase.h" 10#include "exceptionbase.h"
11#include "hash.h"
10 12
11subExceptionDecl( ParseException ); 13subExceptionDecl( ParseException );
12 14
13/** 15/**
14 * 16 * Implements a very simple formula parser that allows use of variables and
17 * custom functions. This is based on a simple calculator-type parser that
18 * executes as it processes, accounting for operator precedence and grouping.
15 */ 19 */
16class Formula 20class Formula
17{ 21{
@@ -19,7 +23,29 @@ public:
19 Formula(); 23 Formula();
20 virtual ~Formula(); 24 virtual ~Formula();
21 25
22 double run( const char *sFormula ); 26 double run( char *sFormula );
27
28 typedef Hash<std::string, double> varHash;
29 varHash hVars;
30
31 typedef struct Func
32 {
33 double operator()( double x )
34 {
35 return 0.0;
36 }
37 } Func;
38
39 typedef Hash<std::string, Func> funcHash;
40 funcHash hFunc;
41
42 typedef struct FuncSin : Func
43 {
44 double operator()( double x )
45 {
46 return sin( x );
47 }
48 } FuncSin;
23 49
24private: 50private:
25 enum 51 enum
@@ -32,31 +58,20 @@ private:
32 symOpenParen, 58 symOpenParen,
33 symCloseParen, 59 symCloseParen,
34 symNumber, 60 symNumber,
35 symVariable 61 symVariable,
62 symExponent,
63 symModulus
36 }; 64 };
37 65
38 typedef struct Token 66 typedef uint8_t symType;
39 {
40 Token() {}
41 Token( uint8_t nSym ) : nSym( nSym ) { }
42 Token( uint8_t nSym, double dNum ) : nSym( nSym ) { val.num = dNum; }
43 uint8_t nSym;
44 union
45 {
46 double num;
47 } val;
48 } Token;
49 67
50 std::stack<Token> sToken; 68 std::stack<symType> sOper;
51 Token tLook; 69 std::stack<double> sValue;
52 int nState;
53 SBuffer sBuf;
54 70
55private: 71private:
56 void push(); 72 symType getPrec( symType nOper );
57 void state(); 73 symType nextToken( char **sBuf );
58 Token nextToken(); 74 void reduce( bool bCloseParen = false );
59 void printToken( Token &tok );
60}; 75};
61 76
62#endif 77#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[] )
6 6
7 Formula f; 7 Formula f;
8 double dOut = f.run( argv[1] ); 8 double dOut = f.run( argv[1] );
9 printf("Final: %f\n", dOut ); 9 printf("%s = %f\n", argv[1], dOut );
10 10
11 return 0; 11 return 0;
12} 12}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-26 17:35:17 +0000