xref: /haiku/src/kits/shared/ExpressionParser.cpp (revision 52c4471a3024d2eb81fe88e2c3982b9f8daa5e56) 
1 /*
2  * Copyright 2006-2012 Haiku, Inc. All Rights Reserved.
3  * Distributed under the terms of the MIT License.
4  *
5  * Authors:
6  *		Stephan Aßmus <superstippi@gmx.de>
7  *		John Scipione <jscipione@gmail.com>
8  *		Ingo Weinhold <bonefish@cs.tu-berlin.de>
9  */
10 
11 #include <ExpressionParser.h>
12 
13 #include <ctype.h>
14 #include <math.h>
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <strings.h>
18 
19 #include <m_apm.h>
20 
21 
22 static const int32 kMaxDecimalPlaces = 32;
23 
24 
25 enum {
26 	TOKEN_NONE					= 0,
27 	TOKEN_IDENTIFIER,
28 	TOKEN_CONSTANT,
29 
30 	TOKEN_END_OF_LINE			= '\n',
31 
32 	TOKEN_PLUS					= '+',
33 	TOKEN_MINUS					= '-',
34 
35 	TOKEN_STAR					= '*',
36 	TOKEN_SLASH					= '/',
37 	TOKEN_MODULO				= '%',
38 
39 	TOKEN_POWER					= '^',
40 	TOKEN_FACTORIAL				= '!',
41 
42 	TOKEN_OPENING_BRACKET		= '(',
43 	TOKEN_CLOSING_BRACKET		= ')',
44 
45 	TOKEN_AND					= '&',
46 	TOKEN_OR					= '|',
47 	TOKEN_NOT					= '~'
48 };
49 
50 
51 struct ExpressionParser::Token {
52 	Token()
53 		: string(""),
54 		  type(TOKEN_NONE),
55 		  value(0),
56 		  position(0)
57 	{
58 	}
59 
60 	Token(const Token& other)
61 		: string(other.string),
62 		  type(other.type),
63 		  value(other.value),
64 		  position(other.position)
65 	{
66 	}
67 
68 	Token(const char* string, int32 length, int32 position, int32 type)
69 		: string(string, length),
70 		  type(type),
71 		  value(0),
72 		  position(position)
73 	{
74 	}
75 
76 	Token& operator=(const Token& other)
77 	{
78 		string = other.string;
79 		type = other.type;
80 		value = other.value;
81 		position = other.position;
82 		return *this;
83 	}
84 
85 	BString		string;
86 	int32		type;
87 	MAPM		value;
88 
89 	int32		position;
90 };
91 
92 
93 class ExpressionParser::Tokenizer {
94  public:
95 	Tokenizer()
96 		: fString(""),
97 		  fCurrentChar(NULL),
98 		  fCurrentToken(),
99 		  fReuseToken(false),
100 		  fHexSupport(false),
101 		  fDecimalSeparator("."),
102 		  fGroupSeparator(",")
103 	{
104 	}
105 
106 	void SetSupportHexInput(bool enabled)
107 	{
108 		fHexSupport = enabled;
109 	}
110 
111 	void SetTo(const char* string)
112 	{
113 		fString = string;
114 		fCurrentChar = fString.String();
115 		fCurrentToken = Token();
116 		fReuseToken = false;
117 	}
118 
119 	const Token& NextToken()
120 	{
121 		if (fCurrentToken.type == TOKEN_END_OF_LINE)
122 			return fCurrentToken;
123 
124 		if (fReuseToken) {
125 			fReuseToken = false;
126 //printf("next token (recycled): '%s'\n", fCurrentToken.string.String());
127 			return fCurrentToken;
128 		}
129 
130 		while (*fCurrentChar != 0 && isspace(*fCurrentChar))
131 			fCurrentChar++;
132 
133 		int32 decimalLen = fDecimalSeparator.Length();
134 		int32 groupLen = fGroupSeparator.Length();
135 
136 		if (*fCurrentChar == 0 || decimalLen == 0)
137 			return fCurrentToken = Token("", 0, _CurrentPos(), TOKEN_END_OF_LINE);
138 
139 		if (*fCurrentChar == fDecimalSeparator[0] || isdigit(*fCurrentChar)) {
140 			if (fHexSupport && *fCurrentChar == '0' && fCurrentChar[1] == 'x')
141 				return _ParseHexNumber();
142 
143 			BString temp;
144 
145 			const char* begin = fCurrentChar;
146 
147 			// optional digits before the comma
148 			while (isdigit(*fCurrentChar) ||
149 				(groupLen > 0 && *fCurrentChar == fGroupSeparator[0])) {
150 				if (groupLen > 0 && *fCurrentChar == fGroupSeparator[0]) {
151 					int i = 0;
152 					while (i < groupLen && *fCurrentChar == fGroupSeparator[i]) {
153 						fCurrentChar++;
154 						i++;
155 					}
156 				} else {
157 					temp << *fCurrentChar;
158 					fCurrentChar++;
159 				}
160 			}
161 
162 			// optional post comma part
163 			// (required if there are no digits before the comma)
164 			if (*fCurrentChar == fDecimalSeparator[0]) {
165 				int i = 0;
166 				while (i < decimalLen && *fCurrentChar == fDecimalSeparator[i]) {
167 					fCurrentChar++;
168 					i++;
169 				}
170 
171 				temp << '.';
172 
173 				// optional post comma digits
174 				while (isdigit(*fCurrentChar)) {
175 					temp << *fCurrentChar;
176 					fCurrentChar++;
177 				}
178 			}
179 
180 			// optional exponent part
181 			if (*fCurrentChar == 'E') {
182 				temp << *fCurrentChar;
183 				fCurrentChar++;
184 
185 				// optional exponent sign
186 				if (*fCurrentChar == '+' || *fCurrentChar == '-') {
187 					temp << *fCurrentChar;
188 					fCurrentChar++;
189 				}
190 
191 				// required exponent digits
192 				if (!isdigit(*fCurrentChar)) {
193 					throw ParseException("missing exponent in constant",
194 						fCurrentChar - begin);
195 				}
196 
197 				while (isdigit(*fCurrentChar)) {
198 					temp << *fCurrentChar;
199 					fCurrentChar++;
200 				}
201 			}
202 
203 			int32 length = fCurrentChar - begin;
204 			BString test = temp;
205 			test << "&_";
206 			double value;
207 			char t[2];
208 			int32 matches = sscanf(test.String(), "%lf&%s", &value, t);
209 			if (matches != 2) {
210 				throw ParseException("error in constant",
211 					_CurrentPos() - length);
212 			}
213 
214 			fCurrentToken = Token(begin, length, _CurrentPos() - length,
215 				TOKEN_CONSTANT);
216 			fCurrentToken.value = temp.String();
217 		} else if (isalpha(*fCurrentChar) && *fCurrentChar != 'x') {
218 			const char* begin = fCurrentChar;
219 			while (*fCurrentChar != 0 && (isalpha(*fCurrentChar)
220 				|| isdigit(*fCurrentChar))) {
221 				fCurrentChar++;
222 			}
223 			int32 length = fCurrentChar - begin;
224 			fCurrentToken = Token(begin, length, _CurrentPos() - length,
225 				TOKEN_IDENTIFIER);
226 		} else if (strncmp(fCurrentChar, "π", 2) == 0) {
227 			fCurrentToken = Token(fCurrentChar, 2, _CurrentPos() - 1,
228 				TOKEN_IDENTIFIER);
229 			fCurrentChar += 2;
230 		} else {
231 			int32 type = TOKEN_NONE;
232 
233 			switch (*fCurrentChar) {
234 				case TOKEN_PLUS:
235 				case TOKEN_MINUS:
236 				case TOKEN_STAR:
237 				case TOKEN_SLASH:
238 				case TOKEN_MODULO:
239 				case TOKEN_POWER:
240 				case TOKEN_FACTORIAL:
241 				case TOKEN_OPENING_BRACKET:
242 				case TOKEN_CLOSING_BRACKET:
243 				case TOKEN_AND:
244 				case TOKEN_OR:
245 				case TOKEN_NOT:
246 				case TOKEN_END_OF_LINE:
247 					type = *fCurrentChar;
248 					break;
249 
250 				case '\\':
251 				case ':':
252 				type = TOKEN_SLASH;
253 					break;
254 
255 				case 'x':
256 					if (!fHexSupport) {
257 						type = TOKEN_STAR;
258 						break;
259 					}
260 					// fall through
261 
262 				default:
263 					throw ParseException("unexpected character", _CurrentPos());
264 			}
265 			fCurrentToken = Token(fCurrentChar, 1, _CurrentPos(), type);
266 			fCurrentChar++;
267 		}
268 
269 //printf("next token: '%s'\n", fCurrentToken.string.String());
270 		return fCurrentToken;
271 	}
272 
273 	void RewindToken()
274 	{
275 		fReuseToken = true;
276 	}
277 
278 	BString DecimalSeparator()
279 	{
280 		return fDecimalSeparator;
281 	}
282 
283 	BString GroupSeparator()
284 	{
285 		return fGroupSeparator;
286 	}
287 
288 	void SetSeparators(BString decimal, BString group)
289 	{
290 		fDecimalSeparator = decimal;
291 		fGroupSeparator = group;
292 	}
293 
294  private:
295 	static bool _IsHexDigit(char c)
296 	{
297 		return isdigit(c) || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F');
298 	}
299 
300 	Token& _ParseHexNumber()
301 	{
302 		const char* begin = fCurrentChar;
303 		fCurrentChar += 2;
304 			// skip "0x"
305 
306 		if (!_IsHexDigit(*fCurrentChar))
307 			throw ParseException("expected hex digit", _CurrentPos());
308 
309 		fCurrentChar++;
310 		while (_IsHexDigit(*fCurrentChar))
311 			fCurrentChar++;
312 
313 		int32 length = fCurrentChar - begin;
314 		fCurrentToken = Token(begin, length, _CurrentPos() - length,
315 			TOKEN_CONSTANT);
316 
317 		// MAPM has no conversion from long long, so we need to improvise.
318 		uint64 value = strtoll(fCurrentToken.string.String(), NULL, 0);
319 		if (value <= 0x7fffffff) {
320 			fCurrentToken.value = (long)value;
321 		} else {
322 			fCurrentToken.value = (int)(value >> 60);
323 			fCurrentToken.value *= 1 << 30;
324 			fCurrentToken.value += (int)((value >> 30) & 0x3fffffff);
325 			fCurrentToken.value *= 1 << 30;
326 			fCurrentToken.value += (int)(value& 0x3fffffff);
327 		}
328 
329 		return fCurrentToken;
330 	}
331 
332 	int32 _CurrentPos() const
333 	{
334 		return fCurrentChar - fString.String();
335 	}
336 
337 	BString		fString;
338 	const char*	fCurrentChar;
339 	Token		fCurrentToken;
340 	bool		fReuseToken;
341 	bool		fHexSupport;
342 	BString		fDecimalSeparator;
343 	BString		fGroupSeparator;
344 };
345 
346 
347 ExpressionParser::ExpressionParser()
348 	:	fTokenizer(new Tokenizer()),
349 		fDegreeMode(false)
350 {
351 }
352 
353 
354 ExpressionParser::~ExpressionParser()
355 {
356 	delete fTokenizer;
357 }
358 
359 
360 bool
361 ExpressionParser::DegreeMode()
362 {
363 	return fDegreeMode;
364 }
365 
366 
367 void
368 ExpressionParser::SetDegreeMode(bool degrees)
369 {
370 	fDegreeMode = degrees;
371 }
372 
373 
374 void
375 ExpressionParser::SetSupportHexInput(bool enabled)
376 {
377 	fTokenizer->SetSupportHexInput(enabled);
378 }
379 
380 
381 BString
382 ExpressionParser::Evaluate(const char* expressionString)
383 {
384 	fTokenizer->SetTo(expressionString);
385 
386 	MAPM value = _ParseBinary();
387 	Token token = fTokenizer->NextToken();
388 	if (token.type != TOKEN_END_OF_LINE)
389 		throw ParseException("parse error", token.position);
390 
391 	if (value == 0)
392 		return BString("0");
393 
394 	char* buffer = value.toFixPtStringExp(kMaxDecimalPlaces,
395 						'.', 0, 0);
396 
397 	if (buffer == NULL)
398 		throw ParseException("out of memory", 0);
399 
400 	// remove surplus zeros
401 	int32 lastChar = strlen(buffer) - 1;
402 	if (strchr(buffer, '.')) {
403 		while (buffer[lastChar] == '0')
404 			lastChar--;
405 
406 		if (buffer[lastChar] == '.')
407 			lastChar--;
408 	}
409 
410 	BString result(buffer, lastChar + 1);
411 	result.Replace(".", fTokenizer->DecimalSeparator(), 1);
412 	free(buffer);
413 	return result;
414 }
415 
416 
417 int64
418 ExpressionParser::EvaluateToInt64(const char* expressionString)
419 {
420 	fTokenizer->SetTo(expressionString);
421 
422 	MAPM value = _ParseBinary();
423 	Token token = fTokenizer->NextToken();
424 	if (token.type != TOKEN_END_OF_LINE)
425 		throw ParseException("parse error", token.position);
426 
427 	char buffer[128];
428 	value.toIntegerString(buffer);
429 
430 	return strtoll(buffer, NULL, 0);
431 }
432 
433 
434 double
435 ExpressionParser::EvaluateToDouble(const char* expressionString)
436 {
437 	fTokenizer->SetTo(expressionString);
438 
439 	MAPM value = _ParseBinary();
440 	Token token = fTokenizer->NextToken();
441 	if (token.type != TOKEN_END_OF_LINE)
442 		throw ParseException("parse error", token.position);
443 
444 	char buffer[1024];
445 	value.toString(buffer, sizeof(buffer) - 4);
446 
447 	return strtod(buffer, NULL);
448 }
449 
450 
451 MAPM
452 ExpressionParser::_ParseBinary()
453 {
454 	return _ParseSum();
455 	// binary operation appearantly not supported by m_apm library,
456 	// should not be too hard to implement though....
457 
458 //	double value = _ParseSum();
459 //
460 //	while (true) {
461 //		Token token = fTokenizer->NextToken();
462 //		switch (token.type) {
463 //			case TOKEN_AND:
464 //				value = (uint64)value & (uint64)_ParseSum();
465 //				break;
466 //			case TOKEN_OR:
467 //				value = (uint64)value | (uint64)_ParseSum();
468 //				break;
469 //
470 //			default:
471 //				fTokenizer->RewindToken();
472 //				return value;
473 //		}
474 //	}
475 }
476 
477 
478 MAPM
479 ExpressionParser::_ParseSum()
480 {
481 	// TODO: check isnan()...
482 	MAPM value = _ParseProduct();
483 
484 	while (true) {
485 		Token token = fTokenizer->NextToken();
486 		switch (token.type) {
487 			case TOKEN_PLUS:
488 				value = value + _ParseProduct();
489 				break;
490 			case TOKEN_MINUS:
491 				value = value - _ParseProduct();
492 				break;
493 
494 			default:
495 				fTokenizer->RewindToken();
496 				return _ParseFactorial(value);
497 		}
498 	}
499 }
500 
501 
502 MAPM
503 ExpressionParser::_ParseProduct()
504 {
505 	// TODO: check isnan()...
506 	MAPM value = _ParsePower();
507 
508 	while (true) {
509 		Token token = fTokenizer->NextToken();
510 		switch (token.type) {
511 			case TOKEN_STAR:
512 				value = value * _ParsePower();
513 				break;
514 			case TOKEN_SLASH: {
515 				MAPM rhs = _ParsePower();
516 				if (rhs == MAPM(0))
517 					throw ParseException("division by zero", token.position);
518 				value = value / rhs;
519 				break;
520 			}
521 			case TOKEN_MODULO: {
522 				MAPM rhs = _ParsePower();
523 				if (rhs == MAPM(0))
524 					throw ParseException("modulo by zero", token.position);
525 				value = value % rhs;
526 				break;
527 			}
528 
529 			default:
530 				fTokenizer->RewindToken();
531 				return _ParseFactorial(value);
532 		}
533 	}
534 }
535 
536 
537 MAPM
538 ExpressionParser::_ParsePower()
539 {
540 	MAPM value = _ParseUnary();
541 
542 	while (true) {
543 		Token token = fTokenizer->NextToken();
544 		if (token.type != TOKEN_POWER) {
545 			fTokenizer->RewindToken();
546 			return _ParseFactorial(value);
547 		}
548 		value = value.pow(_ParseUnary());
549 	}
550 }
551 
552 
553 MAPM
554 ExpressionParser::_ParseUnary()
555 {
556 	Token token = fTokenizer->NextToken();
557 	if (token.type == TOKEN_END_OF_LINE)
558 		throw ParseException("unexpected end of expression", token.position);
559 
560 	switch (token.type) {
561 		case TOKEN_PLUS:
562 			return _ParseUnary();
563 		case TOKEN_MINUS:
564 			return -_ParseUnary();
565 // TODO: Implement !
566 //		case TOKEN_NOT:
567 //			return ~(uint64)_ParseUnary();
568 
569 		case TOKEN_IDENTIFIER:
570 			return _ParseFunction(token);
571 
572 		default:
573 			fTokenizer->RewindToken();
574 			return _ParseAtom();
575 	}
576 
577 	return MAPM(0);
578 }
579 
580 
581 struct Function {
582 	const char*	name;
583 	int			argumentCount;
584 	void*		function;
585 	MAPM		value;
586 };
587 
588 
589 void
590 ExpressionParser::_InitArguments(MAPM values[], int32 argumentCount)
591 {
592 	_EatToken(TOKEN_OPENING_BRACKET);
593 
594 	for (int32 i = 0; i < argumentCount; i++)
595 		values[i] = _ParseBinary();
596 
597 	_EatToken(TOKEN_CLOSING_BRACKET);
598 }
599 
600 
601 MAPM
602 ExpressionParser::_ParseFunction(const Token& token)
603 {
604 	if (token.string == "e")
605 		return _ParseFactorial(MAPM(MM_E));
606 	else if (token.string.ICompare("pi") == 0 || token.string == "π")
607 		return _ParseFactorial(MAPM(MM_PI));
608 
609 	// hard coded cases for different count of arguments
610 	// supports functions with 3 arguments at most
611 
612 	MAPM values[3];
613 
614 	if (strcasecmp("abs", token.string.String()) == 0) {
615 		_InitArguments(values, 1);
616 		return _ParseFactorial(values[0].abs());
617 	} else if (strcasecmp("acos", token.string.String()) == 0) {
618 		_InitArguments(values, 1);
619 		if (fDegreeMode)
620 			values[0] = values[0] * MM_PI / 180;
621 
622 		if (values[0] < -1 || values[0] > 1)
623 			throw ParseException("out of domain", token.position);
624 
625 		return _ParseFactorial(values[0].acos());
626 	} else if (strcasecmp("asin", token.string.String()) == 0) {
627 		_InitArguments(values, 1);
628 		if (fDegreeMode)
629 			values[0] = values[0] * MM_PI / 180;
630 
631 		if (values[0] < -1 || values[0] > 1)
632 			throw ParseException("out of domain", token.position);
633 
634 		return _ParseFactorial(values[0].asin());
635 	} else if (strcasecmp("atan", token.string.String()) == 0) {
636 		_InitArguments(values, 1);
637 		if (fDegreeMode)
638 			values[0] = values[0] * MM_PI / 180;
639 
640 		return _ParseFactorial(values[0].atan());
641 	} else if (strcasecmp("atan2", token.string.String()) == 0) {
642 		_InitArguments(values, 2);
643 
644 		if (fDegreeMode) {
645 			values[0] = values[0] * MM_PI / 180;
646 			values[1] = values[1] * MM_PI / 180;
647 		}
648 
649 		return _ParseFactorial(values[0].atan2(values[1]));
650 	} else if (strcasecmp("cbrt", token.string.String()) == 0) {
651 		_InitArguments(values, 1);
652 		return _ParseFactorial(values[0].cbrt());
653 	} else if (strcasecmp("ceil", token.string.String()) == 0) {
654 		_InitArguments(values, 1);
655 		return _ParseFactorial(values[0].ceil());
656 	} else if (strcasecmp("cos", token.string.String()) == 0) {
657 		_InitArguments(values, 1);
658 		if (fDegreeMode)
659 			values[0] = values[0] * MM_PI / 180;
660 
661 		return _ParseFactorial(values[0].cos());
662 	} else if (strcasecmp("cosh", token.string.String()) == 0) {
663 		_InitArguments(values, 1);
664 		// This function always uses radians
665 		return _ParseFactorial(values[0].cosh());
666 	} else if (strcasecmp("exp", token.string.String()) == 0) {
667 		_InitArguments(values, 1);
668 		return _ParseFactorial(values[0].exp());
669 	} else if (strcasecmp("floor", token.string.String()) == 0) {
670 		_InitArguments(values, 1);
671 		return _ParseFactorial(values[0].floor());
672 	} else if (strcasecmp("ln", token.string.String()) == 0) {
673 		_InitArguments(values, 1);
674 		if (values[0] <= 0)
675 			throw ParseException("out of domain", token.position);
676 
677 		return _ParseFactorial(values[0].log());
678 	} else if (strcasecmp("log", token.string.String()) == 0) {
679 		_InitArguments(values, 1);
680 		if (values[0] <= 0)
681 			throw ParseException("out of domain", token.position);
682 
683 		return _ParseFactorial(values[0].log10());
684 	} else if (strcasecmp("pow", token.string.String()) == 0) {
685 		_InitArguments(values, 2);
686 		return _ParseFactorial(values[0].pow(values[1]));
687 	} else if (strcasecmp("sin", token.string.String()) == 0) {
688 		_InitArguments(values, 1);
689 		if (fDegreeMode)
690 			values[0] = values[0] * MM_PI / 180;
691 
692 		return _ParseFactorial(values[0].sin());
693 	} else if (strcasecmp("sinh", token.string.String()) == 0) {
694 		_InitArguments(values, 1);
695 		// This function always uses radians
696 		return _ParseFactorial(values[0].sinh());
697 	} else if (strcasecmp("sqrt", token.string.String()) == 0) {
698 		_InitArguments(values, 1);
699 		if (values[0] < 0)
700 			throw ParseException("out of domain", token.position);
701 
702 		return _ParseFactorial(values[0].sqrt());
703 	} else if (strcasecmp("tan", token.string.String()) == 0) {
704 		_InitArguments(values, 1);
705 		if (fDegreeMode)
706 			values[0] = values[0] * MM_PI / 180;
707 
708 		MAPM divided_by_half_pi = values[0] / MM_HALF_PI;
709 		if (divided_by_half_pi.is_integer() && divided_by_half_pi.is_odd())
710 			throw ParseException("out of domain", token.position);
711 
712 		return _ParseFactorial(values[0].tan());
713 	} else if (strcasecmp("tanh", token.string.String()) == 0) {
714 		_InitArguments(values, 1);
715 		// This function always uses radians
716 		return _ParseFactorial(values[0].tanh());
717 	}
718 
719 	throw ParseException("unknown identifier", token.position);
720 }
721 
722 
723 MAPM
724 ExpressionParser::_ParseAtom()
725 {
726 	Token token = fTokenizer->NextToken();
727 	if (token.type == TOKEN_END_OF_LINE)
728 		throw ParseException("unexpected end of expression", token.position);
729 
730 	if (token.type == TOKEN_CONSTANT)
731 		return _ParseFactorial(token.value);
732 
733 	fTokenizer->RewindToken();
734 
735 	_EatToken(TOKEN_OPENING_BRACKET);
736 
737 	MAPM value = _ParseBinary();
738 
739 	_EatToken(TOKEN_CLOSING_BRACKET);
740 
741 	return _ParseFactorial(value);
742 }
743 
744 
745 MAPM
746 ExpressionParser::_ParseFactorial(MAPM value)
747 {
748 	if (fTokenizer->NextToken().type == TOKEN_FACTORIAL) {
749 		fTokenizer->RewindToken();
750 		_EatToken(TOKEN_FACTORIAL);
751 		if (value < 1000)
752 			return value.factorial();
753 		else {
754 			// Use Stirling's approximation (9 term expansion)
755 			// http://en.wikipedia.org/wiki/Stirling%27s_approximation
756 			// http://www.wolframalpha.com/input/?i=stirling%27s+series
757 			// all constants must fit in a signed long for MAPM
758 			// (LONG_MAX = 2147483647)
759 			return value.pow(value) / value.exp()
760 				* (MAPM(2) * MAPM(MM_PI) * value).sqrt()
761 				* (MAPM(1) + (MAPM(1) / (MAPM(12) * value))
762 					+ (MAPM(1) / (MAPM(288) * value.pow(2)))
763 					- (MAPM(139) / (MAPM(51840) * value.pow(3)))
764 					- (MAPM(571) / (MAPM(2488320) * value.pow(4)))
765 					+ (MAPM(163879) / (MAPM(209018880) * value.pow(5)))
766 						// 2147483647 * 35 + 84869155 = 75246796800
767 					+ (MAPM(5246819) / ((MAPM(2147483647) * MAPM(35)
768 						+ MAPM(84869155)) * value.pow(6)))
769 						// 2147483647 * 420 + 1018429860 = 902961561600
770 					- (MAPM(534703531) / ((MAPM(2147483647) * MAPM(420)
771 						+ MAPM(1018429860)) * value.pow(7)))
772 						// 2147483647 * 2 + 188163965 = 4483131259
773 						// 2147483647 * 40366 + 985018798 = 86686309913600
774 					- ((MAPM(2147483647) * MAPM(2) + MAPM(188163965))
775 						/ ((MAPM(2147483647) * MAPM(40366) + MAPM(985018798))
776 							* value.pow(8)))
777 						// 2147483647 * 201287 + 1380758682 = 432261921612371
778 						// 2147483647 * 239771232 + 1145740896
779 						// = 514904800886784000
780 					+ ((MAPM(2147483647) * MAPM(201287) + MAPM(1380758682))
781 						/ ((MAPM(2147483647) * MAPM(239771232)
782 								+ MAPM(1145740896))
783 							* value.pow(9))));
784 		}
785 	}
786 
787 	fTokenizer->RewindToken();
788 	return value;
789 }
790 
791 
792 void
793 ExpressionParser::_EatToken(int32 type)
794 {
795 	Token token = fTokenizer->NextToken();
796 	if (token.type != type) {
797 		BString expected;
798 		switch (type) {
799 			case TOKEN_IDENTIFIER:
800 				expected = "an identifier";
801 				break;
802 
803 			case TOKEN_CONSTANT:
804 				expected = "a constant";
805 				break;
806 
807 			case TOKEN_PLUS:
808 			case TOKEN_MINUS:
809 			case TOKEN_STAR:
810 			case TOKEN_MODULO:
811 			case TOKEN_POWER:
812 			case TOKEN_FACTORIAL:
813 			case TOKEN_OPENING_BRACKET:
814 			case TOKEN_CLOSING_BRACKET:
815 			case TOKEN_AND:
816 			case TOKEN_OR:
817 			case TOKEN_NOT:
818 				expected << "'" << (char)type << "'";
819 				break;
820 
821 			case TOKEN_SLASH:
822 				expected = "'/', '\\', or ':'";
823 				break;
824 
825 			case TOKEN_END_OF_LINE:
826 				expected = "'\\n'";
827 				break;
828 		}
829 		BString temp;
830 		temp << "Expected " << expected.String() << " got '" << token.string << "'";
831 		throw ParseException(temp.String(), token.position);
832 	}
833 }
834 
835 
836 status_t
837 ExpressionParser::SetSeparators(BString decimal, BString group)
838 {
839 	if (decimal == group)
840 		return B_ERROR;
841 
842 	fTokenizer->SetSeparators(decimal, group);
843 
844 	return B_OK;
845 }
846