Evaluating math expressions given as a string
Author
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?
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++".
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++".
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.
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).
bison docs here, there are also win32 version (I'm using it under linux, though).
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]
-jouley
[Edit: Renamed a link]
[Edited by - jouley on March 2, 2007 11:05:29 AM]
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.
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.
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.
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)
Quote:Original post by ravyne2001
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.
second this
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
