How to manipulate mathematical symbols?

Question

This is more of an "educational" question. :)

Although, probably, I would like to do something like this in the end.

So, let's say I got the equation. There can be any equation, if this is not funny, and also a person who knew mathematically could solve it.

Let them say ... 0 = (x-1) (x + 2)

or ... y = (x ^ 2), y = 1 / x

Or sine functions, etc. In principle, mathematics, like in school.

The question is, how can I write a computer program to solve this problem? I know this is possible because programs like Mathematica, Maple, etc., have been doing this for decades! But I cannot find good documentation on how to make even a simple equation solver.

I do not expect answers that will tell me "this is exactly how you do it," because, of course, such a thing is a whole big program, and not just a piece of code.

But just a general overview or links to some good docs? That would be great! Thanks:)

Data structures and algorithms are especially needed.

Otherwise, I just need to find out HOW I SOLVE THE EQUATIONS, and encode it. But it will take literally months to get right (I used to do this by formalizing my own thinking process into code, it works, but it is slow).

Answer 1

Wolfram Alpha will become the benchmark that is most easily available to you.

Your inputs are strings, so the first step is to write lexer / parser to split these strings into tokens and put them in an abstract syntax tree (AST).

You don’t say what language you want to implement this, but I would recommend looking at ANTLR . This is a parser generator that can help you create AST. You will have to come up with a grammar for your equations.

Once you have an AST, your solver will walk the tree and associate more specific operations with characters like "+", "-", etc. The more operators you can handle, the more powerful and comprehensive the solution will be.

But there are many difficulties that you will have to face or eliminate:

• Not all equations have solutions.
• Not all equations have closed forms.
• Not all equations are linear.
• Many interesting problems consist of many related equations (I think linear algebra).
• You need to know a lot about numerical methods for cases where the closed form does not allow you.

I would advise you to start with simple arithmetic and polynomials and work. Stephen Wolfram did not write Mathematica in a day.

Answer 2

Look at some articles of symbolic manipulation .

Peter Norvig PAIP book covers a very simple system of symbolic manipulation and solving equations, so it would be useful to read. It presents the basics of an AI program called MacSyma , which ultimately formed the basis of Mathematica .

Answer 3

The basic method is to represent the structure of a mathematical equation in a computer program. This is very similar to what compilers do, but compilers basically convert their inputs into a machine-readable format, but computer algebraic systems basically produce output in the same format as their inputs, but do a slightly different conversion. In any case, the direct output is an abstract syntax tree. The next step will apply some pattern matching methods (just like regular expressions work), as well as some mechanical transformations to rewrite the tree in some useful way.

If you want to see how this can be done, SymPy is a python symbolic math library that is open source and mainly focuses on aspects of manipulating theme symbols.

Answer 4

In addition to other people's useful answers: this link seems interesting: http://en.wikipedia.org/wiki/Pattern_matching also, the "abstract tree syntax" seems interesting. Basically, we are talking about "pattern matching" in the syntax tree! It looks like a regular expression, but for code.

I already wrote my own "abstract tree syntax" :) So, I am already moving a little along the path to the symbolic manipulator.