Thread: Design question.

I'm trying to build a library that can simplify mathematical expressions. I have an ExpressionPrt type, that is the base for all the different parts of an expression. Different expression parts include Constant, Variable, and Add (addition operator/function). Theses three are probably the most common, so they serve more as warning of future problems rather than problems themselves. But ultimately I want to have more complicated operations such as exponentiation and possibly derivation.

The problem is how to build a dependency tree so that the user of this template library does not have to include the whole thing.
In the case of addition, Add can simplify and organize statements contained in addition expressions, in order. So it can simplify y+3+x+7 to 3+7+x+y. It can identify that 3 and 7 are potentially addable (cause they are both constants). But in order to add the two numbers I need a component that knows about both the concepts of addition and of constants. How can I have such a component, without forcing the user to include all addable expression parts whenever he wants to add, and without forcing the user to include the operations that can be preformed on a constant whenever he wants to use constants. Similarly, how do I ensure that a default addition operation exists for those expression parts that cannot be added (that being to not simplify).

My present solution is to just dump all functions that need to know about more than 1 expression part/concept into the base ExpressionPrt class. Obviously this is a bad solution because a)Adding more expression parts requires me to modify the ExpressionPrt class, and b) the default behavior for such operations often requires me to include the associated operation before ExpressionPrt, thus effectively forcing the user to include the entire library in each file that uses any small part.

Help me find a better solution.

Does the library simplify mathematical expressions at compile-time or run-time?
I wasn't quite sure which you were tackling.

Run time. But it parses them as part of the source, so you could write an expression in C++, tell it to print and it would print what you wrote in math symbols. Then you could tell it to simplify and print the new result.

You need to (obviously) parse the expression into an internal form (such as a binary tree). Each operand node could then be classified as a constant or variable term.

You obviously also should cope with (x + y) * (x - y), so that you get x*x + x*y + x * -y + y * -y -> x*x + y * -y, since x*y + x * -y will eliminate each other.

--
Mats

Originally Posted by matsp

You need to (obviously) parse the expression into an internal form (such as a binary tree). Each operand node could then be classified as a constant or variable term.

Obviously, though it's not as simple as a binary tree since each node can have 0, 1, or 2 branches. ExpressionPrt is an abstract base for such nodes.

You obviously also should cope with (x + y) * (x - y), so that you get x*x + x*y + x * -y + y * -y -> x*x + y * -y, since x*y + x * -y will eliminate each other.

Solving (x + y) * (x - y) is just x (x +(-y))+y (x +(- y)), then x*x +x*(-y)+x*y+y*(- y). This is then* sorted in an order determined by mathematical order, polynomial degree, alphabetical order of variables, and possibly other factors. That results in x*(-y) and x*(y) to be recognized as addable. The final result is x*x+y*(-y), or similar.

*The algorithm is recursive, so unlike a human, it will not try to do two steps in different parts of the expression at once. Therefore the steps I am showing do not represent the true sequence of events.

But here you start with multiplication and addition, so there is no problem using both, since they are both included anyway. With an expression like (x*5*y*x/42) there is no need to include addition. It's not involved in the simplification process.

For the interested, I have found a partial solution to the problem. This Solution solves the problem of having to include unused headers in a program, but adds the requirement that all source file including parts of this library must include the same headers (otherwise the behavior is undefined). Unfortunately I cannot think of a way of forcing an error in the undefined case. The solution does have the advantage of separating concepts in the headers themselves.

The solution is as follows:

The Expression class (which is a template class) has a static Simplifier member object. The Simplifier class has 12 (for now) static functor (function object) pointers, for each default action. These numbered and macro is used to write the repetitive code. These functor pointers will thus have names like "defaultFunctor07". Each number maps to a possible operation that can be done on expressions, such as addition. Taking advantage of the default zero initialization of static variables, most of these will be null. However other included header files can initialize these functor pointers. For example the header that includes the ExpressionPrt responsible for addition, may initialize the c.

The simplifier when asked to simplify an expression must be passed the expression to simplify, and the numeric id for the operation (the expression can store it's functor ID). The simplifier can than use the id to look up which function to call. This is done with a big switch statement (which is condensed with the use of macros).

Similarly special case functors (like the addition of two Constants) can are stored in the Simplifier. The definition and use of these is similar except that each of the 12 operation there 12 more special cases. Each of the non null special case functions is tried until one returns a non null result. If none of them do so the default functor is used. The short circuit evaluation of the || operator is used to terminate the sequence of function calls when a non null value is found.

In all cases, the number 12 is hard coded. There is no way around this.

I'm still looking for something better, but because the expressions are a template class that can use any numeric type, there don't seem to be many options.