[Java] Evaluating a math expression given in string form



Answers

I've written this eval method for arithmetic expressions to answer this question. It does addition, subtraction, multiplication, division, exponentiation (using the ^ symbol), and a few basic functions like sqrt. It supports grouping using (...), and it gets the operator precedence and associativity rules correct.

public static double eval(final String str) {
    return new Object() {
        int pos = -1, ch;

        void nextChar() {
            ch = (++pos < str.length()) ? str.charAt(pos) : -1;
        }

        boolean eat(int charToEat) {
            while (ch == ' ') nextChar();
            if (ch == charToEat) {
                nextChar();
                return true;
            }
            return false;
        }

        double parse() {
            nextChar();
            double x = parseExpression();
            if (pos < str.length()) throw new RuntimeException("Unexpected: " + (char)ch);
            return x;
        }

        // Grammar:
        // expression = term | expression `+` term | expression `-` term
        // term = factor | term `*` factor | term `/` factor
        // factor = `+` factor | `-` factor | `(` expression `)`
        //        | number | functionName factor | factor `^` factor

        double parseExpression() {
            double x = parseTerm();
            for (;;) {
                if      (eat('+')) x += parseTerm(); // addition
                else if (eat('-')) x -= parseTerm(); // subtraction
                else return x;
            }
        }

        double parseTerm() {
            double x = parseFactor();
            for (;;) {
                if      (eat('*')) x *= parseFactor(); // multiplication
                else if (eat('/')) x /= parseFactor(); // division
                else return x;
            }
        }

        double parseFactor() {
            if (eat('+')) return parseFactor(); // unary plus
            if (eat('-')) return -parseFactor(); // unary minus

            double x;
            int startPos = this.pos;
            if (eat('(')) { // parentheses
                x = parseExpression();
                eat(')');
            } else if ((ch >= '0' && ch <= '9') || ch == '.') { // numbers
                while ((ch >= '0' && ch <= '9') || ch == '.') nextChar();
                x = Double.parseDouble(str.substring(startPos, this.pos));
            } else if (ch >= 'a' && ch <= 'z') { // functions
                while (ch >= 'a' && ch <= 'z') nextChar();
                String func = str.substring(startPos, this.pos);
                x = parseFactor();
                if (func.equals("sqrt")) x = Math.sqrt(x);
                else if (func.equals("sin")) x = Math.sin(Math.toRadians(x));
                else if (func.equals("cos")) x = Math.cos(Math.toRadians(x));
                else if (func.equals("tan")) x = Math.tan(Math.toRadians(x));
                else throw new RuntimeException("Unknown function: " + func);
            } else {
                throw new RuntimeException("Unexpected: " + (char)ch);
            }

            if (eat('^')) x = Math.pow(x, parseFactor()); // exponentiation

            return x;
        }
    }.parse();
}

Example:

System.out.println(eval("((4 - 2^3 + 1) * -sqrt(3*3+4*4)) / 2"));

Output: 7.5 (which is correct)


The parser is a recursive descent parser, so internally uses separate parse methods for each level of operator precedence in its grammar. I kept it short so it's easy to modify, but here are some ideas you might want to expand it with:

  • Variables:

    The bit of the parser that reads the names for functions can easily be changed to handle custom variables too, by looking up names in a variable table passed to the eval method, such as a Map<String,Double> variables.

  • Separate compilation and evaluation:

    What if, having added support for variables, you wanted to evaluate the same expression millions of times with changed variables, without parsing it every time? It's possible. First define an interface to use to evaluate the precompiled expression:

    @FunctionalInterface
    interface Expression {
        double eval();
    }
    

    Now change all the methods that return doubles, so instead they return an instance of that interface. Java 8's lambda syntax works great for this. Example of one of the changed methods:

    Expression parseExpression() {
        Expression x = parseTerm();
        for (;;) {
            if (eat('+')) { // addition
                Expression a = x, b = parseTerm();
                x = (() -> a.eval() + b.eval());
            } else if (eat('-')) { // subtraction
                Expression a = x, b = parseTerm();
                x = (() -> a.eval() - b.eval());
            } else {
                return x;
            }
        }
    }
    

    That builds a recursive tree of Expression objects representing the compiled expression (an abstract syntax tree). Then you can compile it once and evaluate it repeatedly with different values:

    public static void main(String[] args) {
        Map<String,Double> variables = new HashMap<>();
        Expression exp = parse("x^2 - x + 2", variables);
        for (double x = -20; x <= +20; x++) {
            variables.put("x", x);
            System.out.println(x + " => " + exp.eval());
        }
    }
    
  • Different datatypes:

    Instead of double, you could change the evaluator to use something more powerful like BigDecimal, or a class that implements complex numbers, or rational numbers (fractions). You could even use Object, allowing some mix of datatypes in expressions, just like a real programming language. :)


All code in this answer released to the public domain. Have fun!

Question

I'm trying to write a Java routine to evaluate simple math expressions from String values like:

  1. "5+3"
  2. "10-40"
  3. "10*3"

I want to avoid a lot of if-then-else statements. How can I do this?




External library like RHINO or NASHORN can be used to run javascript. And javascript can evaluate simple formula without parcing the string. No performance impact as well if code is written well. Below is an example with RHINO -

