Calculating mathematical string

flowercamel · #1 28-Jan-2004, 12:03

Hello,

I'm coding a program that draws mathematical functions, among other things.

Drawing these functions with TCanvas hasn't been a problem so far, but I failed when I tried to draw functions entered by users.
The problem is that I don't know how to transform the string into C++ syntax.

As far as i know, there is no eval() function in C++.
Has anybody an idea how to calculate mathematical strings?

I would be very grateful for any kind of hint

dsmith · #2 28-Jan-2004, 13:59

Hey flowercamel, welcome to the forums.

I think I know what you are asking and there is no eval() function that I know of in C/C++. (please correct me if I am wrong.)

It sounds to me like you will need to write your own parsing program. I have done this on a limited basis in the past. Can you give examples of the type of user input that you will have and what you will be doing with it? Could this be done in a RPN fashion or does it need to be algebraic?

flowercamel · #3 29-Jan-2004, 05:20

Hello dsmith,

an example for the type of user input would be:

"y = -12*x^3 + 14.78*x^2 - 71.5*x + sin(2x) / 50"

and that's not even the worst case :-)

hm... I'm sorry, I don't know what is meant by "RPN fashion".

I only need to calculate the values of y for different values of x, so that my program is able to draw the graph of this function.

it should work like this:

double Funktion(double x, AnsiString term)
{
y = // here's the problem; it should calculate the value of y
// with the String that contains something like
// -12*x^3 + 14.78*x^2 - 71.5*x + sin(2x) / 50
return(y);
}

I think it must be pretty hard....
So i would be very pleased if anyone had some further hints for me.

Greetz
flowercamel

Garth Farley · #4 29-Jan-2004, 08:00

Ooh, evaluating a mathematical string is quite a bit of work. You've essentially got to parse it, token by token, and figure out the precedence, and since you're using sines and stuff, it'll be tough work.

RPN stands for Reverse Polish notation. It's a way of writing a mathematical string so that the precedence is implicitly known. ie.
3 5 + 7 *
stands for
(3 + 5) * 7.
The RPN works by placing every number on a stack until it hits an operator, then popping the top 2 elements off the stack & applying the op to them, and pushing the answer onto the stack. Keep at this until you've parsed the whole thing.

To convert normal to RPN, you've to parse the string again. This time, place each number on a string, but place each op (including brackets) on a stack. When you hit an operator of greater precedence than that at the top of the stack, pop the op onto he string. The details are a little fuzzy, I'll try and be more exact in a while,

Got lecture now...
GF

dsmith · #5 29-Jan-2004, 08:03

Wow! Looks like fun.

This can definitely be done, but it is not simple. If you have enough time to put into this though, it can be quite neat.

To get the input from the user, I would use something like:

CPP / C++ / C Code:

printf("y = ");
fgets(input,MAXSIZE,stdin);

Thats the easy part. Now, I would parse this string to seperate out all of the items so that it can be computed easier in your program. (I am assuming that you are looping through values of x and that you will want to compute this on several values of x).

This is where the RPN (reverse polish notation) comes into play. If you have ever used an HP scientific calculator, you have used RPN. In this case though, I think reverse RPN (PN

) would be easiest. This will eliminate parenthesis and make it so you can set up a iterative processing loop. The syntax for this should be "+ 3 2" instead of "3+2"
So your input of this:

"y = -12*x^3 + 14.78*x^2 - 71.5*x + sin(2x) / 50"
needs to be put in a list like this:

Code:

+ - + * -12 p x 3 * 14.78 p x 2 * 71.5 x / s * 2 x 50

Thats terrible to read by the human eye, but makes your processing loop much easier.

Then by iteration your processing function would go threw this something like:

CPP / C++ / C Code:

double calc(formula* position, double x)
{
     double var1;
     double var2;
     if(position->type == 2_FUNCTION){
           var1 = calc ( position + 1, x );
           var2 = calc ( marker, x );
           switch(position->function){
                 case '+':
                        return var1 + var2;
                        break;
                 case '-':
                        return var1 - var2;
                        break;
                  case 'p':
                        return pow10(var1, var2);
                        break;
                   ....
             }
      }
      else if(position->type = 1_FUNCTION){
            var1 =  calc( postion + 1, x);
             switch(position->function){
                  case 's':
                        return sin(var1);
                        break;
                  case 'c':
                         return cos(var1);
                         break;
                  ....
              }
      }
     else if (position->type == VAR)
            return x;
     else if (position->type == NUMBER)
            return (position->number);
}

