Java library to transform a math formula into an AST

Question

I am looking for a Java library which can parse mathematical formulas into an AST (abstract syntax tree).

UPDATE:
I'm open to alternatives in languages other than Java, provided that I can call these tools/libraries from Java.
For example, JavaScript can be embedded using the Rhino engine.

Essential Requirements:

1. The ability to parse formulas in infix notation.

2. The ability to preserve unknown variables — I am not looking for a calculator.

3. A customizable list of operators and functions.
   It would also be excellent if one could remove already built-in functions (e.g. sin(x)).

Non-Essential Requirements:

• The library can be open source, but it doesn't need to be. A free library suffices.

Answer 1

Math.js

The JavaScript part

“Math.js is an extensive math library for JavaScript and Node.js.”
— Project readme

It provides a parse() function.
Example using the NodeJS environment:

var math = require('mathjs')();
var ast = math.parse('xy^(1/2)');

// Fully log the object
var util = require('util');
console.log(util.inspect(ast, {showHidden: false, depth: null}));

Output:

{ op: '^',
  fn: 'pow',
  params:
   [ { name: 'xy' },
     { op: '/',
       fn: 'divide',
       params:
        [ { valueType: 'number', value: '1' },
          { valueType: 'number', value: '2' } ] } ] }

The Java part

I use the Java Nashorn VM (only available in Java >= 8) to execute JavaScript.

Program architecture:

User ---------------> Java
      inputs formla    |----> Nashorn ----> math.js
                       |<---------------------|
User <-----------------|

Using the Nashorn engine is quite simple (Exception handling omitted)

ScriptEngine engine = new ScriptEngineManager().getEngineByName("nashorn");
engine.eval(readerInstancePointingToMathJsLibrary);
engine.eval(readerInstancePointingToBridgeJavaScript);

The bridge's JavaScript code highly depends on your implementation of AST nodes. We take advantage of Nashorn's ability to create and transfer Java objects in JavaScript to Java. Example:

var math = mathjs();
function convert(formula) {
    var ast = math.parse(formula);

    var javaAst = /* build your AST with Java objects */
    return javaAst;
}

We can now access that function from Java and even pass arbitrary arguments:

Invocable inv = (Invocable) engine;
// Expression is my AST node type in Java
expr = (Expression) inv.invokeFunction("convert", formulaFromUser);

Note: I needed a quick way of parsing mathematical expressions. A parser (either handwritten or generated by a parser generator) is always preferable. Nonetheless, the code above shows how Java Nashorn can be easily integrated.

Answer 2

JavaScript

Few months ago, I used Esprima to parse such inputs. Actually, Esprima parses any JavaScript input (converting it into a tree), so it should work for such math expressions.

After including Esprima, you can do:

esprima.parse(input);

...where input is a string containing the input that should be parsed (if it's invalid, an error will be thrown).

Example

esprima.parse("1+2*3")

returns the following object:

{
    "type": "Program",
    "body": [
        {
            "type": "ExpressionStatement",
            "expression": {
                "type": "BinaryExpression",
                "operator": "+",
                "left": {
                    "type": "Literal",
                    "value": 1,
                    "raw": "1"
                },
                "right": {
                    "type": "BinaryExpression",
                    "operator": "*",
                    "left": {
                        "type": "Literal",
                        "value": 2,
                        "raw": "2"
                    },
                    "right": {
                        "type": "Literal",
                        "value": 3,
                        "raw": "3"
                    }
                }
            }
        }
    ]
}

I modified Esprima code and used it in an experimental project to define custom operators in JavaScript. The application is open source on GitHub: http://ionicabizau.net/JavaScript-custom-operators/

Answer 3

Java

It seems that JEP is a math expression parser.

JEP is a Java API for parsing and evaluating mathematical expressions. With this library you can allow your users to enter an arbitrary formula as a string, and instantly evaluate it. JEP supports user defined variables, constants, and functions. A number of common mathematical functions and constants are included.

Features

• Easy-to-use package for parsing mathematical expressions
• Small size (only 56kb as jar archive)
• Supports boolean expressions (!, &&, ||, <, >, !=, ==, >=, and <=)
• Fast evaluation (the expression can be evaluated quickly for different variable values)
• Includes common math functions
• Extendable through user defined functions
• Predefined constants such as 'pi' and 'e'
• Support for strings, complex numbers, and vectors
• Support for implicit multiplication (allows use of expressions such as "3x" instead of "3*x")
• Allows choice between declared and undeclared variables
• Java 1.1 compatible (tested with Sun Java JDK 1.1.8 and the Microsoft Java VM)
• Supports Unicode characters (including Greek symbols)
• Includes JavaCC grammar from which the main classes are generated

It's open source on SourceForge.

Also, there is a SO question regarding this subject: https://stackoverflow.com/q/4589951/1420197

Answer 4

Building formula parsers/tree builders is a pretty simple exercise. You can hunt for a library, but you'll always end up modifying it to produce exactly what you want. Instead, it is likely easier to simply code what you want.

• This StackOverflow link provides directions on how to build parsers like this easily by hand. It also provides access to a second link, that shows how to easily convert such parsers into ones that produce ASTs.
• You can easily customize to include whatever infix operators you like, whatever function operatos ("sin") you like, scalar values and variable names.
• You can code these kinds of parsers in virtually any language, including Java.

If you want to parse something considerably more complex than an expression, you can push this kind of parser to do it, but it is generally easier to switch to parser generator in that case.

Answer 5

Java

Symja transforms a math expression into the following Symja AST .

Answer 6

I have used javassist to convert Java expressions to byte code (which may be what you ultimately is looking for if you want to evaluate the expression). It can even redefine existing functions.

http://www.csg.ci.i.u-tokyo.ac.jp/~chiba/javassist/