Storing complicated mathematical expressions

Question

I've been wondering about the best way to store mathematical expressions programmatically, including expressions with non-normal operations, such as infinite sums/products, set operations, vector/matrix operations, integrals/derivatives etc.

I am aware of using a tree structure for basic expressions, but does it still apply here? Using a string (like LaTeX) would probably not be optimal for evaluation, so how would this problem be solved?

Answer 1

A tree structure is good. It may be easier to you allow more than two children for each node.

An integral might have three nodes: top and bottom limits, and integrand. You might have a special type of node to indicate an infinite limit.

You might want special types of nodes for matrices. While you could represent them as a list of lists, it may prove easier to use a 2D array of nodes. There is a certain trade off the more special types of node you have the more complex the code.

Some CAS systems (Maple) use a Directed Acyclic Graph this allows common sub expressions to be represented more efficiently. There is a considerably increased complexity in this.

Answer 2

A tree structure still applies, but parse (expression) trees are just artifacts of the underlying entity, namely a context-free grammar designed to handle your expressions. Parse trees can be serialized and deserialized using your favorite traversal method.