public class RhinoApp {
    private String simpleAdd = "(12+13+2-2)*2+(12+13+2-2)*2";

public void runJavaScript() {
    Context jsCx = Context.enter();
    Context.getCurrentContext().setOptimizationLevel(-1);
    ScriptableObject scope = jsCx.initStandardObjects();
    Object result = jsCx.evaluateString(scope, simpleAdd , "formula", 0, null);
    Context.exit();
    System.out.println(result);
}



This article points to 3 different approaches, one which is JEXL from Apache and allows for scripts that include references to java objects.




How about something like this:

String st = "10+3";
int result;
for(int i=0;i<st.length();i++)
{
  if(st.charAt(i)=='+')
  {
    result=Integer.parseInt(st.substring(0, i))+Integer.parseInt(st.substring(i+1, st.length()));
    System.out.print(result);
  }         
}

and do the similar thing for every other mathematical operator accordingly ..







Try the following sample code using JDK1.6's Javascript engine with code injection handling.

import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;

public class EvalUtil {
private static ScriptEngine engine = new ScriptEngineManager().getEngineByName("JavaScript");
public static void main(String[] args) {
    try {
        System.out.println((new EvalUtil()).eval("(((5+5)/2) > 5) || 5 >3 "));
        System.out.println((new EvalUtil()).eval("(((5+5)/2) > 5) || true"));
    } catch (Exception e) {
        e.printStackTrace();
    }
}
public Object eval(String input) throws Exception{
    try {
        if(input.matches(".*[a-zA-Z;~`#$_{}\\[\\]:\\\\;\"',\\.\\?]+.*")) {
            throw new Exception("Invalid expression : " + input );
        }
        return engine.eval(input);
    } catch (Exception e) {
        e.printStackTrace();
        throw e;
    }
 }
}



I think what ever way you do this it's going to involve a lot of conditional statements. But for single operations like in your examples you could limit it to 4 if statements with something like

String math = "1+4";

if (math.split("+").length == 2) {
    //do calculation
} else if (math.split("-").length == 2) {
    //do calculation
} ...

It gets a whole lot more complicated when you want to deal with multiple operations like "4+5*6".

If you are trying to build a calculator then I'd surgest passing each section of the calculation separatly (each number or operator) rather than as a single string.







public static void main(String[] args){   
    System.out.println("="+evaluate(args[2]));

}
public static String[] symbols = new String[]{"\\-","\\+","\\/","\\*"};

public static Integer evaluate(String exp){
    System.out.print(exp);
    exp = exp.trim(); 
    boolean isint = true;
    for(int i = 0; i<exp.length() && isint;i++){
        if(exp.charAt(i)>'9' || exp.charAt(i) <'0'){
            isint = false;
        }
    }
    if(isint) return Integer.parseInt(exp);

    for(String symbol:symbols){
        String[] split = exp.split(symbol);
        if(split.length>1){
            int ev = evaluate(split[0]);
            for(int i = 1;i<split.length;i++){
                System.out.print(symbol);
                int val = evaluate(split[i]);
                if("\\*".equals(symbol)) ev*=val;
                if("\\/".equals(symbol)) ev/=val;
                if("\\+".equals(symbol)) ev+=val;
                if("\\-".equals(symbol)) ev-=val;
            }
            return ev;
        }
    }
    return null;
}



You might have a look at the Symja framework:

ExprEvaluator util = new ExprEvaluator(); 
IExpr result = util.evaluate("10-40");
System.out.println(result.toString()); // -> "-30" 

Take note that definitively more complex expressions can be evaluated:

// D(...) gives the derivative of the function Sin(x)*Cos(x)
IAST function = D(Times(Sin(x), Cos(x)), x);
IExpr result = util.evaluate(function);
// print: Cos(x)^2-Sin(x)^2



This is another interesting alternative https://github.com/Shy-Ta/expression-evaluator-demo

The usage is very simple and gets the job done, for example:

  ExpressionsEvaluator evalExpr = ExpressionsFactory.create("2+3*4-6/2");  
  assertEquals(BigDecimal.valueOf(11), evalExpr.eval()); 



HERE is another open source library on GitHub named EvalEx.

Unlike the JavaScript engine this library is focused in evaluating mathematical expressions only. Moreover, the library is extensible and supports use of boolean operators as well as parentheses.




You can evaluate expressions easily if your Java application already accesses a database, without using any other JARs.

Some databases require you to use a dummy table (eg, Oracle's "dual" table) and others will allow you to evaluate expressions without "selecting" from any table.

For example, in Sql Server or Sqlite

select (((12.10 +12.0))/ 233.0) amount

and in Oracle

select (((12.10 +12.0))/ 233.0) amount from dual;

The advantage of using a DB is that you can evaluate many expressions at the same time. Also most DB's will allow you to use highly complex expressions and will also have a number of extra functions that can be called as necessary.

However performance may suffer if many single expressions need to be evaluated individually, particularly when the DB is located on a network server.

The following addresses the performance problem to some extent, by using a Sqlite in-memory database.

Here's a full working example in Java

Class. forName("org.sqlite.JDBC");
Connection conn = DriverManager.getConnection("jdbc:sqlite::memory:");
Statement stat = conn.createStatement();
ResultSet rs = stat.executeQuery( "select (1+10)/20.0 amount");
rs.next();
System.out.println(rs.getBigDecimal(1));
stat.close();
conn.close();

Of course you could extend the above code to handle multiple calculations at the same time.

ResultSet rs = stat.executeQuery( "select (1+10)/20.0 amount, (1+100)/20.0 amount2");



Links