Design question.

This is a discussion on Design question. within the C++ Programming forums, part of the General Programming Boards category; I'm trying to build a library that can simplify mathematical expressions. I have an ExpressionPrt type, that is the base ...

  1. #1
    Registered User
    Join Date
    Apr 2006
    Posts
    2,035

    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.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    Does the library simplify mathematical expressions at compile-time or run-time?
    I wasn't quite sure which you were tackling.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Apr 2006
    Posts
    2,035
    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.
    Last edited by King Mir; 05-14-2008 at 01:41 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Apr 2006
    Posts
    2,035
    Quote Originally Posted by matsp View Post
    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.
    Last edited by King Mir; 05-14-2008 at 03:36 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

  6. #6
    Registered User
    Join Date
    Apr 2006
    Posts
    2,035
    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.
    Last edited by King Mir; 05-30-2008 at 12:08 PM.
    It is too clear and so it is hard to see.
    A dunce once searched for fire with a lighted lantern.
    Had he known what fire was,
    He could have cooked his rice much sooner.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Game design question
    By h3ro in forum Game Programming
    Replies: 6
    Last Post: 02-28-2008, 07:20 AM
  2. Question about engine design.
    By Shamino in forum Game Programming
    Replies: 9
    Last Post: 01-29-2008, 09:53 AM
  3. question about class design and overloading
    By l2u in forum C++ Programming
    Replies: 7
    Last Post: 12-13-2007, 01:02 PM
  4. database app design question
    By MPSoutine in forum Windows Programming
    Replies: 4
    Last Post: 12-02-2003, 09:13 PM
  5. design question: opinion
    By ggs in forum C Programming
    Replies: 2
    Last Post: 01-29-2003, 10:59 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21