Re: how to parse linear equations

[Hans Aberg]

On 16 Jan 2010, at 01:40, Michael Chen wrote:

> The input I have is linear equation like:
>
> 2 * x + ( x - y ) = x + 1
>
> And I would like to get at end
>
> 2 * x - y = 1
>
> I studied the calculator example, and be able to build ast tree.
> however  I have no way to reduce it. Please give me an example or
> link. Thanks.

You need methods used in symbolic programming (like Maple), theorem  
provers, and CLP like:
  http://en.wikipedia.org/wiki/CLP(R)
  http://en.wikipedia.org/wiki/Constraint_logic_programming

One can solve polynomial equations using Buchberger's Groebner Basis  
Algorithm. Given an ideal (p_1, ..., p_k) it produces a new set of  
generators relative a monomial order on diagonalized form. In the case  
of one variable, it reduces to the Euclidean algorithm computing the  
greatest common denominator. For a set of equations, just write them  
as p_1 = 0, ..., p_k = 0, and apply it to the ideal (p_1, ..., p_k).

If you want to just solve linear equations, you can use just the  
ordinary matrix solution method: write matrices A X = B, and solve it.  
- Check for computationally efficient methods doing this.

When doing it the CLP way, one integrates this algorithm into the  
unification process that i Prolog is used to unify the heads of the  
clauses. This produces a very elegant way to solve them, as you can  
see on that link above, but is somewhat limited if one wants to do  
more general things.

  Hans