OpenEuphoria

RE: simplify math expression

• Posted by Matthew Lewis <matthewwalkerlewis at YAHOO.COM> Jun 11, 2002
• 448 views

> -----Original Message-----
> From: tone.skoda at gmx.net [mailto:tone.skoda at gmx.net]

> some math expert will sure know how to do this.
> 
> simplify math expression so that you remove all braces and 
> put arguments in
> alphabetical order. no calculation, just "pretty print".
> 
> examples:
> 
> b+(c+(a+d))   --> a+b+c+d
> c+((d+b)+a)   --> a+b+c+d
> (b*a)/c           --> a*b/c
> a/(b/c)            --> a*c/b
> b*(c+a)          --> a*b+a*c
> 
> i guess removing all braces and puting arguments in 
> alphabetical order is
> not so important,
> but important is that these two expressions get simplified to 
> same result:
> b+(c+(a+d))   --> a+b+c+d
> c+((d+b)+a)   --> a+b+c+d
> 
> tough cookie huh?
> speed is also important
> i didn't find this feature in any math evaluator library in 
> euphoria archive
> or on the net. if you know some c source code for this that 
> would also be
> okay, i'll just make dll out of it.

My current matheval lib makes a start at this.  I haven't updated the lib
proper, but and updated version is included in EuSQL on my page:

http://www14.brinkster.com/matthewlewis/projects.html

The relevant files are 
* matheval.e :  Main matheval lib file
* symeval.e  :  Symbolic/algebraic simplification
* parseval.e :  Parses mathematical/logical expressions
* booleval.e :  Evaluates boolean expressions
* ppeval.e   :  Formats matheval sequences for display
* misceval.e :  Used by matheval.e

There's not much documentation there, but if you d/l the matheval from the
page, you can get some old docs that explain how some stuff works.  One of
my long term goals of the project was to be able to do some fairly serious
symbolic calculations, which requires some pattern matching capability.
Basically, each expression is a recursive sequence:

sorta-pseudocode: a+b+c = {ADD,A,{ADD,B,C}} or {ADD,{ADD,A,B},C} etc

In symeval, you'll see some code that simplifies expressions.  You might be
interested in ExpandAddition().  This function will take the above addition
example, and return {A,B,C}.  You could always sort these, and then use
CompactExpr() to get back to a real matheval expression.  Scanning the file,
I don't see that it would know what to do about 
a/(b/c)            --> a*c/b
although it could probably be made to do so.  This could probably be done in
ExpandMult():

function ExpandMult( sequence expr )
    integer ix, jx
    atom exp
    sequence term, bits
    ix = 1
    
    if matheval_seq( expr ) then
        expr = { expr }
    end if
    
    while ix <= length(expr) do
        if expr[ix][FUNC] = MULTIPLY then 
            expr[ix] = { expr[ix][ARG1], expr[ix][ARG2] } 
            for i = 1 to 2 do
                term = ExpandMult( expr[ix][i] )
                expr[ix] &= term
            end for

--- start adding code here ---
        elsif expr[ix][FUNC] = DIVIDE then
            expr[ix] = { expr[ix][ARG1], expr[ix][ARG2] } 
            if expr[ix][2][FUNC] = DIVIDE then
                if expr[ix][1][FUNC] = DIVIDE then
                    -- (a/b)/(c/d) => (ad)/(bc)
                    expr[ix] &= expr[ix][1][ARG1]
                    expr[ix] &= expr[ix][2][ARG2]
                    expr[ix] &= {{EXPONENT,{MULTIPLY,expr[ix][1][ARG2],
                       expr[ix][2][ARG1]},{CONSTANT,{-1},{}}}}
                else
                    -- a/(b/c) => (ac)/b
                    expr[ix] &= expr[ix][1][ARG1]
                    expr[ix] &= expr[ix][2][ARG2]
                    expr[ix] &=
{{EXPONENT,expr[ix][2][ARG1],{CONSTANT,{-1},{}}}}      
                end if
            end if

Then...

function MultiplyOut( sequence expr )
    integer func, ix, jx
    sequence rest, temprest, bits, term,
       divide -- add this
    object exp
...
    ix = find(ONE, expr )
    while ix do
        expr = RemoveOne(expr, ix)
        ix = find(ONE, expr )
    end while

--- add code here ---
    divide = {}
    ix = 1
    while ix <= length(expr) do
        if expr[ix][FUNC] = EXPONENT and expr[ix][ARG2][FUNC] = CONSTANT
        and expr[ix][ARG2][ARG1] < 0 then
        -- find all negative exponents and separate them out
            expr[ix][ARG2][ARG1] *= -1
            divide = append(divide,expr[ix])
            expr = RemoveOne(expr, ix)
        else
            ix += 1
        end if
    end while
--- stop adding here ---

    expr = CompactExpr( expr, MULTIPLY )

--- add code here ---
    if length( divide ) then
        divide = CompactExpr( MultiplyOut( divide ), MULTIPLY )
        expr = {DIVIDE, expr, divide}
    end if
-- stop adding here---
    return expr
end function

That should put everything that belongs on the bottom of the division.  I
haven't fully tested this, and its been a while since I've messed around in
symeval, but that should do the trick for you.  If you do the sort on
ExpandMult() and ExpandAdd(), it should handle all the cases you've listed.

NB: The main point of the code was to figure out if things could be put into
polynomials, because these are highly optimized [in the lib] versus a long
chain of addition, multiplication and exponentiation that otherwise makes a
polynomial.

In ppeval.e, you could change the routines easily enough to not output ()'s
around everything.

You can download the actual lib to get some documentation that's still
pretty accurate.  The only thing that's changed (besides more functionality)
is the modularity of the lib.  Also, the demo that's up there is pretty cool
IMHO. :)  It's sorta like a graphing calculator program.  You can enter in
expressions, variables and equations and then evaluate and graph them.

Matt Lewis