Thread: finding the value and derivative of a math function

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:

Code:

Val Stack Oper Stack
--------- ----------
2
X         ^
3         *

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:

  ^
 / \
x   2

Which represents the expression x^2 and leaves our stacks as follows:

Code:

Val Stack Oper Stack
--------- ----------
3         *

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:

  *
 / \
3   ^
   / \
  x   2

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:

Val Stack Oper Stack
--------- ----------
1         +

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:

  +
 / \
1   *
   / \
  3   ^
     / \
    x   2

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:

+

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:

  *
 / \
3   ^
   / \
  x   2

So our solution tree stands at:

Code:

  +
 / \
0  "Rest of the above subtree"

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     +
    /   \
   *     *
  / \    / \
 0   ^  3  "The rest of the subtree (X^2)"
    / \
   X  2

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   *
    / \    /  \
   X  2   2    ^
              / \
             X   1

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:

  *
 /  \
6   X

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.

Phew... you have no idea how long that took.

Originally Posted by darentuzi

hk_mp5kpdw do u have any contact information any email ,i would like to ask you somethings !

You may create a thread on the board. That way, everyone can benefit from the knowledge of the answer to your question.

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.