Just wanted to point out a few things I think you missed in your CAS topic, on the off chance you don't know about them. The standard (and easiest) way to parse mathematical expressions is actually to work in Reverse polish notation. A lot of CASes convert to RPN before evaluation, so here's a simple algorithm for it (basically the Shunting-yard algorithm).

Given: (2x+5)(x+4)(5x+6)^5

->(2*x+5)*(x+4)((5*x+6)^5)

Using the shunting yard algorithm, we can convert this to RPN:


(2*x+5)-> 2 X * 5 +

(x+4)-> X 4 +

((5*x+6)^5)-> 5 X * 6 + 5 ^


Combining these into one expression, we get*:

 2 X * 5 + X 4 + 5 X * 6 + 5 ^ * *

Recognize that it's essential for a CAS to have an X^n operation. Rather than expanding the expression using pascal's triangle (which would be incredibly tedious/slow for a 9001th degree equation), you can use x^n for numerical evaluation since the expression is constant for each value of the variables. Plug the values in and watch it go. For symbolic operations, you can just apply the normal power laws.

From this messy RPN equation, we can actually get something incredibly useful for a CAS, namely a beautiful syntax tree:

Code: [Select]

              Ans
       |
       *
    /   \
   +       *
  / \     /  \
*   5   +    ^
/ \     / \   / \
2  X   X   4 5   +
        / \
      6   *
         / \
        X  5
Now we have a simple way to evaluate the expression in terms of a few elementary operations. You just need to traverse the tree and evaluate the values at each node. The answer then comes right out. It also allows you to do certain optimizations to the expression, such as evaluating constant values such as 2*3 in the equation (2*3)+X, which would show up as a node with constant arguments. A little pruning of the syntax tree and you get a nice simplified expression.

Anyway, just thought I'd mention it 


*Might be wrong. I don't use RPN very often

Wow.... I honestly did not know that!
Now I know why programming classes LOVE to talk about trees...
The basis of my CAS theory is basically asking a computer to do the same thing we do when solving a problem. (I would be actually pleasantly surprised for the FPM!) Of course, humans may not be as

Somehow, someway, the RPN notation makes things a lot faster (and of course, much more efficient then nCr, in which I found out that the calc slows and stops at 36 (ERR:OVR), and my laptop, although "modern", takes quite a while to compute that. (451.583050966 seconds => 7.53 minutes!)

I think I get your idea/theorem... and then again, maybe not!
The tree somewhat deviates from the RPN converted equations you posted, and I'm not too sure how I would handle such input.

Either way, the theorem you mentioned is interesting indeed, and I could use all the help I can get!

Thanks!
Albert

P.S - do you mind if I post your PM in the topic? It might be somewhat useful for people to know.

I have absolutely no problem with you posting it.

About the tree deviating slightly, well that's because I'm not very good at RPN

Basically, what RPN does is convert the expression into a series of individual operations on the operands in the order they're supposed to occur. What the tree does is group them in such a way that every operations is linked to its operands. The operations are the nodes and the operands are the leaves. You start from the bottom (or top down, they both work) with all of the given constants and variables listed. Then, you connect all of the operands with their operations. Those operations produce new operands which are then operated on by some of the leftover initial operands and so on until you end up with one final operand that is your answer. That's also essentially how you generate trees in code. If you want to start from the top, you just assume an answer, then find the operations that produce that answer, the operands for those operations, and then the operations that produce those operands, etc...


On a side note, Dynamic trees are useful, but they're a serious PITA to organize in memory. I've had nightmares about the internal representations