Smart design of a math parser?

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? I did write one in VB6 ages ago but it ended up being way to bloated and not very portable (or smart for that matter...). General ideas, psuedo code or real code is appreciated.

Answer 1

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

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

Answer 3

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.

Answer 4

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.

Answer 5

This is a great tutorial series to get started writing your own parser. It's really not that hard.

http://compilers.iecc.com/crenshaw/

Answer 6

The related question Equation (expression) parser with precedence? has some good information on how to get started with this as well.

Answer 7

There's a few tutorials on JavaCC that use a calculator as an example on how to use JavaCC to generate a parser, like this tutorial or the one included in the JavaCC distribution by default. Ofcourse this is java based, but there's quite some EBNF based parser generators out there.

Answer 8

I wrote a few blog posts about designing a math parser. There is a general introduction, basic knowledge about grammars, sample implementation written in Ruby and a test suite. Perhaps you will find these materials useful.

Answer 9

I have written an infix to postfix algorithm some years ago. I put it on my blog tonight so you can have a look at it.

It is not the same as Dijkstra's. He uses a stack, I only use an array. I think its quite neat. Please have a look.

Answer 10

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

Answer 11

eval(...) works for me.

Answer 12

An easy way to do it is as follows. Let's demonstrate it with an example:

(x+y)/sin(x)-1

1. Find the operator that will be executed LAST. How to do this: We walk left to right. Everytime we open paranthesis, we increment level, everytime we close, we decrement. The operator we are looking for is at level 0. In above example, + is at level 1, so it cannot be the one we look for. We have / but when we reach -, it's precedence is less, so it must be executed AFTER /. We reach the end of the string with - being our guy.

2. From the location of -, divide the expression in two pieces:

Operator: -

Left: (x+y)/sin(x)

Right: 1

For Left and for Right, recursively repeat above steps.

At the end we end up with a tree structure which we can walk to evaluate the expression.

This is how Math Parsers from Bestcode.com works.

JbcParser makes it possible to parse and evaluate mathematical expressions in your Java programs. This math parser library precompiles the expression into an abstract syntax tree so that repeated expressions are as fast as it gets.

JbcParser - Math Parser for Java features include:

Easy to use, simple class API.
Comes with predefined functions.
You can create custom functions/variables and get callbacks to your own functions in your source code.
Function/variable names start with letters and can contain letters, numbers and ’_’.
Optimization: Constant expression elimination for repeated tasks.
Operators: +, -, /, *, ^
Boolean Operators: <, >, =, &, |, ! ,<>, >=, <=
Paranthesis: (, {, [
Functions in the form of: f(x,y,z, ...)
Function parameter calculations are only done if needed.
List of predefined functions is available in the documentation.
Provides localization support.
Royalty free distribution.
Source code is included.

JbcParser is especially useful in scientific and engineering programs as well as financial spread sheet implementations.

To be efficient in repeated calculations, parser creates a parse tree at first and re-uses this parse tree for each evaluation without the need to reparse.

Optimizer: If Optimization is on, the parse tree will be optimized by calculating constant expression sections at once so that further evaluation requests will be quicker without the need to re-evaluate those constant branches.

JbcParser comes with the Java Math Parser source code and there is also help documentation available for reference. Download is a single zip file with size of around 290KB. Package contains source files, Jar file, sample Applet, JavaDocs.

Examples of typical expressions are:

SIN(3.14)+5^2+POW(2,MAX(X*2,Y))

Functions, variables, constants can be nested. Common math functions are defined by default.

2*[LN(1+X) / LOG(1-X)]

Paranthesis can be (, {, [ for readability.

IF(X>0, 3/X, F(X))

You can avoid Division By Zero errors as in 3/X. (3/X will not be evaluated if X>0 is false - parameters to functions are evaluated only if required by the internal logic of a function).

IF(a,b,c) branching function is supported.

Boolean operators are supported. Any non-zero value is TRUE, 0 is FALSE.

Functions can be defined to have 1,2,...N numbers of parameters.

PI*(R^2)

Constants supported. For example, PI is a constant, not a variable. When optimization is turned on, constants may improve the speed of repeated evaluations where expression does not change but variable values change.

X+Y/LOG(1+5)

If Optimization is turned ON, LOG(1+5) will be optimized away since it is a constant.

VOLUME(HEIGHT, WIDTH, LENGTH)

You can create your own functions and variables and name them as you wish.

You can replace a predefined function with your own implementation.

X+COSH(3E-2)

Scientific notation is supported: 3E-2

SUM(1,2,3,4,5,6,...n) Functions that take unknown number of parameters are supported.