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 source file with no external dependencies, weighing just over 20 KiB (just over 10 KiB when JAR’d).

Primary Features:

• Basic math operators, with inferred precedence (^ * × · / ÷ % + -).
• Explicit precedence with parenthesis.
• Implicit multiplication of bracketed subexpressions.
• Correct right-associativity of exponentials (power operator).
• Direct support for hexadecimal numbers prefixed by 0x.
• Constants and variables.
• Extensible operators.
• Extensible functions.
• Tiny 20 KiB footprint.

Thanks to Carlos Gómez of Asturias, Spain, for his time, thoughts and input in the area of unary operators and operator associativity which proved invaluable to implementing these features and verifying their correct operation.

How It Works

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

Broadly speaking, 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 current location to the end of the current expression. If we detect a bracketed sub-expression we also recurse to evaluate it. Otherwise, we perform the current operation and make the newly discovered operator current. If the now current operation does not have greater precedence than the pending operation, or we reach the end of the current expression, we return the left-value. When we return from the top recursion level we are done.

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).

/**
 * Evaluate the next operand of an expression.
 * @param beg       Inclusive begin offset for subexpression.
 * @param end       Inclusive end offset for subexpression.
 * @param pnd       Pending operator (operator previous to this subexpression).
 * @param lft       Left-value with which to initialize this subexpression.
 * @param cur       Current operator (the operator for this subexpression).
 */
private double _evaluate(int beg, int end, double lft, Operator pnd, Operator cur) 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 <left-val> <op> <right-val>. Depending on the precedence of the following operator, this sub-expression is either evaluated arriving at a new left-value, or pushed to one side (via recursion) to be actioned once the following sub-expression is done. Thus “1 + 2 × 3” becomes “2 × 3” (=6), followed by “1 + 6”.

Operator Precedence

Generally, if the current operator is of lower precedence than the next operator, we recurse to evaluate the right value before applying the current operator to the current left value.

if(opPrecedence(cur,LEFT_SIDE)<opPrecedence(nxt,RIGHT_SIDE)) {                                  // correct even for last (non-operator) character, since non-operators have the artificial "precedence" zero
    rgt=_evaluate((ofs+1),end,rgt,cur,nxt);                                                     // from after operator to end of current subexpression
    ofs=offset;                                                                                 // modify offset to after subexpression
    nxt=(ofs<=end ? getOperator(expression.charAt(ofs)) : OPERAND);                             // modify next operator
    }

If parenthesis are used, we also recurse to evaluate the entire bracketed sub-expression:

else if(ch0=='(') {
    rgt=_evaluate(beg+1,end);
    ofs=skipWhitespace(expression,offset+1,end);                                                // skip past ')' and any following whitespace
    nxt=(ofs<=end ? getOperator(expression.charAt(ofs)) : OPERAND);                             // modify next operator
    }

Operator Associativity and Unary Operators

One interesting complication with evaluating precedence is that by convention multiple consecutive power operators bind in a right-associative manner such that x^y^z is evaluated as x^(y^z) not (x^y)^z. This problem is solved by assigning operators two precedence values, one for when the operator is on the left of an operand and the other for when the operator is on the right of an operand. When evaluating their precedence they can have a different value depending on whether they are on the left or right of the intervening operand. So the power operator has a precedence of 80 for the left and 81 for the right.

static private final Operator       OPR_PWR =new Operator('^',80,81,NO_SIDE   ,false,DefaultImpl.INSTANCE); // power

Handling of unary operators is also challenging for two reasons; first they have a missing operand, and second they must be evaluated independent of precedence on one side (the side with no operand), and consider precedence on the other. These problems are resolved by making unary operators “glued” to their operand when seen from the opposite side, or the side which has no operand. Thus the negation in 2^-x^y has maximum precedence when considering 2^-x because ^-x" is nonsense, but when considering -x^y the negation has its normal precedence, lower than power.

private int opPrecedence(Operator opr, int sid) {
    if     (opr==null)                              { return Integer.MIN_VALUE;                                    } // not an operator
    else if(opr.bindTo==NO_SIDE || opr.bindTo!=sid) { return (sid==LEFT_SIDE ? opr.precedenceL : opr.precedenceR); } // operator is binary or is unary and bound to the operand on the other side
    else                                            { return Integer.MAX_VALUE;                                    } // operator is unary and associates with the operand on this side
    }

Finally, when a blank operand is detected we specifically allow it if the current operator is left-binding (e.g. 2! × 2) or the next operator is right-binding (e.g. 2^-2). When the current operator is left-binding we will always proceed to evaluate it because of the special unary Integer.MAX_VALUE precedence, while when the next operator is right-binding there must be no operand immediately left of it and we will always recurse, again because of the special unary Integer.MAX_VALUE precedence.

if(beg==ofs && (cur.unary==LEFT_SIDE || nxt.unary==RIGHT_SIDE)) {
    rgt=Double.NaN;                                                                             // left-binding unary operator; right value will not be used and should be blank
    }

Default set of operators, showing precedence:

