aboutsummaryrefslogtreecommitdiff
path: root/src/formula.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--src/formula.h399
1 files changed, 399 insertions, 0 deletions
diff --git a/src/formula.h b/src/formula.h
new file mode 100644
index 0000000..3809508
--- /dev/null
+++ b/src/formula.h
@@ -0,0 +1,399 @@
1#ifndef FORMULA_H
2#define FORMULA_H
3
4#include <stdint.h>
5
6#include <math.h>
7//#include "sbuffer.h"
8
9#include "bu/stack.h"
10#include "bu/exceptionbase.h"
11#include "bu/hash.h"
12#include "bu/fstring.h"
13
14subExceptionDecl( ParseException );
15
16namespace Bu
17{
18 /**
19 * Implements a very simple formula parser that allows use of variables and
20 * custom functions. This is based on a simple calculator-type parser that
21 * executes as it processes, accounting for operator precedence and
22 * grouping.
23 *
24 * prec = precision, a type to use for all math (except binary ops)
25 * bin = binary type, a type to hard cast all data to for binary ops
26 */
27 template<typename prec, typename bin=uint32_t>
28 class Formula
29 {
30 public:
31 Formula()
32 {
33 }
34
35 virtual ~Formula()
36 {
37 }
38
39 prec run( const char *sFormula )
40 {
41 for(;;)
42 {
43 uint8_t tNum = nextToken( &sFormula );
44 if( tNum == symEOS )
45 break;
46 else if( tNum == symSubtract )
47 {
48 tNum = nextToken( &sFormula );
49 if( tNum != symNumber )
50 throw ParseException(
51 "Unary minus must be followed by a number, "
52 "variable, function, or parenthesis.");
53 sValue.top() = -sValue.top();
54 }
55 else if( tNum == symNot )
56 {
57 tNum = nextToken( &sFormula );
58 if( tNum != symNumber )
59 throw ParseException(
60 "Unary, binary not must be followed by a number, "
61 "variable, function, or parenthesis.");
62 sValue.top() = static_cast<prec>(
63 ~static_cast<bin>(sValue.top())
64 );
65 }
66 else if( tNum == symOpenParen )
67 {
68 sOper.push( tNum );
69 continue;
70 }
71
72 oppart: uint8_t tOpr = nextToken( &sFormula );
73 if( tOpr == symEOS )
74 {
75 //printf("EOS ");
76 reduce();
77 return sValue.top();
78 break;
79 }
80 if( !sOper.isEmpty() && getPrec( sOper.top() ) > getPrec( tOpr ) )
81 {
82 reduce();
83 }
84 if( tOpr != symCloseParen )
85 {
86 sOper.push( tOpr );
87 }
88 else
89 {
90 reduce( true );
91 goto oppart;
92 }
93 }
94 return sValue.top();
95 }
96
97
98 typedef Hash<Bu::FString, prec> varHash;
99 varHash hVars;
100
101 typedef struct Func
102 {
103 prec operator()( prec x )
104 {
105 return 0;
106 }
107 } Func;
108
109 typedef Hash<Bu::FString, Func> funcHash;
110 funcHash hFunc;
111/*
112 typedef struct FuncSin : Func
113 {
114 prec operator()( prec x )
115 {
116 return sin( x );
117 }
118 } FuncSin;
119 */
120
121 private:
122 enum
123 {
124 symEOS,
125 symAdd,
126 symSubtract,
127 symMultiply,
128 symDivide,
129 symOpenParen,
130 symCloseParen,
131 symNumber,
132 symVariable,
133 symExponent,
134 symModulus,
135
136 symAnd,
137 symOr,
138 symXor,
139 symNot
140 };
141
142 typedef uint8_t symType;
143
144 Bu::Stack<symType> sOper;
145 Bu::Stack<prec> sValue;
146
147 private:
148 symType getPrec( symType nOper )
149 {
150 switch( nOper )
151 {
152 case symNumber:
153 case symVariable:
154 case symOpenParen:
155 case symCloseParen:
156 return 0;
157
158 case symAdd:
159 case symSubtract:
160 return 1;
161
162 case symMultiply:
163 case symDivide:
164 case symModulus:
165 return 2;
166
167 case symAnd:
168 case symOr:
169 case symXor:
170 return 2;
171
172 case symExponent:
173 case symNot:
174 return 3;
175
176 default:
177 return 0;
178 }
179 }
180
181 symType nextToken( const char **sBuf )
182 {
183 for(;;)
184 {
185 char cbuf = **sBuf;
186 ++(*sBuf);
187 switch( cbuf )
188 {
189 case '+':
190 return symAdd;
191
192 case '-':
193 return symSubtract;
194
195 case '*':
196 return symMultiply;
197
198 case '/':
199 return symDivide;
200
201 case '^':
202 return symExponent;
203
204 case '%':
205 return symModulus;
206
207 case '(':
208 return symOpenParen;
209
210 case ')':
211 return symCloseParen;
212
213 case '|':
214 return symOr;
215
216 case '&':
217 return symAnd;
218
219 case '#':
220 return symXor;
221
222 case '~':
223 return symNot;
224
225 case ' ':
226 case '\t':
227 case '\n':
228 case '\r':
229 break;
230
231 case '\0':
232 return symEOS;
233
234 default:
235 if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') )
236 {
237 char num[50]={cbuf};
238 int nPos = 1;
239 bool bDot = false;
240
241 for(;;)
242 {
243 cbuf = **sBuf;
244 if( cbuf == '.' )
245 {
246 if( bDot == false )
247 bDot = true;
248 else
249 throw ParseException(
250 "Numbers cannot have more than one "
251 ". in them."
252 );
253 }
254 if( cbuf == '.' || (cbuf >= '0' && cbuf <= '9') )
255 {
256 num[nPos++] = cbuf;
257 }
258 else
259 {
260 num[nPos] = '\0';
261 sValue.push(
262 static_cast<prec>(
263 strtod( num, NULL )
264 )
265 );
266 return symNumber;
267 }
268 ++(*sBuf);
269 }
270 }
271 else if( (cbuf >= 'a' && cbuf <= 'z') ||
272 (cbuf >= 'A' && cbuf <= 'Z') ||
273 (cbuf == '_') )
274 {
275 char tok[50]={cbuf};
276 int nPos = 1;
277
278 for(;;)
279 {
280 cbuf = **sBuf;
281 if( (cbuf >= 'a' && cbuf <= 'z') ||
282 (cbuf >= 'A' && cbuf <= 'Z') ||
283 (cbuf >= '0' && cbuf <= '9') ||
284 cbuf == '_' || cbuf == '.' || cbuf == ':' )
285 {
286 tok[nPos++] = cbuf;
287 }
288 else
289 {
290 tok[nPos] = '\0';
291 //printf("Checking variable \"%s\"\n", tok );
292 try
293 {
294 sValue.push( hVars[tok] );
295 return symNumber;
296 }
297 catch( HashException &e )
298 {
299 throw ParseException(
300 "No variable named \"%s\" exists.",
301 tok
302 );
303 }
304 }
305 ++(*sBuf);
306 }
307 }
308 break;
309 }
310 }
311 }
312
313 void reduce( bool bCloseParen = false )
314 {
315 while( !sOper.isEmpty() )
316 {
317 uint8_t nOpr = sOper.top();
318 if( nOpr == symOpenParen )
319 {
320 //printf("Found ( stopping reduction.\n");
321 if( bCloseParen == true )
322 sOper.pop();
323 return;
324 }
325 sOper.pop();
326
327 prec dTop = sValue.top();
328 sValue.pop();
329
330 switch( nOpr )
331 {
332 case symAdd:
333 //printf("%f + %f = %f\n", sValue.top(), dTop, sValue.top()+dTop );
334 sValue.top() += dTop;
335 break;
336
337 case symSubtract:
338 //printf("%f - %f = %f\n", sValue.top(), dTop, sValue.top()-dTop );
339 sValue.top() -= dTop;
340 break;
341
342 case symMultiply:
343 //printf("%f * %f = %f\n", sValue.top(), dTop, sValue.top()*dTop );
344 sValue.top() *= dTop;
345 break;
346
347 case symDivide:
348 //printf("%f / %f = %f\n", sValue.top(), dTop, sValue.top()/dTop );
349 sValue.top() /= dTop;
350 break;
351
352 case symExponent:
353 //printf("%f ^ %f = %f\n", sValue.top(), dTop, pow(sValue.top(),dTop) );
354 sValue.top() = static_cast<prec>(
355 pow( sValue.top(), dTop )
356 );
357 break;
358
359 case symModulus:
360 //printf("%f %% %f = %f\n", sValue.top(), dTop, fmod(sValue.top(),dTop) );
361 sValue.top() = static_cast<prec>(
362 fmod( sValue.top(), dTop )
363 );
364 break;
365
366 case symOr:
367 sValue.top() = static_cast<prec>(
368 static_cast<bin>(sValue.top()) |
369 static_cast<bin>(dTop)
370 );
371 break;
372
373 case symAnd:
374 sValue.top() = static_cast<prec>(
375 static_cast<bin>(sValue.top()) &
376 static_cast<bin>(dTop)
377 );
378 break;
379
380 case symXor:
381 sValue.top() = static_cast<prec>(
382 static_cast<bin>(sValue.top()) ^
383 static_cast<bin>(dTop)
384 );
385 break;
386 }
387 }
388
389 if( bCloseParen == true )
390 {
391 throw ParseException(
392 "Close-paren found without matching open-paren."
393 );
394 }
395 }
396 };
397}
398
399#endif