Solve equation from string to result in C

Question

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 !

Answer 1

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.

Answer 2

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).

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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++.