Printable View
hi
what should we do if we take a math function from input like "sin(2x+1)/tan(x^2) " and we want to find the derivative of the functionand the value of the function for a special x (ex. x=2) ....
(we might have sin,cos,tan,cotn,exp,ln,log in the input .and we only have one variable)
i have no idea for solving this problem.:(
finding the value is very straightforward. simply evaluate the given function.
here's how i would evaluate the derivative.
http://en.wikipedia.org/wiki/Finite_difference
I had to solve a similar problem in college for a class project. It involved user input of an arbitrary function and solving for the derivative of that function (it did not involve solving the function for a given value). What I did to solve the problem was to implement a couple stacks and a tree structure. The stacks stored operations (sin,cos,+,-,*,/,^,etc.) and values (2,x,etc.). As the input equation was read, values/operations were pushed onto the relevant stacks and also popped from the stacks and used to build an expression tree. This tree could later be used to easily figure out the derivative by building a second tree from the original. NOTE: I make no claim that the following is the best solution for you, only that it is the one I implemented.
Consider the function 3*x^2+1 (derivative is 6x). You need to read through the expression and parse it out for values and operators. First item is the value 3 so push it onto the value stack. Next is the multiplication (*) operator so push it onto the operator stack. Next is the value x, and the exponent (^) operator, and the value 2 so push them onto their appropriate stacks and we should have the following:
Now we read/parse the plus (+) operator but we don't push it because when pushing operators you only push as long as what you are about to push has an equal or greater operator precedence as what's already on the top of the stack. + is lower is precedence than the exponent operator (^) at the top so we have to start building the tree at this point by popping off values/operators. First up is the exponent obviously and the values 2 and x so we pop all of those off their respective stacks and build the tree as follows:Code:Val Stack Oper Stack
--------- ----------
2
X ^
3 *
Which represents the expression x^2 and leaves our stacks as follows:Code:^
/ \
x 2
Since the addition (+) operator is still of lower precedence than the multiplication (*) operator. We need to do some more popping, this time we only have a single value instead of two and of course the multiplication operator which we add to the expression tree:Code:Val Stack Oper Stack
--------- ----------
3 *
This represents the expression 3*x^2 and leaves both our stacks empty. We can now push the addition operator onto the operator stack and also the last value (1) that we read from the user.Code:*
/ \
3 ^
/ \
x 2
Since we are at the end of the users expression, we can pop these last values off the stack and we arrive at the following tree:Code:Val Stack Oper Stack
--------- ----------
1 +
Now we have our arbitrary users function stored as a tree and we can do the derivative. To do this we start at the top of the tree and apply our rules of finding the derivatives of functions, such as the derivative of a function (A + B) is the derivative of A + the derivative of B, and also the derivative of a function (A^B) is B*A^(B-1). At the top of our tree we have the addition operator so our differentiated tree will also begin with the addition operator:Code:+
/ \
1 *
/ \
3 ^
/ \
x 2
We can recursively apply our solver code to then calculate the derivatives for each branch left/right of the original expression tree. The left branch is the constant value 1 which the derivative of is 0. The right branch is the the subtree:Code:+
So our solution tree stands at:Code:*
/ \
3 ^
/ \
x 2
The rest of this subtree consists of the multiplication operator at the top so the product rule for derivatives must be used which is - the derivative of a function (A*B) is A'*B + A*B'. In our case, 3 is A and the subtree X^2 is B, which at this stage we can add to our solution tree as:Code:+
/ \
0 "Rest of the above subtree"
The rest of the subtree X^2 uses one of the above rules - the derivative of A^B is B*A^(B-1). This leaves us with a solution tree of:Code:+
/ \
0 +
/ \
* *
/ \ / \
0 ^ 3 "The rest of the subtree (X^2)"
/ \
X 2
This tree represents the expression 0 + 0 * x^2 + 3 * 2 * X^1 and can be simplified by some further processing of the tree to get a final solution tree of:Code:+
/ \
0 +
/ \
* *
/ \ / \
0 ^ 3 *
/ \ / \
X 2 2 ^
/ \
X 1
Which represents our solution mentioned above of 6*X. It should now be a simple matter of substituting your X value and arriving at the desired outcome. How you choose to use this information is up to you.Code:*
/ \
6 X
Phew... you have no idea how long that took.
oh, i misunderstood! you need to evaluate a function entered by the user. that is rather a bit different!
thanks for your answer.
i would think about it and i'll come back with more specific questions.;)
hk_mp5kpdw do u have any contact information any email ,i would like to ask you somethings !
It certainly is different, but it has definitely been done before. The tree-method of a math-function (like the one posted byQuote:
oh, i misunderstood! you need to evaluate a function entered by the user. that is rather a bit different!
hk_mp5kpdw) is a very effective form of prefix notation (+ 2 2 with the operator before the operands). Usually, math equations
are commonly written in infix notation (2+2 has the operator between the operands). I'm sure one can write an algorithm
for parsing the infix equation and converting it into a prefix notation.
Infix Notation
Prefix Notation
You may create a thread on the board. That way, everyone can benefit from the knowledge of the answer to your question.Quote:
Originally Posted by darentuzi
Please don't bring up old threads. If an old thread contains important information you wish to include in your question, add a link to the new thread you create.