views:

529

answers:

7

Hi, I would like to know if anyone has info or experience on how to do something which sounds simple but doesn't look like it when trying to program it. The idea is : give a string containing an equation, such as : "2*x = 10" for example (this is simple, but it could get very complex, such as sqrt(54)*35=x^2; and so on....) and the program would return x = 5 and possibly give a log of how he got there.

Is this doable ? If so, does anyone have a lead ? For info there is this site (http://www.numberempire.com/equationsolver.php) which does the same thing in PHP, but isn't open source.

Thanks for any help !

+1  A: 

If equations do get complex, It won't surely be few lines of C/C++ code.

For linear equations, you would have to simulate one of the methods described in Linear Algebra Books. The code of that is small enough.

Gunner
First, as I said many times in comments, parsing is the first step, then the equation must be "described" abstractly, that is in a class, and finally, solved... I don't think it will hold in a few lines of code... LOL thanks anyway. PS What is the name of the book you are talking about ?
Alexandre Cassagne
I was not talking about any particular book, but you could check Elementary Liner Algebra, Howard Anton.You could try googling "Gaussian Elimination"
Gunner
+1  A: 

One correction: this isn't linear algebra, which usually means matricies of multiple equations and unknowns.

Your example certainly isn't complex.

What you need is a simple expression grammar and parser. Parse the equation into an abstract syntax tree and walk the tree to evaluate it.

If you were writing Java it might look like this. Another example is symja. Perhaps it'll be enough inspiration for you to come up with your own for C++.

You might also want to look into Mathematica and Wolfram's Alpha. Stephen Wolfram is one of the world's best mathematicians and computer scientists. He's got a lot of stuff that you could reuse to good advantage rather than writing it yourself.

You'll have to define what you mean by "solve" and what you expect to have returned.

There are symbolic solutions and numerical solutions. Which one do you mean? Both are equally valid, but they're different. You'll apply different techniques depending on your answer.

Another point: there are many techniques for "solving" equations that depend a great deal on the type of equation. If you give me something like f(x) = 0 I think of root finding algorithms like Newton's method. If you give me an ordinary differential equation I might try a substitution method or numerical integration using Runge-Kutta. If you give me a partial differential equation I can apply finite difference, finite element, or boundary element techniques. (Don't get me started on elliptical, parabolic, and hyperbolic PDEs.)

The point is that your question is very generic, and the answer depends a great deal on what you're trying to do. More detail might help.

duffymo
That's not everything he needs, as he's not interested in just evaluating a mathematical expression, but in solving an equation. He also needs a method that can solve any equation.
IVlad
Indeed, the project is in two parts :Create an equation type/object which is capable of parsing a string (any string, like on the site I showed http://www.numberempire.com/equationsolver.php) which would, I guess be the hardest part, as it has to accept any input, x=3/2 as well as x^2=(x+2)*4+7^2 (this is just a random example, but the fact that it parses a string makes it hard as it needs to expect anything.Also, the second part, solving the equation should hopefully be easier, even though I'm not sure it will exactly be a "two-liner" but I hope to be able to find the way...
Alexandre Cassagne
+2  A: 

Firstly you have to properly define what kinds of equations you can have as an input. Then you should create a good abstraction to represent the equation, e.g. a polynomial class. When you want to use more complex expression, go for a tree for numerical expressions. Parsing can be quite easy if you have good rules to convert the expression into prefix notation, then evaluation is easy using stacks. Once you have artithmetic trees or polynomials, you can implement transformations to compute the variable(s).

Gabriel Ščerbák
Parsing is very complicated as far as I'm concerned, we are talking about taking a string which can expect any value to it, it can be "x*3+5=12" as well as "x+1=1" or "x*2*3.14159" or anything, there is no specific rules to an equation, except "left member is separated from the right member using the symbol '='. This makes the parsing very complex for equations.
Alexandre Cassagne
@Alexandre Cassagne Firstly identify all your operators, specify their arity (unary or binary I guess in your case) and define ordering for them, which will show their precedence. Than you can tokenize your equation (split it into parts) by searching for the most significant operator first.
Gabriel Ščerbák
@Alexandre Cassagne To give you an example for "x*3+5=12" using arithmetic tree, firstly you search for "=" which is most significant and will be root of your tree. Then recursively look into left ("x*3+5") and right parts ("12") for most important operator first. For left part you have no "=" but you have "+" which is next and therefore your left child is plus operation, now again recursion for the left part of the left part ("x*3")... Leafs of your tree will be constants or variables.
Gabriel Ščerbák
@Alexandre Cassagne solving the equation would be than about finding variable leaf in the tree and gradually removing nodes from path from the "=" root to the leaf by converting the operation to its counterpart (plus to minus...) and adding it as the other child of "=". At the end "x" will be child of "=" and evaluating the otehr child of "=" will give you the result. The evaluating is simple inorder.
Gabriel Ščerbák
@Alexandre Cassagne if you are asking about the design for this solution, use Composite design patter nfor the arithmetic tree and use Visitor design pattern for evaluation, use the Iterator design pattern for walking the tree.
Gabriel Ščerbák
Thanks a lot :) I'm gonna start trying :PI'll try to make my code public, because as I see it, equation should be public domain ^^
Alexandre Cassagne
@Alexandre Cassagne I have got inspired by my answer as well and I will try to do some Code Kata exercieses to solve this:) However do no t expect mainstream adoption, because as someone mentioned above, there are numerical algorithm to solve some subproblems of this kind quite efficiently and as you get more general, you will significantly loose performance. But this is a very nice design task:)
Gabriel Ščerbák
+3  A: 

