How to evaluate a math expression given in string form?

Solution 1:

With JDK1.6, you can use the built-in Javascript engine.

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

public class Test {
  public static void main(String[] args) throws ScriptException {
    ScriptEngineManager mgr = new ScriptEngineManager();
    ScriptEngine engine = mgr.getEngineByName("JavaScript");
    String foo = "40+2";
    System.out.println(engine.eval(foo));
    } 
}

Solution 2:

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!}

Solution 3:

For my university project, I was looking for a parser / evaluator supporting both basic formulas and more complicated equations (especially iterated operators). I found very nice open source library for JAVA and .NET called mXparser. I will give a few examples to make some feeling on the syntax, for further instructions please visit project website (especially tutorial section).

https://mathparser.org/

https://mathparser.org/mxparser-tutorial/

https://mathparser.org/api/

And few examples

1 - Simple furmula

Expression e = new Expression("( 2 + 3/4 + sin(pi) )/2");
double v = e.calculate()

2 - User defined arguments and constants

Argument x = new Argument("x = 10");
Constant a = new Constant("a = pi^2");
Expression e = new Expression("cos(a*x)", x, a);
double v = e.calculate()

3 - User defined functions

Function f = new Function("f(x, y, z) = sin(x) + cos(y*z)");
Expression e = new Expression("f(3,2,5)", f);
double v = e.calculate()

4 - Iteration

Expression e = new Expression("sum( i, 1, 100, sin(i) )");
double v = e.calculate()

Found recently - in case you would like to try the syntax (and see the advanced use case) you can download the Scalar Calculator app that is powered by mXparser.

Solution 4:

The correct way to solve this is with a lexer and a parser. You can write simple versions of these yourself, or those pages also have links to Java lexers and parsers.

Creating a recursive descent parser is a really good learning exercise.

How to evaluate a math expression given in string form?

Solution 1:

Solution 2:

Solution 3:

Solution 4:

Related

Recent Posts