Math Expression Evaluator
This math expression evaluator was born out of a need to have a small-footprint and efficient solution which could evaluate arbitrary expressions reasonably efficiently without requiring pre-compilation. I needed something which would do basic math with variables, expressions like: “Top+2”, “Bottom-2” and “(Right+1-Left)/2”.
Research on the Internet turned up a number of fairly good solutions, all of which revolved around creating parse trees (which makes sense). The problem was - they were all rather bulky, and I couldn’t afford to add 100K to my applet size just for math. So I started wondering about a linear recursive solution to the problem. The end result is an acceptably performing single class with no external dependencies, weighing in under 10 KiB.
How It Works
Primary Features
- Basic math operators, with inferred precedence: + - * / % ^
- Explicit precedence with parenthesis.
- Constants and variables
- Common math functions
- Direct support for expressions with hexadecimal numbers (prefixed by 0x).
Here’s a simple example which calculates the middle column of the subsection of a text display (biased left).
MathEval math=new MathEval();
math.setVariable("Top", 5);
math.setVariable("Left", 20);
math.setVariable("Bottom",15);
math.setVariable("Right", 60);
System.out.println("Middle: "+math.evaluate("floor((Right+1-Left)/2)")); // 20
The heart of this class is the private recursive function _evaluate() (I use the lead underscore exclusively for private methods which share the same name as a public method because they provide its actual implementation; this is almost always a recursive method).
/**
* @param exp Entire expression.
* @param beg Inclusive begin offset for sub-expression.
* @param end Inclusive end offset for sub-expression.
* @param pop Pending operator (operator previous to this sub-expression).
* @param tot Running total to initialize this sub-expression.
* @param cop Current operator (the operator for this sub-expression).
*/
private double _evaluate(String exp, int beg, int end, char pop, double tot, char cop) throws NumberFormatException, ArithmeticException {
This is an immediate divergence from more traditional ways of solving this problem; instead of generating a parse tree and subsequently evaluating it, we recursively parse and evaluate subsections of the original input string. Essentially, the expression is broken up into multiple simple expressions of
Implicit Precedence:
if(cop!='=' && opPrecedence(nop)>opPrecedence(cop)) { // correct even for last (non-opr) character, since non-oprs have "precedence" zero
val=_evaluate(exp,(ofs+1),end,cop,val,nop); // from after operator to end of current sub-expression
ofs=offset; // modify offset
nop=exp.charAt(ofs<=end ? ofs : end); // modify next operator
}
Explicit Precedence (Parenthesis):
if(ch0=='(') {
val=_evaluate(exp,(beg+1),(beg+txt.length()-2),'=',0,'=');
}
Accumulation of Total
After working out what operation we need to do next, we simply do that on our total, and loop around for the next one.
switch(cop) {
case '=' : { tot=val; } break;
case '+' : { tot=(tot+val); } break;
case '-' : { tot=(tot-val); } break;
case '*' : { tot=(tot*val); } break;
case '/' : { tot=(tot/val); } break;
case '%' : { tot=(tot%val); } break;
case '^' : { tot=Math.pow(tot,val); } break;
default : {
int tmp=beg;
while(tmp>0 && !isOperator(exp.charAt(tmp))) { tmp--; }
throw exception(exp,tmp,"Operator '"+cop+"' not handled by math engine (Programmer error: The list of operators is inconsistent with the engine)");
}
}
So, essentially, we read our string looking for operators. When we find one, if its precedence is greater than the currently pending operation, we recurse on a sub-expression from the previous value to end of the current sub- expression. If it’s of equal or lessor precedence, we perform the pending operation and make the newly discovered one pending. When we reach the end of the expression, we return, and when we return from the top recursion level we are done. Throw in a special recursion for any parenthesized sub-expression (including that of a function parameter) and we are done.
Where To Go From Here
Several improvements could be made to this class:
- It could have an optional precompiled tree;
- It could have an interface for resolving external variables and functions;
- It really needs support for multiple-parameter functions (harder than you would think).
Get The Source
The source compiles to Java 5, but modifications to target earlier JVM versions are trivial (although some functions will have to be sacrified). Adding functions supported by later JVM's is also trivial.
Download MathEval.java (Total downloads: 0)