# What are the interesting data structures to work with to manipulate mathematical expressions?

For learning purposes only, I would like to make a small, fairly basic computer algebra system (CAS) manipulating mathematical expressions, such as polynomials, logarithmic or trigonometric expressions. One of the key features of this style of project is the simplification of expressions. For example, we can ask to simplify $$4x²+20x+3xy+15y$$ into $$(4x+3y)(x+5)$$ or $$\log(e^{3x - 7})$$ into $$3x-7$$.

A CAS interfaces with the user via a small language and the input is then parsed into an AST. For example, 3*x - 1 might correspond to the following AST: Sub(Mul(Int 3, Var x), Int 1). This AST step is the simplest step for me, my question is about manipulating expressions via this style of tree. The example I showed above on the simplification of $$\log(e^{3x - 7})$$ is a case of simplification that I would call "simple", it is indeed enough to apply a series of rewriting rules on the AST (with pattern matching for example):

let rec simplify expr =
match expr with
| Log (Power (Constant E, x)) -> simplify x
| ...
| _ -> expr


The other example I gave, however, cannot be solved with pattern matching (at least not as directly, I think), because we don't indeed recognise any pattern, we manipulate the expression to transform it.

My question then is how to apply this style of transformation on a tree (the method I used for the example is grouping) and I wonder what kind of data structure could be used to handle this in a way that is perhaps more suitable as I showed by grouping the terms (there is not only one simplification technique, but I remain focused on the question), as manipulating a tree to apply a grouping algorithm seems quite complicated (or I just don't know the algorithms for that structure, in which case I'm interested too). My first idea was simply to turn the tree into a list of terms of the form $$Ax^b$$ (a monomial), but I don't know if this is useful or not.

So the question is: how to represent an expression to apply simplification algorithms, like the grouping method, on it? Is an AST sufficient? If so, how should it be handled for the style of simplification method I have outlined?

PS: I don't think this question is a duplicate of this and this one, the posts in question are more about building an AST as well as equation solving algorithms, whereas I'm more about what data structure (other than AST, perhaps) to use.

PPS: I'm not especially looking for efficiency (since it's only for learning).

• For factoring, one of the rules I use to determine when to stop for a branch is to check for prime numbers. Jan 31, 2022 at 11:57
• I asked the Calculus question to get an idea of how you think. Since you took it to heart I will give you a hint. The definition I try to use for calculus is that it is a term reduction system that leads to a normal form (in Math they like to use the word canonical form at times). When there are no more rules or reductions that can be applied you have your answer. If given a well formed formula and a proper set of rules the result should be a non-reducible normal form. Jan 31, 2022 at 12:05
• Okay, I see. As I'm a beginner in this field, I was focusing on the technical aspect first (so, how to represent the objects). I'll have a look at it all!
– Foxy
Jan 31, 2022 at 12:33
• Before I forget and to be clear on this point. IIRC factoring does not have normal form or canonical form. On the other hand simplification will have a normal for or canonical form. One can go nuts looking for a normal form or canonical form for factoring if it does not exist and thus one of the early comments. Good luck. Also when you feel confident you should answer you own question here so that others can learn from it. Jan 31, 2022 at 12:42
• Just as an addendum: cs.stackexchange.com/q/134858 Feb 1, 2022 at 4:55