Smart design of a math parser? [closed]

Question

What is the smartest way to design a math parser? What I mean is a function that takes a math string (like: "2 + 3 / 2 + (2 * 5)") and returns the calculated value?

Amboise

you can checkout a java implementation of the shunting yard algorithm here: projects.congrace.de/exp4j – Tautomerism

Answer 1

A pretty good approach would involve two steps. The first step involves converting the expression from infix to postfix (e.g. via Dijkstra's shunting yard) notation. Once that's done, it's pretty trivial to write a postfix evaluator.

Dacoit

I don't think the shunting yard algorithm can handle correct unary minus binding to bases of exponents. i.e. it can't parse -2^3 as -(2^3), only as (-2)^3. I might be wrong though, I don't know for sure. – Herby

@mebob That looks like user input error to me. I wouldn't bother to correct it. If I was feeling nice I might add something to check for it and alert the user that they may be wrong. – Ecklund

Answer 2

You have a couple of approaches. You could generate dynamic code and execute it in order to get the answer without needing to write much code. Just perform a search on runtime generated code in .NET and there are plenty of examples around.

Alternatively you could create an actual parser and generate a little parse tree that is then used to evaluate the expression. Again this is pretty simple for basic expressions. Check out codeplex as I believe they have a math parser on there. Or just look up BNF which will include examples. Any website introducing compiler concepts will include this as a basic example.

Codeplex Expression Evaluator

Oshea

Answer 3

If you have an "always on" application, just post the math string to google and parse the result. Simple way but not sure if that's what you need - but smart in some way i guess.

Terri

That's what i mean, you're smart enough to know how to get things done ;-) – Terri

Answer 4

I know this is old, but I came across this trying to develop a calculator as part of a larger app and ran across some issues using the accepted answer. The links were IMMENSELY helpful in understanding and solving this problem and should not be discounted. I was writing an Android app in Java and for each item in the expression "string," I actually stored a String in an ArrayList as the user types on the keypad. For the infix-to-postfix conversion, I iterated through each String in the ArrayList, then evaluated the newly arranged postfix ArrayList of Strings. This was fantastic for a small number of operands/operators, but longer calculations were consistently off, especially as the expressions started evaluating to non-integers. In the provided link for Infix to Postfix conversion, it suggests popping the Stack if the scanned item is an operator and the topStack item has a higher precedence. I found that this is almost correct. Popping the topStack item if it's precedence is higher OR EQUAL to the scanned operator finally made my calculations come out correct. Hopefully this will help anyone working on this problem, and thanks to Justin Poliey (and fas?) for providing some invaluable links.

Hatchment

Answer 5

Assuming your input is an infix expression in string format, you could convert it to postfix and, using a pair of stacks: an operator stack and an operand stack, work the solution from there. You can find general algorithm information at the Wikipedia link.

Ming

Answer 6

ANTLR is a very nice LL(*) parser generator. I recommend it highly.

Dawkins

Answer 7

Developers always want to have a clean approach, and try to implement the parsing logic from ground up, usually ending up with the Dijkstra Shunting-Yard Algorithm. Result is neat looking code, but possibly ridden with bugs. I have developed such an API, JMEP, that does all that, but it took me years to have stable code.

Even with all that work, you can see even from that project page that I am seriously considering to switch over to using JavaCC or ANTLR, even after all that work already done.

Herlindaherm

Answer 8

11 years into the future from when this question was asked: If you don't want to re-invent the wheel, there are many exotic math parsers out there.

There is one that I wrote years ago which supports arithmetic operations, equation solving, differential calculus, integral calculus, basic statistics, function/formula definition, graphing, etc.

Its called ParserNG and its free (DISCLAIMER: ParserNG is authored by me.)

Evaluating an expression is as simple as:

    MathExpression expr = new MathExpression("(34+32)-44/(8+9(3+2))-22"); 
    System.out.println("result: " + expr.solve());

    result: 43.16981132075472

Or using variables and calculating simple expressions:

 MathExpression expr = new MathExpression("r=3;P=2*pi*r;"); 
System.out.println("result: " + expr.getValue("P"));

Or using functions:

MathExpression expr = new MathExpression("f(x)=39*sin(x^2)+x^3*cos(x);f(3)"); 
System.out.println("result: " + expr.solve());

result: -10.65717648378352

Or to evaluate the derivative at a given point(Note it does symbolic differentiation(not numerical) behind the scenes, so the accuracy is not limited by the errors of numerical approximations):

MathExpression expr = new MathExpression("f(x)=x^3*ln(x); diff(f,3,1)"); 
System.out.println("result: " + expr.solve());

 result: 38.66253179403897

Which differentiates x^3 * ln(x) once at x=3. The number of times you can differentiate is 1 for now.

or for Numerical Integration:

MathExpression expr = new MathExpression("f(x)=2*x; intg(f,1,3)"); 
System.out.println("result: " + expr.solve());

result: 7.999999999998261... approx: 8

This parser is decently fast and has lots of other functionality.

Work has been concluded on porting it to Swift via bindings to Objective C and we have used it in graphing applications amongst other iterative use-cases.

Morentz

You would need to look at the documentation of both to see which has more functionality and especially, which has what you need. I speak of ParserNG though, and it has lots of functionality, possibly with even more coming. Apart from expression evaluation, it works with variables creation, functions creation, equations solving, matrix and statistics functions, differential and integral calculus among others. – Morentz