// Created by Lawrence PC Dol.  Released into the public domain.
//
// Source is licensed for any use, provided this copyright notice is retained.
// No warranty for any purpose whatsoever is implied or expressed.  The author
// is not liable for any losses of any kind, direct or indirect, which result
// from the use of this software.
//
// UPDATE 2012-03-27: Correct problems caused by embedded whitespace in the expression

package <your-package-here>;

import java.math.*;
import java.util.*;

/**
 * Math Evaluator.  Provides the ability to evaluate a String math expression, with support for functions, variables and
 * standard math constants.
 * <p>
 * Predefined Constants:
 * <ul>
 *   <li>E              - The double value that is closer than any other to e, the base of the natural logarithms (2.718281828459045).
 *   <li>Euler          - Euler's Constant (0.577215664901533).
 *   <li>LN2            - Log of 2 base e (0.693147180559945).
 *   <li>LN10           - Log of 10 base e (2.302585092994046).
 *   <li>LOG2E          - Log of e base 2 (1.442695040888963).
 *   <li>LOG10E         - Log of e base 10 (0.434294481903252).
 *   <li>PHI            - The golden ratio (1.618033988749895).
 *   <li>PI             - The double value that is closer than any other to pi, the ratio of the circumference of a circle to its diameter (3.141592653589793).
 *   </ul>
 * <p>
 * Supported Functions (see java.Math for detail and parameters):
 * <ul>
 *   <li>abs
 *   <li>acos
 *   <li>asin
 *   <li>atan
 *   <li>cbrt
 *   <li>ceil
 *   <li>cos
 *   <li>cosh
 *   <li>exp
 *   <li>expm1
 *   <li>floor
 *   <li>getExponent
 *   <li>log
 *   <li>log10
 *   <li>log1p
 *   <li>nextUp
 *   <li>round
 *   <li>roundHE (maps to Math.rint)
 *   <li>signum
 *   <li>sin
 *   <li>sinh
 *   <li>sqrt
 *   <li>tan
 *   <li>tanh
 *   <li>toDegrees
 *   <li>toRadians
 *   <li>ulp
 *   </ul>
 * <p>
 * Threading Design : [x] Single Threaded  [ ] Threadsafe  [ ] Immutable  [ ] Isolated
 *
 * @author          Lawrence Dol
 * @since           Build 2008.0426.1016
 */

public class MathEval
extends Object
{

// *****************************************************************************
// INSTANCE PROPERTIES
// *****************************************************************************

private SortedMap<String,Double>        constants;                              // external constants
private SortedMap<String,Double>        variables;                              // external variables
private boolean                         relaxed;                                // allow variables to be undefined

private int                             offset;                                 // used when returning from a higher precedence sub-expression evaluation
private boolean                         isConstant;                             // constant expression flag

// *****************************************************************************
// INSTANCE CREATE/DELETE
// *****************************************************************************

/**
 * Create a math evaluator.
 */
public MathEval() {
    super();

    constants=new TreeMap<String,Double>(String.CASE_INSENSITIVE_ORDER);
    setConstant("E"     ,Math.E);
    setConstant("Euler" ,0.577215664901533D);
    setConstant("LN2"   ,0.693147180559945D);
    setConstant("LN10"  ,2.302585092994046D);
    setConstant("LOG2E" ,1.442695040888963D);
    setConstant("LOG10E",0.434294481903252D);
    setConstant("PHI"   ,1.618033988749895D);
    setConstant("PI"    ,Math.PI);

    variables=new TreeMap<String,Double>(String.CASE_INSENSITIVE_ORDER);
    }

// *****************************************************************************
// INSTANCE METHODS - ACCESSORS
// *****************************************************************************

/** Set a named constant (constant names are not case-sensitive).  Constants are like variables but are not cleared by clear(). Variables of the same name have precedence over constants. */
public double getConstant(String nam) {
    Double                              val=constants.get(nam);

    return (val==null ? 0 : val.doubleValue());
    }

/** Gets an unmodifiable iterable of the constants in this evaluator. */
public Iterable<Map.Entry<String,Double>> getConstants() {
    return Collections.unmodifiableMap(constants).entrySet();
    }

/** Set a named constant (constants names are not case-sensitive).  Constants are like variables but are not cleared by clear(). Variables of the same name have precedence over constants. */
public MathEval setConstant(String nam, double val) {
    return setConstant(nam,Double.valueOf(val));
    }

/** Set a named constant (constants names are not case-sensitive).  Constants are like variables but are not cleared by clear(). Variables of the same name have precedence over constants. */
public MathEval setConstant(String nam, Double val) {
    if(!Character.isLetter(nam.charAt(0))) { throw new IllegalArgumentException("Constant names must start with a letter"     ); }
    if(nam.indexOf('(')!=-1              ) { throw new IllegalArgumentException("Constant names may not contain a parenthesis"); }
    if(nam.indexOf(')')!=-1              ) { throw new IllegalArgumentException("Constant names may not contain a parenthesis"); }
    if(constants.get(nam)!=null          ) { throw new IllegalArgumentException("Constants may not be redefined"              ); }
    constants.put(nam,val);
    return this;
    }

/** Set a named variable (variables names are not case-sensitive). */
public double getVariable(String nam) {
    Double                              val=variables.get(nam);

    return (val==null ? 0 : val.doubleValue());
    }

/** Gets an unmodifiable iterable of the variables in this evaluator. */
public Iterable<Map.Entry<String,Double>> getVariables() {
    return Collections.unmodifiableMap(variables).entrySet();
    }

/** Set a named variable (variables names are not case-sensitive). */
public MathEval setVariable(String nam, double val) {
    return setVariable(nam,Double.valueOf(val));
    }

/** Set a named variable (variables names are not case-sensitive). If the value is null, the variable is removed. */
public MathEval setVariable(String nam, Double val) {
    if(!Character.isLetter(nam.charAt(0))) { throw new IllegalArgumentException("Variable must start with a letter"           ); }
    if(nam.indexOf('(')!=-1              ) { throw new IllegalArgumentException("Variable names may not contain a parenthesis"); }
    if(nam.indexOf(')')!=-1              ) { throw new IllegalArgumentException("Variable names may not contain a parenthesis"); }
    if(val==null) { variables.remove(nam);  }
    else          { variables.put(nam,val); }
    return this;
    }

/** Clear all variables (constants are not affected). */
public MathEval clear() {
    variables.clear();
    return this;
    }

/** Clear all variables prefixed by the supplied string followed by a dot, such that they match "Prefix.xxx". */
public MathEval clear(String pfx) {
    variables.subMap((pfx+"."),(pfx+"."+Character.MAX_VALUE)).clear();
    return this;
    }

/** Get whether a variable which is used in an expression is required to be explicitly set. If not explicitly set, the value 0.0 is assumed. */
public boolean getVariableRequired() {
    return relaxed;
    }

/** Set whether a variable which is used in an expression is required to be explicitly set. If not explicitly set, the value 0.0 is assumed. */
public MathEval setVariableRequired(boolean val) {
    relaxed=(!val);
    return this;
    }

// *****************************************************************************
// INSTANCE METHODS - PUBLIC API
// *****************************************************************************

/**
 * Evaluate this expression.
 */
public double evaluate(String exp) throws NumberFormatException, ArithmeticException {
    isConstant=true;
    return _evaluate(exp,0,(exp.length()-1),'=',0,'=');
    }

/**
 * Return whether the previous expression evaluated was constant (i.e. contained no variables).
 * This is useful when optimizing to store the result instead of repeatedly evaluating a constant expression like "2+2".
 */
public boolean previousExpressionConstant() throws NumberFormatException, ArithmeticException {
    return isConstant;
    }

// *****************************************************************************
// INSTANCE METHODS - PRIVATE IMPLEMENTATION
// *****************************************************************************

/**
 * @param exp       Entire expression.
 * @param beg       Inclusive begin offset for subexpression.
 * @param end       Inclusive end offset for subexpression.
 * @param pop       Pending operator (operator previous to this subexpression).
 * @param tot       Running total to initialize this subexpression.
 * @param cop       Current operator (the operator for this subexpression).
 */
private double _evaluate(String exp, int beg, int end, char pop, double tot, char cop) throws NumberFormatException, ArithmeticException {
    char                                nop=0;                                  // next operator
    int                                 ofs=beg;                                // current expression offset

    while(beg<=end && Character.isWhitespace(exp.charAt(beg))) { beg++; }
    if(beg>end) { throw exception(exp,beg,"Mathematical expression '"+exp+"' is blank or contains a blank sub-expression"); }

    OUTER:
    for(ofs=beg; ofs<=end; ofs++) {
        while(ofs<=end && Character.isWhitespace(exp.charAt(ofs))) { ofs++; }
        if(ofs<=end) {
            boolean bkt=false;
            for(beg=ofs; ofs<=end; ofs++) {
                nop=exp.charAt(ofs);
                if(nop=='(') {
                    int cls=skipTo(')',exp,(ofs+1),end,false,false);
                    if(cls>end) { throw exception(exp,ofs,"Mathematical expression '"+exp+"' contains an unclosed parenthesis"); }
                    bkt=true;
                    ofs=cls;
                    }
                else if(isOperator(nop) && (!isSign(nop) || ofs!=beg)) {        // break at operator, excluding lead sign character
                    break;
                    }
                }

            char   ch0=exp.charAt(beg);
            double val;

            if(ch0=='(') {
                int rgt=(ofs-1);
                while(rgt>beg && exp.charAt(rgt)!=')') { rgt--; }
                val=_evaluate(exp,(beg+1),(rgt-1),'=',0,'=');
                }
            else if(Character.isLetter(ch0)) {
                if(bkt) { val=function(exp,beg,(ofs-1)); }
                else    { val=variable(exp,beg,(ofs-1)); }
                }
            else {
                String txt;                                                     // Double and Long parse() functions only accept a string
                if(bkt) {                                                       // implied multiplication; e.g 2(x+3)
                    ofs=skipTo('(',exp,beg,end,false,false);
                    txt=exp.substring(beg,ofs);                                 // before decrementing ofs
                    ofs--;                                                      // back up to before '(' to compensate for outer loop ofs++
                    nop='*';
                    }
                else {
                    txt=exp.substring(beg,ofs).trim();
                    }
                try {
                    if(stringSW(txt,"0x")) { val=(double)Long.parseLong(txt.substring(2),16); }
                    else                   { val=Double.parseDouble(txt);                     }
                    }
                catch(NumberFormatException thr) { throw exception(exp,beg,"Mathematical expression '"+exp+"' contains the invalid value \""+txt+"\""); }
                }

            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 subexpression
                ofs=offset;                                                     // modify offset
                nop=exp.charAt(ofs<=end ? ofs : end);                           // modify nop
                }

            try {
                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)");
                        }
                    }
                }
            catch(ArithmeticException thr) { throw exception(exp,beg,"Mathematical expression '"+exp+"' failed to evaluate (Exception: "+thr.getMessage()+")"); }
            cop=nop;
            if(pop!='=' && opPrecedence(cop)<=opPrecedence(pop)) { break OUTER; }
            }
        if(ofs==end && isOperator(nop)) { throw exception(exp,ofs,"Mathematical expression '"+exp+"' ends with a blank sub-expression"); }
        }
    offset=ofs;
    return tot;
    }

