2

For fun, I would like to design a mathematical expression evaluator, with variables. It could simplify the entered expressions by factoring them, reducing them to a sum of simple fractions, calculating them, grouping them, etc...

To give an example, if the user enters the following expression:

Example of expression

(in a code format, of course, not in Latex)

I wish my program could return the following simplification, which is the maximum simplification that can be made in this case:

Example of simplification

To achieve this result, you need a parser and an AST. My question concerns the handling of the AST. Indeed, the idea I have to get such an output is to browse the AST and operate on the different expressions via rewriting rules of the latter. Nevertheless, this approach seems to me really long and tedious (moreover, to simplify the implementation, it would be necessary to use recursion, but the performances do not bother me). Thanks to the properties of powers, we could generalize a lot of rewriting rules, so an extra pass would be necessary to rewrite the expression of the example into this equivalent expression:

In this case, however, this rewriting does not seem relevant. So my question is what interesting methods of simplification exist that I could use to achieve the style of result presented. I'm not talking about algorithms to compute some expressions in optimal times, but really about methods to simplify expressions encoded in an AST.

3
  • 1
    I don't understand your question. You don't simplify an expression at AST level: instead, you take AST, and do whatever needs to be done to simplify it, similarly to what Computer Algebra System does in Texas Instruments calculators, or Calculus & Analysis does in Wolfram|Alpha. If you're talking about this sort of simplification, there are entire books written on the subject, and lots of research going on to make the software; not something which can be written in a short answer. Jun 4 at 20:14
  • I must have misspoken because I didn't mean simplifying AST as such, but as you say using it and doing what needs to be done to apply simplification methods. This is the type of simplification I was talking about, I didn't know there were books on the subject, it seems to be a vast subject, which is why my research was quite unsuccessful, I think. I will look into the resources you mentioned.
    – Foxy
    Jun 4 at 20:56
  • Got it. See my answer. Jun 4 at 22:16
7

The term you are looking for is symbolic computation or algebraic computation, as opposed to numerical computation which deals with numerical approximations.

It is a large domain, with an important number of books written on the subject. There is no way to tell you how to solve the problem you're facing, because there are just too many things to consider. The Wikipedia article may be a start; from there, you should be able to find other resources, and more importantly books and research papers explaining the different concepts and the specific details.

Note that such systems are highly complex and take years to develop. As examples, you may be interested in Computer Algebra System used in Texas Instruments calculators, and Calculus & Analysis in Wolfram|Alpha. Maple is another popular application which deals with symbolic computation. There are possibly open source projects as well, although I don't know any.

Finally, you may also be interested in the following StackExchange sites:

3

In your examples, there's a straightforward representation which is a key component in many computer algebra systems: rational polynomials. Computer algebra systems have a rich set of algorithms to manipulate polynomials, because this is a foundation on which many other algorithms are based.

(Note: This is taken from one of my answers at Computer Science SE. You are definitely better of asking a question like this on a forum that has LaTeX.)

A field, you will recall, is an algebraic structure which supports addition, subtraction, multiplication, and division.

Starting with the rational numbers Q, we can extend this with a monomial, which we will call x. This gives us the field Q[x], where the elements of the field are rational polynomials p(x)/q(x) where p and q are polynomials whose coefficients are rational numbers.

Any expression involving the field operations, rational numbers, and x can be converted into this form. In your case, you can simplify it dividing both the numerator and the denominator by their greatest common divisor.

We can go further and extend with more monomials, to form, say, Q[x][y], whose elements are rational polynomials p(y)/q(y) where the coefficients are in Q[x].

This formulation, of the field operations plus free variables, is interesting for several reasons, notably that its first order theory is decidable.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.