1. RE: simplify math expression
> -----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
2. RE: simplify math expression
> -----Original Message-----
> From: Matthew Lewis [mailto:matthewwalkerlewis at YAHOO.COM]
Oops! There should be some {} around the &= (or use append)
> expr[ix] &= expr[ix][1][ARG1]
> expr[ix] &= expr[ix][2][ARG2]
should be
expr[ix] &= {expr[ix][1][ARG1]}
expr[ix] &= {expr[ix][2][ARG2]}
and
> expr[ix] &= expr[ix][1][ARG1]
> expr[ix] &= expr[ix][2][ARG2]
should be
expr[ix] &= {expr[ix][1][ARG1]}
expr[ix] &= {expr[ix][2][ARG2]}
Matt Lewis
3. RE: simplify math expression
- Posted by a.tammer at hetnet.nl
Jun 11, 2002
Hi Matthew,
maybe we could cooperate on nimplementing your libs and my=
ICD.lib
could turn into quite a powerful tool I guess
a@t, antoine
4. RE: simplify math expression
> -----Original Message-----
> From: a.tammer at hetnet.nl [mailto:a.tammer at hetnet.nl]
> maybe we could cooperate on nimplementing your libs and my ICD.lib
> could turn into quite a powerful tool I guess
It's pretty easy to add new stuff to the lib with an include file. In fact,
booleval.e is an add on I wrote. You don't have to have booleval.e to run
matheval.
If you want to add a new type of matheval sequence, you have to create the
funtion that handles it, a parse routine, a pretty print routine, and you
also need to initialize it. In order to parse it, you might have to fool
the parser using some notation like (otherwise, it would try to make 1e1000
into a constant, i.e., atom--KABOOM):
MAKEBIG("1e1000")
Then, for the parsing routine for MAKEBIG (really a function), you would
have to know to convert the token to your right (should be {DATA,"1e1000"} )
into a BIGNUM. My notation for the parsing routines is to prefix the
routine with a 'C', for Collapse, because that's actually what it does. The
parser scans the input and tokenizes everything, and then, based on
precedence rules (specified in the initialization), the 'Collapse' routine
sucks up the tokens around it (based on whether it's binary or left/right
unary).
You would also have to use add_to_func(). This would allow the builtin
operators to use your new stuff. For instance, ADD doesn't know how to add
BIGNUM's. So you would write a routine that handles all the cases of adding
BIGNUM's (BIGNUM+BIGNUM,BIGNUM+CONSTANT, etc).
I don't think you'd be able to have constant operations automatically
promote to BIGNUM's, but then you probably shouldn't be using constants if
you think you might create a BIGNUM. You could always use MAKEBIG to
promote manually like if you had a variable or some other result that you
knew was a constant (since it would be faster to calculate as a constant).
If you're interested, I could help you with any questions. I'd definitely
recommend reading the docs before you start. They give you an idea of how
some of the guts of the lib work.
Matt Lewis