I don' know if you want to put this much effort into it or not. If you do, I would write this slowly using simple input and verifying the output is correct in each case, ie make sure that if you enter 3+2, you get 5. Then make sure that if you enter 3+2+1, you get 6.

The worst part of this whole thing (IMO) is taking the string input and reducing it to the PN format. The processing function is complicated, but should be able to be written in close to the format that I have. Anyway, let me know what you decide. If you do write this, please post and tell us about it. Also, if you don't mind sharing, please post your code.

flowercamel · #6 29-Jan-2004, 09:44

At first, I want to thank for your advice.

Well, i'm quite serious about this because it's gonna be part of a A-level thesis.

I understand how RPN works, but as you already mentioned, the big problem is transforming the string into RPN format.

Why do you prefer the reverse RPN format?
I'm gonna think about this

Greets

dsmith · #7 29-Jan-2004, 14:08

Quote:

Originally Posted by flowercamel

Why do you prefer the reverse RPN format?

Greets

Just for terminology sakes I looked this up. A better name for this is prefix notation. And it is called Polish Notation, which was a total swag on my part

The reason that I like the prefix notation for the C language routines is from past experience and what seems like the simplest for me to program. I wrote a low level database library and when it came to queries, I wanted to do complex queries in the easiest way possible. I found that by sending the query statements in prefix format, I was able to do complex queries with minimal code that didn't have to do a lot of processing. If you would like to see this sample, I can send you the functions that do this.

If you used algebraic format, you would have to parse the string anyways and then your process would have to do a lot of extra evaluation becuase you would have to keep track of paranthesis and such. I think your program would run much quicker (and be simpler in the long run), if you spent more time doing the parsing (which should only occur one time) and less time doing the calculations (which may happen many times).

This is my 2 cents only. There are other people which may have better solutions (in fact I am sure of it

), so I hope that they will post as well...

flowercamel · #8 30-Jan-2004, 06:47

Hello,

I managed to code something that calculates RPN formated strings...
It's not too fine code but it works

CPP / C++ / C Code:

{
short i,varnr,chrpos;
double number[10],temp;
char numberchr[10][50];
AnsiString mstring;

mstring=Edit1->Text;
//read m string form an TextEdit

// exchange every x with 2.. (for example)
for (i=1;i<mstring.Length()+1;i++)
 {
 if (mstring[i] == 'x')
        mstring[i] = '2';
 }


for (i=10;i<11;i++)
 numberchr[i][0]='W';

// used to mark these arrays as not filled with numbers

chrpos=0;
// position in the numberchr array
varnr=1;
// number of current variable

for (i=1;i<mstring.Length()+1;i++)
// now go through the mathematical string
 {
          if (mstring[i] > 47 && mstring[i] < 58) 
             {
              numberchr[varnr][chrpos]=mstring[i];
              chrpos++;
              // save number in char array
             }

          if (mstring[i] == ' ')
             {
             // if symbol befor ' ' was a number then mark end of char array   
             //andconvert into short
             if (numberchr[varnr][0] != 'W')
             {
             numberchr[varnr][chrpos] = '\0';
             number[varnr]=StrToInt(numberchr[varnr]);
             chrpos=0;
             varnr++;
              }

   if (mstring[i] == '+')
         // if there is a +, add the last two stored numbers, delete the last     
         // and replace the second to last with the result
         { 
          temp=number[varnr-2]+number[varnr-1];
          varnr--;
          number[varnr-1]=temp;
          numberchr[varnr][0]='W';
          numberchr[varnr+1][0]='W';
     }

             if (mstring[i] == '^')
            {
            temp=pow(number[varnr-2],number[varnr-1]);
            varnr--;
            number[varnr-1]=temp;
            numberchr[varnr][0]='W';
            numberchr[varnr+1][0]='W';
            }


   if (mstring[i] == '/')
  {
  temp=number[varnr-2]/number[varnr-1];
  varnr--;
  number[varnr-1]=temp;

        numberchr[varnr][0]='W';
        numberchr[varnr+1][0]='W';
  }

   if (mstring[i] == '-')
  {
  temp=number[varnr-2]-number[varnr-1];
  varnr--;

  number[varnr-1]=temp;
  numberchr[varnr][0]='W';
  numberchr[varnr+1][0]='W';
  }

   if (mstring[i] == '*')
  {
  temp=number[varnr-2]*number[varnr-1];
  varnr--;

  number[varnr-1]=temp;
  numberchr[varnr][0]='W';
  numberchr[varnr+1][0]='W';
  }

  }

ShowMessage(number[1]);
// and that's the result

I tried this out and it works well with thinks like:
4 x 2 ^ / 7 + (which stands for 4/x^2 + 7)

7 x 3 ^ * 14 5 / + 1 x 2 ^ / -
(7x^3 + 14/5 - 1/x^2)

I fear you won't like this chaotic code

I admit that this whole thing must be possible much more simple...

But the main problem that remains is still converting the user entered mathematical string (like 7x^3 + 14/5 - 1/x^2) into RPN format (7 2 3 ^ * 14 5 / + 1 2 2 ^ / -)

Garth Farley, i read in one of your older posts that you once built a calculator program.
I would be very pleased to hear some further details :-)

Thanks alot
flowercamel

dsmith · #9 30-Jan-2004, 07:53

Hey flowercamel.

Don't feel that you have to write this using RPN or PN because I think it would be easier. I have used RPN calculators daily for the past 15 years and I can't even use an algebraic calculator anymore

.

Based on the way that you are trying to write this, maybe a straightforward algebraic method would work better for you. I think that you could somewhat adjust the code you have written to allow for parenthesis tracking and change the way that you get your variables.

Here is the way my mind is working on this. I may even code this because it could be handy in a lot of cases. First of all, I want to completely seperate my processing from my parsing. So I would make a structure like:

CPP / C++ / C Code:

struct entry{
    char type;
    double number;  //You could use a union to save space if needed.
    char func;
};

Where my types would be defined by:

CPP / C++ / C Code:

#define VALUE 0     //Constant Value
#define 1FUNC 1    //Single parameter function, ie sine, cosine, etc.
#define 2FUNC 2    //Double parameter function, ie +, -, etc.
#define VAR 3       //Variable value

Then the I would parse the string to format it and also error check it. Every time that I found something, I would add it to the list with a call to a custom routine like

CPP / C++ / C Code:

add_entry(list, entry)

and write the code in that function of where to insert it. Basically, what I would want to end up with is a list of entries (in prefix or postfix notation) where all the identification is done so I don't have to do that in my process loop.

I would use prefix notation because it fits so nicely into an iterative C loop. Then I would use the calc routine that I wrote above.

I guess what I am saying is don't worry about using postfix or prefix notation if it doesn't feel right or if it doesn't offer any advantages to the way you want to code.

Like I said, I may code a parser library based on the above, because it is handy to have. Once it is written, I could see a lot of applications for it.

Any way that you do it, good luck! It looks like a really great and challenging program.

tay · #10 04-Feb-2004, 13:55

actually the best way is using flowercamel way
the Polish Notation, this is 1 of the algorithms from data structure
it is using the stack format the store the data and pop it out

e.g
4*(2+3)-5

polish notation will
convert it to this form
>> 5 4 3 2+ * -

1st do the 3 2 + means : 3+2=5
>>5 4 5 * -
2nd do the 4 5 * means : 5*4=20
>>5 20 -
3rd do the 5 20 - means: 20-5=15

the final answer is 15

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Including Maps and strings??	maddie	C++ Forum	17	05-Jul-2004 06:25
[function] AutoLink (converts URLS into links inside a string)	JdS	PHP Code Library	0	26-Jan-2004 05:02
C++ Error that makes no sense!	ArcticTiger	C++ Forum	1	10-Nov-2003 07:14
storing a token pointer as a string	CoreLEx	C Programming Language	1	07-Oct-2003 11:33
string to double C++	calculus87	C++ Forum	2	18-Sep-2003 11:50