This is called "parsing", and although computer science has already solved this problem it isn't simple at all until you understand it thoroughly. There's an entire computer-science discipline that describes how to solve this problem. In C you must define the grammar of your input (possibly with precedence rules in it), then perform lexical analysis on your input, then parse the result and finally evaluate your parse tree.

In languages such as Ruby, however, because you have such thorough support for string manipulation and because you have such tremendous runtime power you can solve your problem with a single line of code like so:

puts(eval($_)) while gets

Yes, that will cover more than what you ask for.

wilhelmtell
How does the " eval() " command act ? Does it evaluate every character of the string it is given ?
Alexandre Cassagne
The `eval()` function takes a string as argument and evaluates it as if it was a script in that language. This function is very common in almost any interpreted language -- any language that doesn't use a compiler to execute its code. Perl, Python, Bash and others all have an `eval()` function or builtin.
wilhelmtell
Because every Ruby expression evaluates to something, the `eval()` function will always have a return value. So the code above just prints to screen whatever the `eval()` returns. The `eval()` takes as argument the value of the last expression, in this case the `gets()` call. The `gets()` takes a line from stdin and returns it. Its boolean value is false if it gets an end-of-file symbol.
wilhelmtell
In simple terms, the `eval()` function interprets and evaluates Ruby code, _any_ Ruby code. Because `4+5` is in fact Ruby code (which evaluates to `Fixnum` value `9`) the `eval()` function accepts it and parses it as such. It will interpret any Ruby code: if you type `4+5` you will get `9`, and if you type "calculator" code above the input `File.open("there","w") {|f| f.puts("be dragons")}` then the script will happily create a file and write to it. A powerful calculator, indeed, and perhaps too powerful. It can calculates anything at all though, no doubt.
wilhelmtell
Nice, I'm gonna try linking a ruby document to C nowThank you :)
Alexandre Cassagne
+1  A: 

You could try linking in SymPy to your C (or C++) code and using it to solve your equations.

IIRC, SymPy has that kind of functionality. Plus, it should be easier to manipulate the input string to a usable equation inside of Python and then pass it off to SymPy for solving.

Sagekilla
+1  A: 

There's going to be two parts to your problem: parsing the equation(s), and solving them symbolically. I'm not going to say much about the first, since other answers have already covered that topic well; my personal recommendation would be to write a simple recursive descent parser for expressions in prefix notation.

The second part, solving equations analytically, is going to be tricky. Generally speaking there are special classes of equations for which standard methods exist to find an analytic solution:

  • Systems of linear equations: any direct linear solver. If you want to show the steps explicitly and the number of equations/unknowns is small, I'd recommend something simple like unpivoted Gaussian elimination or Cramer's rule.
  • System of polynomial equations: Equivalent, after variable substitution, to finding roots of single polynomials. If these have degree <= 4, there are formulas for exact solutions. NB: For degree 3 and 4 these formulas are not pleasant.
  • Rational solutions to a system of polynomial equations with rational coefficient: Do variable substitution as above. Then brute force using the rational zero test.
  • Other kinds of equations: Good luck. For more complicated [systems of] nonlinear equations, if you can settle for numerical (non-analytic) solutions, look into Newton's Method.
+1  A: 

In general, you will have to parse the expression into some internal representation. Many linear algebra books suggest using matrices (or std::vector) to represent the coefficients. The exponent of the term is defined by its position in the vector.

So for example, the expression:

 2 + 3x + 5x^2

Can be represented as an array or std::vector:

std::vector<int> expression;
expression[0] = 2; // 2 * x ^ 0
expression[1] = 3;
expression[2] = 5;

Writing an evaluation function becomes trivial, and left as an exercise for the reader.

Solving multiple equations becomes more complex. There are existing libraries and algorithms for this. A Google search should come up with something good. :-)

I suggest starting out with simple terms and building a parser for that. Once that works, you can change the parser to accept function names as well.

If you are trying to simplify an expression that has terms on both sides of the =, just write down the steps you would normally take when solving by hand. Try some different equations to get some rules down. Now implement these rules in C++.

Thomas Matthews
Actually, a google search oddly doesn't turn up many interesting stuff, but I'm gonna try some methods on the page and make my searching furtherthanks :)
Alexandre Cassagne