java: how to implement math parsing_问答_开发者

I am trying to implement a simple math parser in java. This is for my small school project working with matrices that enables to input some simple equations, such as A^-1(B+C) and then the program asks to input matrices A,B and C and outputs result for these operations.

What I got so far is a class called MathParser, that creates o开发者_如何转开发bjects of class Operation. Operation has methods like setOperation ( one of plus,times,inverse,power) and addInput(Matrix|Operation|int) and finally executeOperation() that loops all items from addInput() and executes chosen operation from setOperation. If it finds that some item from the input is instance of class Operation, it executes it first - this is a sort of recurrent calling. It is done this way to manage operation order - multiplying comes before addition etc.

However, I don't find this solution very good. Do you have any ideas how to implement such a task?

I found a blog describing how to parse and execute expressions in a simple calculator then looking on expression trees.

It might be a litle over the top but it should give some tips:

http://community.bartdesmet.net/blogs/bart/archive/2006/10/11/4513.aspx

Well, maybe this solution is not exactly what you need/want to implement or maybe it's a overkill, but I'd go with some scripting engine (for example Groovy). In that case this is how your code would look:

GroovyShell shell = new GroovyShell();
shell.setVariable("a",10);
shell.setVariable("b",20);
int result = ((Number) shell.evaluate("(a+b)/2")).intValue();

Moreover, you can also parse formulas of any complexity or even using your specific calculation functions. You just put it all into the shell and then evaluate the input string.

Added: Operators do not work with matrices by default, but it is not hard to implement that with groovy as it supports operator overloading (read more about it here: http://groovy.codehaus.org/Operator+Overloading)

So here is an example with matrices:

class Matrix {
    private int[][] data;

    public Matrix(int[][] data) {
        this.data = data;
    }

    public int[][] getData() {
        return data;
    }

    //Method that overloads the groovy '+' operator
    public Matrix plus(Matrix b) {
        Matrix result = calculateMatrixSumSomehow(this,b);
        return result;
    }
}

Now in your call will look like this:

shell.setVariable("A",new Matrix(...));
shell.setVariable("B",new Matrix(...));
Matrix result = (Matrix)shell.evaluate("A+B"); //+ operator will use 'plus' function

The canonical method for parsing mathematical expressions is the shunting yard algorithm. It is a very simple and elegant algorithm, and implementing it will teach you a lot.

http://en.wikipedia.org/wiki/Shunting-yard_algorithm has a good description, complete with a worked example.

Have you considered using embedded scripting?

i released an expression evaluator based on Dijkstra's Shunting Yard algorithm, under the terms of the Apache License 2.0:

http://projects.congrace.de/exp4j/index.html

Have a look at http://bracer.sourceforge.net It's my implementation of shunting-yard algorithm.

You can consider using library built specifically for math expression parsing, such as mXparser. You will get a lot of very helpful options:

1 - Checking expression syntax

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("2+3-");
e.checkSyntax();
mXparser.consolePrintln(e.getErrorMessage());

Result:

[mXparser-v.4.0.0] [2+3-] checking ...
[2+3-] lexical error 

Encountered "<EOF>" at line 1, column 4.
Was expecting one of:
    "(" ...
    "+" ...
    "-" ...
    <UNIT> ...
    "~" ...
    "@~" ...
    <NUMBER_CONSTANT> ...
    <IDENTIFIER> ...
    <FUNCTION> ...
    "[" ...

[2+3-] errors were found.

[mXparser-v.4.0.0]

2 - Evaluating expression

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("2+3-(10+2)");
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

Result:

[mXparser-v.4.0.0] 2+3-(10+2) = -7.0

3 - Using built-in functions constants, operators, etc..

import org.mariuszgromada.math.mxparser.*;
...
...
Expression e = new Expression("sin(pi)+e");
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

Result:

[mXparser-v.4.0.0] sin(pi)+e = 2.718281828459045

4 - Defining your own functions, arguments and constants

import org.mariuszgromada.math.mxparser.*;
...
...
Argument z = new Argument("z = 10");
Constant a = new Constant("b = 2");
Function p = new Function("p(a,h) = a*h/2");
Expression e = new Expression("p(10, 2)-z*b/2", p, z, a);
mXparser.consolePrintln(e.getExpressionString() + " = " + e.calculate());

Result:

[mXparser-v.4.0.0] p(10, 2)-z*b/2 = 0.0

5 - Tokenizing expression string and playing with expression tokens

import org.mariuszgromada.math.mxparser.*;
...
...
Argument x = new Argument("x");
Argument y = new Argument("y");
Expression e = new Expression("2*sin(x)+(3/cos(y)-e^(sin(x)+y))+10", x, y);
mXparser.consolePrintTokens( e.getCopyOfInitialTokens() );

Result:

[mXparser-v.4.0.0]  --------------------
[mXparser-v.4.0.0] | Expression tokens: |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------
[mXparser-v.4.0.0] |    TokenIdx |       Token |        KeyW |     TokenId | TokenTypeId |  TokenLevel |  TokenValue |   LooksLike |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------
[mXparser-v.4.0.0] |           0 |           2 |       _num_ |           1 |           0 |           0 |         2.0 |             |
[mXparser-v.4.0.0] |           1 |           * |           * |           3 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |           2 |         sin |         sin |           1 |           4 |           1 |         NaN |             |
[mXparser-v.4.0.0] |           3 |           ( |           ( |           1 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           4 |           x |           x |           0 |         101 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           5 |           ) |           ) |           2 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |           6 |           + |           + |           1 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |           7 |           ( |           ( |           1 |          20 |           1 |         NaN |             |
[mXparser-v.4.0.0] |           8 |           3 |       _num_ |           1 |           0 |           1 |         3.0 |             |
[mXparser-v.4.0.0] |           9 |           / |           / |           4 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          10 |         cos |         cos |           2 |           4 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          11 |           ( |           ( |           1 |          20 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          12 |           y |           y |           1 |         101 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          13 |           ) |           ) |           2 |          20 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          14 |           - |           - |           2 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          15 |           e |           e |           2 |           9 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          16 |           ^ |           ^ |           5 |           1 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          17 |           ( |           ( |           1 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          18 |         sin |         sin |           1 |           4 |           3 |         NaN |             |
[mXparser-v.4.0.0] |          19 |           ( |           ( |           1 |          20 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          20 |           x |           x |           0 |         101 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          21 |           ) |           ) |           2 |          20 |           4 |         NaN |             |
[mXparser-v.4.0.0] |          22 |           + |           + |           1 |           1 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          23 |           y |           y |           1 |         101 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          24 |           ) |           ) |           2 |          20 |           2 |         NaN |             |
[mXparser-v.4.0.0] |          25 |           ) |           ) |           2 |          20 |           1 |         NaN |             |
[mXparser-v.4.0.0] |          26 |           + |           + |           1 |           1 |           0 |         NaN |             |
[mXparser-v.4.0.0] |          27 |          10 |       _num_ |           1 |           0 |           0 |        10.0 |             |
[mXparser-v.4.0.0]  ---------------------------------------------------------------------------------------------------------------

6 - Whats equally important - you will find much more in mXparser tutorial, mXparser math collection and mXparser API definition.

7 - mXparser supports: