In thinking about how to approach this problem I think several things will be required, some tivial:
- An expression tree where non-leaf node is an operation (not sure if that part is redundant), but not every node has just two children.
- All nodes for operations have a defined number of children that they must have (some operators are unary (like $!$) while others are binary ($*,+,-,$ etc) and still other are n-ary ($f(a,b,d)$ and versions with different amounts of variables).
- All leaf nodes are some type of number
I am under the impression that the tree should not explicitly retain information regarding the order of operations, but rather that information should be used in the parsing stage to insert things into the tree correctly.
This leads to the question, how should inserting to a specific position in the tree be done? Simply passing a list of directions (from root, take node zero, then node 1, etc, then insert) will work, but it seems overly clunky.
Or should I avoid that situation entirely (not talking about editing an equation here, just building a representation of one) by using the fact that in some sense the tree must be complete (all binary operations MUST have two children, etc, and even operators that are seemingly ambiguous (the $_{^-}$ sign for example) but these ambiguities are resolved before this point. That would all me to insert "in order"
Am I taking a reasonable approach? Does it make no sense whatsoever?
Additionally, are there papers or articles that I should read about CAS systems?
Clarification: The tree will need to support three different compound operations.
- Creation: (from a string, but how to actually do that is beyond the scope of this question)
- Reduction: (to some type of canonical form) so that if $a+b$ and $b+a$ are both entered and reduced, they will form identical trees.
- Evaluation: Be able to traverse the tree
These are all the operations that need to be supported. There are probably many other more basic operations that may need to be supported, but in this case it only matters that the three operations above are supported. My understanding is that search for example is not a property that will be required, but deletion will be (of a whole subtree).