Mathematical Function Parser

I'm looking at making a Function parser in C++ that will take sloppily written functions, clean them up, and evaluate them. Uses of this would include writing simple calculators, graphing calculators, and the like.

As I see it, there would be three main classes:
variables (constants, intrinsic, user defined)
functions (intrinsic, user defined, single & multi-argument, default-argument)
operators (intrinsic, user defined, precedence optionally set by user)

There should be some way to make additional evaluations of a given function (read: parse a function so that a smaller amount of work has to be done to evaluate it a second time).

Anything else you would want to add would be excellent. I am looking for people to give me ideas on what to include, and possibly people to help me code it. I will definately need some guidance on syntax. I have done a function parser in VB with some of the above capabilities, but I have a feeling C++ will be *slightly* faster. Not only that, but I have a feeling it is an excellent way to acquaint myself with the syntax used.

Hehe, Hey man I am doing the EXACT SAME THING!!!

But I am currently in the process of supporting simple math functions (abs, cos, sin, etc)...

And you are right, C++ is much faster (about 1000:1 or more)!! If used right (but still faster if used incorrect and sloppy)...

Here's what I used to get me started:

Code:

---


I found this on a Newsgroup at: http://groups.google.com/

And im sorry, I lost the URL before I was able to give the proper author credit...

A simple solution to implement:

Uses two stacks:
  operand stack
  operator stack

The expression is parsed from left to right, one item at a time.

Initial state: 8 * 4 + 1 / 9 * 9 * 6
              ^
  operand stack = empty
  operator stack = empty

The first item is the operand 8. When an operand is found, we always
push it on the stack.
I will refer to this action as action 1.

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 1)
          ^
  operand stack = 8
  operator stack = empty

The next item is the operator *.

If the new operator's precedence is higher than the precedence of the
operator
at the top of stack, we do the following:
  Push the operator on the operator stack
I will refer to this action as action 2a.

If the new operator's precedence is lower or equal to the precedence of
the operator at
the top of stack, we do the following:
  Pop off one operator from the operator stack (op),
  Pop off two operands from the operand stack (v1 and v2),
  Push the result of the (v1 op v2) on the operand stack,
  Push the new operator on the operator stack.
I will refer to this action as action 2b.
     
Remark: if the operator stack is empty we use action 2a.

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 2a)
            ^
  operand stack = 8
  operator stack = *

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 1)
              ^
  operand stack = 8 4
  operator stack = *

New state: 8 * 4 + 1 / 9 * 9 * 6  (action 2b)
                ^
  operand stack = 32
  operator stack = +

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 1)
                  ^
  operand stack = 32 1
  operator stack = +

New state: 8 * 4 + 1 / 9 * 9 * 6  (action 2a)
                    ^
  operand stack = 32 1
  operator stack = + /

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 1)
                      ^
  operand stack = 32 1 9
  operator stack = + /

New state: 8 * 4 + 1 / 9 * 9 * 6  (action 2b)
                        ^
  operand stack = 32 0.11
  operator stack = + *

New state: 8 * 4 + 1 / 9 * 9 * 6  (action 1)
                          ^
  operand stack = 32 0.11 9
  operator stack = + *

New state: 8 * 4 + 1 / 9 * 9 * 6  (action 2b)
                            ^
  operand stack = 32 1
  operator stack = + *

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 1)
                              ^
  operand stack = 32 1 6
  operator stack = + *

When the expression is entirely parsed we must unwind the stack.
Do the following until they are no more operators:
  Pop off the operator from the operator stack (op),
  Pop off two operands from the operand stack (v1 and v2),
  Push the result of the (v1 op v2) on the operand stack,
I will refer to this action as action 3.

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 3)
                                ^
  operand stack = 32 6
  operator stack = +

New state: 8 * 4 + 1 / 9 * 9 * 6 (action 3)
                                ^
  operand stack = 38
  operator stack = empty

The result is 38 (the remaining value on the operand stack)

This algorithm can be extended to process any type of mathematical
expression (electronic calculators use the same kind of algorithm).

Hope it helps...

---

Anyways, thats what you have to do for beginers.

If you dont know what a stack is or how to implement it, then here is some info:

basically you have an array of MAX_LENGTH size (could be anything, i used 80) and a counter

then to PUSH or ADD to the stack you increment the counter and set that value to the value being pushed... (confusing?)

to POP or REMOVE, you decrement the counter and return the value

Code:

---


int stack[MAX_LENGTH] = {0};
int counter = 0;

void push(int s[], int c, int value)
{
    s[c++] = value;
}

int pop(int s[], int c)
{
    return s[--c];
}

---

Thats all... if you need some more source code and a sample... let me know and ill give you something...

in case you want to try my expression evaluator out, i will attach it, try it (the GUI is vb, and the expression engine is in C++ dll).

Regards,
MoMad

while you are at it ... why not just write your own compiler??? :D


expression parsing is one of the more difficult aspects of compiler design, IMHO.

Well Actually, doesnt have to be :)

What if you are making a game that people can make new maps for, like Quake or any of the extendable mod'able games out there... wouldnt you need to load everything from a file? Now, apply the same concepts to a program like, hummmm... a Particle Engine, you want it to support all kinds of Particle Systems,... like Fire, Ice, Snow, Rain, etc... and some funky ones too... are you just gonna hard code it in the program? What if its a program like photoshop? What if you just want that particle applied to a game? What if....

You see, these things are very usefull and do not require re-inventing the wheel. But you need to know how incase the need comes up!! Anyways, im making a game and thats what mine is for... my game will have a particle engine, and i am planning on loading all of the particles from a file instead of hard-coding them :)

%GamePath%/Particles/Fire.dat

etc...


the thing is, particles are not a static thing to play around with... you cant just say something like, particle.x = 5, it has to be a variable... and the only way to do that, is to have the ability to parse expressions at run-time!!!!

so that your particle system is not just a boring pixel on the screen!!!!!! Now, there are many, many, many, other uses for this... for instance, i plan on having AI in my game, and absolutely dont plan on having to hard code it all... I want to have a seperate program (server) that controlls each player.... and that program will take care of all the ai, and communicate back and forth... how? simple, it will pass the game a behavior string that is to be parsed by the game... if my AI was hard coded, then this program would be useless. This way, i dont have to recompile my entire program if i want to say, make a competition of computers... and believe me, the need will arise!!

And so the moral of the story goes something like this....


Making a parser does NOT mean making a compiler. But the process is the exact same for making a compiler.... but then again, who said making a parser is not the same as making a compiler? oh yeah, it was me... oh well, better luck next time :D

Sometimes, you have to re-invent the wheel in order to take it for a spin!

Hey, hey hey.... who says it will be easy? It took me a while to get it right.. but it works just fine now!!

Take a look:

ExprTest.zip


[EDIT]
A While means a few days
[/EDIT]