Constructing a data structure for a computer algebra system

In thinking about how to approach this problem I think several things will be required, some tivial:

1. 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.
2. 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).
3. 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?

Clarification: The tree will need to support three different compound operations.

1. Creation: (from a string, but how to actually do that is beyond the scope of this question)
2. 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.
3. 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).

• Are you looking for algorithms to construct such a tree or to modify an existing one? What types of operations will you be doing on the tree exactly, e.g. search, replace, insert... ? – Pedro May 30 '12 at 21:04
• @Pedro, updated with clarifications – soandos May 30 '12 at 21:12
• @soandos: A couple of questions. What if your node(object) is a complex number? What if your object is not even a number? e.g. how do you compute the intersection of two sets of which the elements are not numbers but sets of numbers? – scaaahu May 31 '12 at 3:10
• @scaaahu, The numbers will contain some object. That object could be a boxed value type though. Not really concerned at this point with computing anything though. Just to compute equality is not a problem though, overload .equals (or whatever it is in a language) – soandos May 31 '12 at 4:38

From the comments OP wrote, I understand he wants to start small. However, we need to think more generally so that the to-be developped CAS can be of real use. Otherwise it is nothing but another calculator. Please see Definition of Computer Algebra System.

My suggestion:

Numbers, elements, sets, operations, etc. are fundermental in algebra. The data structures will have to be about them. In particular, you can start with elementary set theory. Determine what will be an element, a set, etc. The elements should be generic(they can be anything). Abstraction is the key. Then, what are the operations associated with them? Constructing a set, membership test, union, intersection, etc. Once we have them in place, plug in the number manipulation packages to the system is a matter of instantiation.

This looks like a classical application for Object-Oriented Programming (OOP), or more explicitly, Polymorphism.

You could create a basic object, e.g. treeObj with a method evaluate, and then generate sub-types for every object in your language, e.g. a plusOp object for the $+$ expression, the constructor of which takes two other treeObj as its left and right operands.

Every subclass of treeObj implements its own evaluate method which is called recursively on its operands. This is essentially Depth-First tree traversal.

Construction of such a tree from a string is usually done by converting the string into tokens, and then assembling the tree from the bottom up. For this you may want to have a look at LALR parsers, or, for more simple languages, a Recursive Descent parser.

Reduction is a bit trickier, as each node defines equivalence differently. Personally, I would handle this by making each treeObj provide a function isEqual, which compares it to another treeObj. Each different sub-type of treeObj could then implement its own commutativity, depending on the underlying mathematical properties of the operator.

In summary, a lot of Polymorphism and Recursion.

• Those are nice ideas, but I took them for granted, and besides the point really. I am not looking a programming style or paradigm pre-se, nor about parsers (though I will need that later). I am just asking for how to store the information. How to actually accomplish the operations is also beyond the scope of this question, they just need to be supported – soandos May 30 '12 at 21:39
• @soandos, you're asking how to store information. I'd like to point out that algebra is not just number manipulation. If what you're working on is a school project, you're probably fine. If you're trying to develop a real CAS, what you said in your question is far from it. You need to ask yourself a question, what's the difference between the calculator on your computer and the CAS you're designing? – scaaahu May 31 '12 at 4:12
• The primary difference is that it should be able to do algebra ($x+5=17$ for example) not that that is so special. – soandos May 31 '12 at 4:54
• Obviously we have difference in our defintion of CAS. I guess your defintion of algebra is high school algebra while my definition of algebra is abstract algebra. – scaaahu May 31 '12 at 5:06
• @scaaahu, Apologies, I wanted to start small. I thought it was implied in the operations that I gave as examples. – soandos May 31 '12 at 5:13

Take a look at Chapter 8 of Paradigms of Artificial Intelligence Programming - where the author Peter Norvig solves this problem in Common Lisp.

• Would you care to elaborate on "solves this problem"? If it were solved, should we tell MO? (Referring to mathoverflow.net/questions/11517) – scaaahu May 31 '12 at 12:06
• I meant that it provides an implementation for a data structure that the question asks for. (I'm not sure what question you're asking.) – hawkeye May 31 '12 at 23:02
• Maybe I misunderstood both you and the OP. CAS is a huge thing to me. See this page and that page – scaaahu Jun 1 '12 at 1:39
• Agree - it is huge. Thanks for those links - I wasn't aware of some of those. – hawkeye Jun 1 '12 at 11:09