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