static private final Operator       OPR_EQU =new Operator('=',99,99,RIGHT_SIDE,true ,DefaultImpl.INSTANCE); // simple assignment, used as the final operation, must be maximum precedence
static private final Operator       OPR_PWR =new Operator('^',80,81,NO_SIDE   ,false,DefaultImpl.INSTANCE); // power
static private final Operator       OPR_NEG =new Operator('±',60,60,RIGHT_SIDE,true ,DefaultImpl.INSTANCE); // unary negation
static private final Operator       OPR_MLT1=new Operator('*',40                    ,DefaultImpl.INSTANCE); // multiply (classical)
static private final Operator       OPR_MLT2=new Operator('×',40                    ,DefaultImpl.INSTANCE); // multiply (because it's a Unicode world out there)
static private final Operator       OPR_MLT3=new Operator('·',40                    ,DefaultImpl.INSTANCE); // multiply (because it's a Unicode world out there)
static private final Operator       OPR_BKT =new Operator('(',40                    ,DefaultImpl.INSTANCE); // multiply (implicit due to brackets, e.g "(a)(b)")
static private final Operator       OPR_DIV1=new Operator('/',40                    ,DefaultImpl.INSTANCE); // divide (classical computing)
static private final Operator       OPR_DIV2=new Operator('÷',40                    ,DefaultImpl.INSTANCE); // divide (because it's a Unicode world out there)
static private final Operator       OPR_MOD =new Operator('%',40                    ,DefaultImpl.INSTANCE); // remainder
static private final Operator       OPR_ADD =new Operator('+',20                    ,DefaultImpl.INSTANCE); // add/unary-positive
static private final Operator       OPR_SUB =new Operator('-',20                    ,DefaultImpl.INSTANCE); // subtract/unary-negative

Operator Evaluation

After working out what operation we need to do next we simply do it, assigning the result to the current left-value which is our running total. Then we loop around for the next one.

lft=operator(exp,beg,end,lft,cur,rgt);

...

private double operator(String exp, int beg, int end, double lft, Operator opr, double rgt) {
    try { return opr.handler.evaluateOperator(lft,opr.symbol,rgt); }
    catch(ArithmeticException thr) {
        throw exception(exp,beg,"Mathematical expression \""+exp+"\" failed to evaluate",thr);
        }
    catch(UnsupportedOperationException thr) {
        int tmp=beg;
        while(tmp>0 && getOperator(exp.charAt(tmp))==null) { tmp--; }                           // set up for offset of the offending operator
        throw exception(exp,tmp,"Operator \""+opr.symbol+"\" not handled by math engine (Programmer error: The list of operators is inconsistent within the engine)");
        }
    }

...

static class DefaultImpl
extends Object
implements OperatorHandler, FunctionHandler
{
public double evaluateOperator(double lft, char opr, double rgt) {
    switch(opr) {
        case '=' : return rgt;                                                                  // simple assignment, used as the final operation, must be maximum precedence
        case '^' : return Math.pow(lft,rgt);                                                    // power
        case '±' : return -rgt;                                                                 // unary negation
        case '*' : return lft*rgt;                                                              // multiply (classical)
        case '×' : return lft*rgt;                                                              // multiply (because it's a Unicode world out there)
        case '·' : return lft*rgt;                                                              // multiply (because it's a Unicode world out there)
        case '(' : return lft*rgt;                                                              // multiply (implicit due to brackets, e.g "(a)(b)")
        case '/' : return lft/rgt;                                                              // divide (classical computing)
        case '÷' : return lft/rgt;                                                              // divide (because it's a Unicode world out there)
        case '%' : return lft%rgt;                                                              // remainder
        case '+' : return lft+rgt;                                                              // add/unary-positive
        case '-' : return lft-rgt;                                                              // subtract/unary-negative
        default  : throw new UnsupportedOperationException("MathEval internal operator setup is incorrect - internal operator \""+opr+"\" not handled");
        }
    }
...
}

Extensibility

The evaluator’s abilities can be extended by registering handlers for operators and functions.

The design concept for handlers is that any given handler is coded for multiple operators or functions, and that it is registered for each of the operators or functions you wish to use. An important thing to observe is that the implementation methods are passed the operator or function they are to handle - a pure OO design would not do this. However, this design allows some flexibility in coding handlers which a pure-OO design would prohibit. Note that this allowance for handlers performing multiple functions in no way requires it. If Java had lightweight first-class functions, they would have been my first choice for supplying a handler implementation.

The design I chose for implementing the default operators and functions represents a compromise between pure-OO and reducing the number of classes required. This consideration was important to me because I wanted keep the footprint of the solution at around 20 KiB. The benefit of this choice, which I think outweighs the negatives, is that instead of requiring forty classes (twelve for operators and twenty-eight for functions), I have one class to handle all of the default operators and functions.

However, my implementation has two minor undesirable aspects. First the need to specify the identifying element twice - the characters for the default operators appear once when the operators are created and again within the evaluateOperator function; likewise the function names at registration and in evaluateFunction(). The second undesirable outcome of this compromise is seen within the function handling. In order to mitigate the cost of the string comparisons, it does a switch on the first character. This is pure overhead since the evaluator has already performed a map lookup on the name to find the registered function handler. If every handler did just one function, that lookup would entirely suffice to locate the code which must be done for the function.

Adding an operator extension that does factorial using the unary left-binding operator '!' looks like this:

mathEval.setOperator(new MathEval.Operator('!',90,90,MathEval.LEFT_SIDE,new MathEvalHandler()));

...

public class MathEvalHandler
extends Object
implements MathEval.OperatorHandler
{

public double evaluateOperator(double lft, char opr, double rgt) throws ArithmeticException {
    switch(opr) {
        case '!': {
            if(lft<0) {
                throw new ArithmeticException("Cannot calculate factorial of negative number");
                }
            else if(lft<2) {
                return 1;
                }
            else {
                int tot=2;
                for(int xa=3; xa<=lft; xa++) { tot*=xa; }
                return tot;
                }
            } // returns
        default: {
            throw new ArithmeticException("Operator '"+opr+"' not supported in custom operator implementation");
            } // throws
        }
    }
}

Get The Source

The source compiles to Java 5, but modifications to target earlier JVM versions are trivial (some functions will have to be sacrificed and generics need to be removed). Adding functions supported by later JVM’s is also trivial.

Download MathEval.java.