Sign in to follow this  

Expression simplification

This topic is 3865 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a math expression, given in a string (e.g. "x*x/(x-1)+2") that is a function of x and maybe other variables. I want to write a program that simplifies it, for example convert 1*(x-1*0)/x to 1.

Share this post


Link to post
Share on other sites
Well, I'm assuming there's two questions here; at least there's two things you need to consider.

#1: What steps do you take to simplify an expression?

#2: How do you know when to stop?

I suppose #2 is really irrelevant for algebraic expressions... for the most part - but #1 is not so bad.

This should work like a calculator; the first step is evaluating all of your constants. Handle things in order of operations. In your second example, 1*0 would be evaluated first; leaving it with 1. That's the only constant expression you have, so it's time to clean up givens; strip out every multiplication or exponent of 1 or addition or exponent of 0. Process any multiplications by 0; complain about any divisions by 0.

Where do you want to take this? Do you want to end with a polynomial expression? Do you want all the factors laid out?

From there I would treat divisions as negative exponents; by this point your expression becomes x^1 * x^-1; you should be able to evaluate this as x^(1-1)=x^0. If you run through the process from the start at every step, then you should already have the groundwork to determine this is equal to 1. Running through it again should leave the string unchanged, so you're done.

For the first example, you have x*x/(x-1)+2. Running through the process:

(1) Evaluate constant expressions
There are constants, but no expressions; string unchanged
(2) Turn divisions into negative exponents
String becomes x*x*(x-1)^-1 + 2
(3) Evaluate variable expressions
x*x becomes x^2; string becomes x^2 * (x-1)^-1 + 2
It's done.

How do you simplify expressions by hand? Finding examples and working through them will help reveal this process.

See a nice breakdown of the steps at:

http://www.teacherschoice.com.au/Maths_Library/Algebra/Alg_7.htm

Share this post


Link to post
Share on other sites
In terms of how you'd actually do this programatically, the first step is to get a tree representation of your expression (you'd do this using a parser). Then apply transformations to that tree to simplfy the expression. Then finally print out the tree as an expression.

So for your example expression you'd get a tree that looks something like this:

div

/ \

/ \

* x

/ \

/ \

1 -

/ \

/ \

x *

/ \

/ \

1 0



You could then have a function simplify that you call on the root node of the tree (div, I didn't use / to avoid it getting mixed up with the tree branches). This function would look at the type of the node and perform appropriate actions. So calling it on div would check for various simplifying conditions, e.g. if you had some expression in the left branch and the right branch was 1 then it would just simplify to the left branch. Before applying these rules it could try simplfying the left and right branches, so in the case above simplifying the left hand branch would give x, and simplifying the right hand branch would give x. There'd then be a rule for div nodes that says if you have the same left and right hand branches simplify to 1.

You'd then have similar rules for other node types, e.g. when you try to simplify the left branch of div you'd be simplifying a * node, that'd have rules like if the left and right hand branches are both constants then evaluate left * right and simplify to that answer, or if either left hand branch or right hand branch of the node are 0, simplify to 0 etc.

Share this post


Link to post
Share on other sites
Thanx for the methods, I will try to implement the one with negative exponents. The problem is, if I have a list of factors (with powers), do I check every pair of them (whatever, I do not care about speed too much) for equality?

I've already implemented a procedure that breaks down the string into objects (like expression, term, factor), but now I realize I don't have to make separate objects for +/-, */div, .., it just replicated the recursive process of parsing expressions. The recursive tree method is way simpler to work with, now I come to think of it. I also have a process that eliminates expressions independent of the argument. Basically I want to be able to differentiate expressions symbolically, but I don't want to get d(x*x/x)/dx = ((1*x+1*x)*x-1*(x*x))/x/x.

There's also a question about efficient 2D equation solving. You get an expression with x and y parameters (e.g. "x^2+y^2-9"=0) and have to draw it. I broke down the window into 16x16 rectangles and check a few points in it for sign. If it varies, I check every pixel of the rectangle and draw them if the sign changes in them (first in xy order, then in yx order). It works, but it does take considerable time do draw every frame (so if I try do drag the picture it gives out something like 1 fps). Is there a more efficient method for doing this?

And, there's a part about factorizing expressions in numerator/denominator that might be simplified. What is the simplest way to factorize expressions for this? By the way, the expressions may also consist of sines/cosines/other functions as well.

[Edited by - ReaVeR-Andrey on May 20, 2007 11:33:52 AM]

Share this post


Link to post
Share on other sites

This topic is 3865 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this