# Question on Converting a String into an Algorithm / Equation

• 06-27-2010
GraceC1990
Question on Converting a String into an Algorithm / Equation
I am considering writing a personal program that uses Newton's Method to compute the second and third approximations of a root.

The formula is x2=x1-(f(x))/(f'(x))

I would like the prompt to be "Enter the equation/expression: "

I know how to program everything, except for how to turn a string of numbers and letters (user-defined variables) into an equation the program understands, to replace f(x) in my pre-defined formula.

Any suggestions?
• 06-27-2010
rodrigorules
maybe this will help

Expression Trees
• 06-27-2010
GraceC1990
Thank you for the link. I understand that I will have to program loops in a way that imitates the order of operations and search arrays. If anyone has any example code, that would be helpful.
• 06-28-2010
rodrigorules
If the only information the program has is f(x) and it needs f ' (x), the program will have to find the derivative itself .. the only way that I know of to do this is to use a better data structure to contain the equation, as I linked to (press next on the page to continue to code examples). I think its gonna be a bit more complicated than 'program loops'

(or look for numerical solutions to derivatives)

on the other hand there probably are libraries for handling expressions, handling derivatives, etc. But then again there probably are libraries which can do newtons method as well, which defeats the purpose of programming this (assuming your trying to learn c++)
• 06-28-2010
MacNilly
Since parsing general equations (as well as finding derivatives) is much more complicated than what the program actually does, I would suggest breaking the user input up like so:

enter f(x):
enter f'(x):

etc...

That saves a lot of parsing problems. As for parsing the expressions, by far the easiest way is to enter them in RPN (reverse polish notation). Another help is to have the terms of the expressions be whitespace separated. Then you can easily tokenize them.