# Evaluating math expressions given as a string

## Recommended Posts

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

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
I used this one in one of my earlier projects. It's basically a function that takes in a string and returns a function pointer.

#### Share this post

##### Share on other sites
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

##### Share on other sites
You could take a look at Operator-precedence parsers or Dijkstra's Shunting Yard Algoirthm which is designed to parse infix notation into RPN notation, which is easily evaluated using a stack and some simple execution logic.

#### Share this post

##### Share on other sites
Quote:
 Original post by SneftelJust 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

##### Share on other sites
Quote:
 Original post by ravyne2001You could take a look at Operator-precedence parsers or Dijkstra's Shunting Yard Algoirthm which is designed to parse infix notation into RPN notation, which is easily evaluated using a stack and some simple execution logic.

second this

#### Share this post

##### Share on other sites
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

##### Share on other sites
Admittedly I've only used boost.spirit once, but why hasn't it been mentioned yet? I would have thought it was ideal.

#### Share this post

##### Share on other sites
Quote:
 Original post by DaBookshahAdmittedly 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

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
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.

## 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

• ### Forum Statistics

• Total Topics
628316
• Total Posts
2982033

• 9
• 9
• 13
• 11
• 14