private double function(String exp, int beg, int end) {
    int                                 nam=beg;

    while(beg<=end && exp.charAt(beg)!='(') { beg++; }
    while(beg<=end && exp.charAt(end)!=')') { end--; }

    // CONSTANT VALUE FUNCTIONS: THESE FUNCTIONS RETURN THE SAME VALUE GIVEN THE SAME PARAMETERS EACH TIME THEY ARE CALLED (Java 4+)
    if(isWordAt(exp,nam,"abs"         )) { return Math.abs        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"acos"        )) { return Math.acos       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"asin"        )) { return Math.asin       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"atan"        )) { return Math.atan       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"ceil"        )) { return Math.ceil       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"cos"         )) { return Math.cos        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"exp"         )) { return Math.exp        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"floor"       )) { return Math.floor      (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"log"         )) { return Math.log        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"round"       )) { return Math.round      (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"roundHE"     )) { return Math.rint       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); } // round half-even
    if(isWordAt(exp,nam,"sin"         )) { return Math.sin        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"sqrt"        )) { return Math.sqrt       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"tan"         )) { return Math.tan        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"toDegrees"   )) { return Math.toDegrees  (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"toRadians"   )) { return Math.toRadians  (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }

    // CONSTANT VALUE FUNCTIONS: THESE FUNCTIONS RETURN THE SAME VALUE GIVEN THE SAME PARAMETERS EACH TIME THEY ARE CALLED (Java 5+)
    if(isWordAt(exp,nam,"cbrt"        )) { return Math.cbrt       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"cosh"        )) { return Math.cosh       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"expm1"       )) { return Math.expm1      (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"log10"       )) { return Math.log10      (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"log1p"       )) { return Math.log1p      (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"signum"      )) { return Math.signum     (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"sinh"        )) { return Math.sinh       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"tanh"        )) { return Math.tanh       (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"ulp"         )) { return Math.ulp        (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }

    // CONSTANT VALUE FUNCTIONS: THESE FUNCTIONS RETURN THE SAME VALUE GIVEN THE SAME PARAMETERS EACH TIME THEY ARE CALLED (Java 6+)
    if(isWordAt(exp,nam,"getExponent" )) { return Math.getExponent(_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }
    if(isWordAt(exp,nam,"nextUp"      )) { return Math.nextUp     (_evaluate(exp,(beg+1),(end-1),'=',0,'=')); }

    isConstant=false;

    // INCONSTANT VALUE FUNCTIONS: THESE FUNCTIONS POTENTIALLY RETURN A DIFFERENT VALUE EVERY TIME THEY ARE CALLED, EVEN IF WITH THE SAME PARAMETERS
    if(isWordAt(exp,nam,"random"      )) { return Math.random     (                                        ); }

    throw exception(exp,beg,"Unrecognized function \""+exp.substring(nam,(end+1))+"\"");
    }

private double variable(String exp, int beg, int end) {
    while(beg<=end && Character.isWhitespace(exp.charAt(end))) { end--; }
    if(beg>end) { throw exception(exp,beg,"Mathematical expression '"+exp+"' is blank or contains a blank sub-expression"); }

    String                  nam=exp.substring(beg,(end+1));
    Double                  val;

    if     ((val=constants.get(nam))!=null) {                   return val.doubleValue(); }
    else if((val=variables.get(nam))!=null) { isConstant=false; return val.doubleValue(); }
    else if(relaxed                       ) { isConstant=false; return 0.0;               }

    throw exception(exp,beg,"Unrecognized variable or constant \""+exp.substring(beg,(end+1))+"\"");
    }

private boolean isSign(char chr) {
    return (chr=='-' || chr=='+');
    }

private boolean isOperator(char chr) {
    return (chr<128 && PRECEDENCE[chr]!=0);
    }

private int opPrecedence(char chr) {
    return (chr<128 ? PRECEDENCE[chr] : 0);
    }

private ArithmeticException exception(String exp, int ofs, String txt) {
    return new ArithmeticException(txt+" at offset "+ofs+" in expression \""+exp+"\"");
    }

// *****************************************************************************
// INSTANCE INNER CLASSES
// *****************************************************************************

// *****************************************************************************
// STATIC NESTED CLASSES
// *****************************************************************************

// *****************************************************************************
// STATIC PROPERTIES
// *****************************************************************************

static private final int[]              PRECEDENCE;
static {
    int[] prc=new int[127];
    prc['+']=1;
    prc['-']=1;
    prc['*']=2;
    prc['/']=2;
    prc['%']=2;
    prc['^']=3;
    PRECEDENCE=prc;
    }

// *****************************************************************************
// STATIC INIT & MAIN
// *****************************************************************************

// *****************************************************************************
// STATIC METHODS - UTILITY
// *****************************************************************************

static private boolean isWordAt(String str, int ofs, String wrd) {
    int                                 len=wrd.length();
    char                                aft=(len>=str.length() ? '\0' : str.charAt(ofs+len));

    return (str.regionMatches(true,ofs,wrd,0,len) && !Character.isLetter(aft) && !Character.isDigit(aft));
    }

static private boolean stringSW(String str, String val) {
    if(str==null || val==null) { return (str==val); }
    return str.regionMatches(true,0,val,0,val.length());
    }

static private int skipTo(char chr, String str, int beg, int end, boolean ignqut, boolean ignesc) {
    int                                 ofs=beg,lvl=1;
    boolean                             nst,qut,esc;                            // nesting, quoting, escaping
    char                                opn;

    if     (chr==')' ) { nst=true;  opn='('; qut=ignqut; esc=false;  }
    else if(chr==']' ) { nst=true;  opn='['; qut=ignqut; esc=false;  }
    else if(chr=='}' ) { nst=true;  opn='{'; qut=ignqut; esc=false;  }
    else if(chr=='>' ) { nst=true;  opn='<'; qut=ignqut; esc=false;  }
    else if(chr=='"' ) { nst=false; opn=0;   qut=false;  esc=ignesc; }
    else if(chr=='\'') { nst=false; opn=0;   qut=false;  esc=ignesc; }
    else               { nst=false; opn=0;   qut=ignqut; esc=ignesc; }

    for(; ofs<=end; ofs++) {
        char cur=str.charAt(ofs);
        if     (cur==opn  && nst) { lvl++; continue;                                  }
        else if(cur=='\'' && qut) { ofs=skipTo(cur,str,(ofs+1),end,false,ignesc); }
        else if(cur=='\"' && qut) { ofs=skipTo(cur,str,(ofs+1),end,false,ignesc); }
        else if(cur==chr) {
            if((!esc || !isEscaped(str,beg,ofs)) && (--lvl)==0) { break; }
            }
        }
    return ofs;
    }

static private boolean isEscaped(String str, int beg, int ofs) {
    boolean                             ie=false;

    while(ofs>beg && str.charAt(--ofs)=='\\') { ie=!ie; }
    return ie;
    }

} // END PUBLIC CLASS