Sign in to follow this  
Miksan

Evaluating math expressions given as a string

Recommended Posts

Miksan    126
If I have a string like "2x^2+5x+7", "log(x)+ln(x)+sqrt(x)", "sin(x)^2-cos(x)", "(x^2+y^2)(2-x^2-y^2)", how could I parse it for evaluation and plotting? I'm using C. Some things I thought: - convert the expression into valid programming language syntax, wrap it inside a function, compile it dynamically and then use it - not possible in C though...? - use some ready library designed for this - preferred, though I didn't find any Any ideas?

Share this post


Link to post
Share on other sites
AshleysBrain    162
This task is well suited to C++. Why stick with C? You can represent each operator and operand as an abstract 'expression part' class with a virtual 'Evaluate' function. Once you've parsed the string and built a tree of these classes, you can evaluate it very quickly (just a few virtual calls).

You may also want to use some kind of variant class if you deal with any other types than floats. There are probably examples on this around the interweb, try googling "expression evaluation C++".

Share this post


Link to post
Share on other sites
TheUnbeliever    963
Quote:
Original post by Miksan
- convert the expression into valid programming language syntax, wrap it inside a function, compile it dynamically and then use it - not possible in C though...?


This is possible, but I can't help but think you're using a tactical nuclear weapon to crack a nut.

Quote:
Any ideas?


Try Googling for lexing and parsing - although these are likely to turn up examples far beyond what you need. Perhaps Googling for 'write your own calculator' tutorials would be useful.

Off the top of my head, why not just map tokens to a set of functions (using a 2D array of char strings and function pointers, perhaps). Of course, you still need to be able to parse the string for the tokens themselves (re:retreiving functions and the appropriate number of arguments: this kind of thing is easier to compute using RPN - look into Dijkstra's shunting yard algorithm to convert from infix) but I'm assuming that's within your capabilities.

Share this post


Link to post
Share on other sites
cobru    193
Or, you can write a simple grammar.y for bison (or use the example calculator available in the bison tutorial) and get away with doing it in C :D

bison docs here, there are also win32 version (I'm using it under linux, though).

Share this post


Link to post
Share on other sites
jouley    805
When I was in the practice of reinventing wheels, I wrote an expression matcher using recursive descent, and it seems like it's equally viable here, for a well-defined vocabulary and grammatical structure (List of functions: log, ln, sqrt, etc; and the arguments they take are easily defined). Reading that wiki page led to the boost:spirit parser framework, which seems to have done all the hard work for you.

-jouley

[Edit: Renamed a link]

[Edited by - jouley on March 2, 2007 11:05:29 AM]

Share this post


Link to post
Share on other sites
Sneftel    1788
Compile Lua into your project and evaluate the string as a Lua expression. Or compile Python into your project and evaluate the string as a Python expression. Or compile TCL into your project and evaluate the string as a TCL expression. Or compile Perl into your project and evaluate the string as a Perl expression. Et cetera.

Share this post


Link to post
Share on other sites
Zahlman    1682
Quote:
Original post by Sneftel
Just use Lua and eval(); you can optimize the rest of the project later by writing and calling into C DLLs if you have to. Or just use Python and eval(); you can optimize the rest of the project later by writing and calling into C DLLs if you have to. Or just use Perl and eval(); you can optimize the rest of the project later by writing and calling into C DLLs if you have to. Et cetera.


Fixed? (*TCL*? o_O)

Share this post


Link to post
Share on other sites
mikeman    2942
I agree with Sneftel, this is by far the most easy(and scalable) solution.

Other than that, the last time I did it myself(for a program that produced 3D graphical representations of functions), I just converted the expression into Reverse Polish Notation(it's pretty easy), and based on that I dynamically produced assembly code that used the FPU stack(which also works with RPN, so it basically was a 1-1 translation, all I had to do is look up the opcodes of the various instructions).

Share this post


Link to post
Share on other sites
jouley    805
Quote:
Original post by DaBookshah
Admittedly I've only used boost.spirit once, but why hasn't it been mentioned yet? I would have thought it was ideal.

I should have made it clear that that was my second link, above. Editing now...

Share this post


Link to post
Share on other sites
Miksan    126
Thanks for your ideas! It seems that using Shunting yard algorithm to convert infix notation to Reverse polish notation and then evaluating that looks like a nice solution ;)

Share this post


Link to post
Share on other sites
Rockoon1    104
Yes, and RPN isnt just easy to evaluate .. it is also easy to compile to a target processor instruction set!

The stack paradigm fits well with both stack based processors and register based processors (in the register based case, the compiler maintains a stack of unused registers names while compiling) which is why both Java's IL and .NET's IL use a stack based paradigm.

Stack based expressions also lends themselves well to be converted to and from abstract syntax tree's (AST's) which is at the heart of most optimizing compilers (GCC, Intel C++, VC++, etc..)

Share this post


Link to post
Share on other sites
_goat    804
The easiest way I've found is to use the ANTLR approach, which takes something like this:

x = 4 * 8 + 5 * (7 + 19)^2 - 12 - -55

And produces this (I normally use imaginary base nodes to avoid ambiguities and to help with optimisation):

( assignment x ( sub ( add ( mul 4 8 ) ( mul 5 ( power ( add 7 19 ) 2 ) ) ) 12 ( neg 55 ) )

That may be a little hard to read, but it's very easy to parse. Don't scream at me if I forgot a bracket or something.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this