# algebra solver

This is a discussion on algebra solver within the C++ Programming forums, part of the General Programming Boards category; Ok people, I am a maths teacher. I teach simple highschool maths. Kids always seem to have problems with algebra. ...

1. ## algebra solver

Ok people,

I am a maths teacher. I teach simple highschool maths. Kids always seem to have problems with algebra. They struggle to apply the rules of 'BODMAS' in order to solve an equation.

I want to create a general algebra solver using c++! Sounds pretty daunting I know. But I know it can be done. An example would be to create a program to solve:

6(x+2)+ x/2= 5(x+1)

And before anyone writes in saying use a 'scientific calculator' - this is not what I want. Specifically, the program should show each line applying the rules of 'BODMAS' so....

1. 6x+ 12 + x/2 = 5x+5 Expand brackets

2. 2(6x+12) +x = 2(5x+5) Multiply of the bottom

3. 12x+ 24 + x = 10x +10 Expand brackets again

4. 12x +x -10x = 10 -24 Collect x terms on LHS

5. 3x = -14 simplify

6. x = -14/3 factorise out x and solve.

In order to do this I reckon you would need to create several functions. Namely;

' Multiply_off_bottom'
'Expand_brackets'
'Separate 'x' onto LHS'
'Factorise out x'

What's more the program should be able to recognise 'terms'. Not just terms involving 'x' but any other letters, 'n', 'xyz' etc.

Here's what i got so far (not much I know)

Code:
```#include <iostream>
#include <stdlib.h>
#include <string.h>

using namespace std;

int main()
{
char count[81];
char store[81];
int  freq[81];
char array[81][81];
int size_a;
int freq_counter;
int array_counter;

cin>>store;

size_a=strlen(store);
//counts terms automatically
int count_terms=1;
for (int a=0; a<size_a; a++)
{
if (store[a]=='+')
{
count_terms++;
}
if(store[a]=='=')
{
count_terms++;
}
if (store[a]=='-')
{
count_terms++;
}

}

for (int a=0; a<count_terms; a++)
{   cout<<"Enter each term"<<endl;
cin>>count;
int size=strlen(count);
freq[a]=size;
cout<<freq[a]<<endl;
}
cout<<""<<endl;

//store[81]='-4x+2y-x-2'
//store each term in a 2-d array
int counter =0;
for (int b=0; b<count_terms; b++)
{
for (int c=0; c<freq[b]; c++)
{
array[b][c]=store[counter];
counter++;
}
}
// like term count
// x = 2,      found in array [0][-],[2][-] *sum these*
// y = 1,       found in array [1][-]
// number = 1,  found in array [3][-]
// Need letter freq count!!!
cout<<array[0][1];

system("PAUSE");
return 0;
}```

2. heres a little help as i cant really tell where you want to go with this.

if you use this code instead, you wont need to have the user input the equation, and then each term separately.

Code:
```vector <char>  termHolder;
int term_placeholder1 = 0; //points to the spot where the term begins
int term_placeholder2 = 0; //points to the spot where the term ends
char term[20];

for (int a=0; a<size_a; a++)
{
if (store[a]=='+')
{
count_terms++;
term_placeholder2 = a - 1; //you dont want term_placeholder to be pointing to the '+' but rather to the last digit in the term

for(int x = term_placeholder1; x < term_placeholder2; ++x)
{
term[x] = store[x]; //I am not sure if this is the correct syntax (or even if this is allowed), so you might need to use pointers to get the value of store[x] into term[x]
}
termHolder.push_back(term);
term_placeholder1 = term_placeholder2 + 2; //set the term_placeholder1 so that it points to the first digit in the next term. You add two because if you added 1 you would be pointing to the '+' sign and if you add two you point to the first digit in the next term
}
if(store[a]=='=')
{
count_terms++;
term_placeholder2 = a - 1;

for(int x = term_placeholder1; x < term_placeholder2; ++x)
{
term[x] = store[x];
}
termHolder.push_back(term);
term_placeholder1 = term_placeholder2 + 2;
}

if (store[a]=='-')
{
count_terms++;
term_placeholder2 = a - 1;

for(int x = term_placeholder1; x < term_placeholder2; ++x)
{
term[x] = store[x];
}
termHolder.push_back(term);
term_placeholder1 = term_placeholder2 + 2;
}

}```

A couple of notes that you should know:

this method looks for the '+' (or what not) and then counts the term that is before it, not after. also this code is probably very errorful syntax wise, cuz im just cool like that.

3. >>Sounds pretty daunting I know.
Indeed, it is - and it seems that you haven't yet realized the full magnitude of the task yourself, especially given your VERY general requirements. It is difficult enough to make a simple expression evaluator, and more difficult to make one that will expand polynomials, and even more difficult to make one that will solve polynomials, and even more difficult to make one that will solve polynomials by methods of factoring. The requirement that it should be able to 'solve' multivariable equations tops off the heap, especially considering that with 1 equation and 2 variables, there is no numerical solution but an infinite number of rearrangements of the equation. And if you plan to make it solve several multivariable equations simultaneously, I highly doubt that you (or most other people, myself included) will get very far. This is especially highlighted by the fact that invitational mathematics competitions have 'general' algebra problems, and many people have difficulties solving them even though they are specifically engineered to have 'easy' solutions.

Not to be a spoilsport, but perhaps you should consider revising your goal to be more realistic; then you can see where to go from there.

4. The best method I can think of for dealing with symbolic algebra (provided you do want to program it yourself) is to build an expression tree (a tree structure with either constants or variables as the leaves, and each operator node taking an appropriate number of sub-expressions as children) and build up the tree as you parse the input string. If you are doing this in C++, I'd recommend using the std::string class as well, as it would make your life much easier.

5. As long as you're limiting it to elementary algebra -- one variable, first degree, no transcendental functions -- it shouldn't be too daunting, but it involves more than you have outlined.

You probably want to write a parser that can first ascertain that the two expressions (on each side of the =) are valid expressions and then evaluate and manipulate them according to your rules. In order to do this you must first define your grammar: what is a valid expression? what is a valid term? what is a valid factor? etc.

To begin, look up "context free grammars". Then you probably ought to consult a textbook on compiler construction for information about parsing.

Finally, although it obviously can be done in C or C++, think about possibly writing it in a language like lisp or prolog which would probably make the task considerably easier.

6. First of all thank you for all of your responses.

In response to 'Hunter2', I believe what I am trying to achieve is realistic. For example, I plan to make a one variable, first degree equation solver as outlined by 'R. Stiltskin'. And if I plan to use more than one term the equation should be easily solved using highschool mathematics.

I am well aware of the difficulties faced when trying to solve equations of a higher order. For example to solve : x2 + 4x-8 =0
you would need to use the 'quadratic equation'. However, these are not the kind of equations I intend to solve. I'm sorry if I did not make myself clear.

In response to 'R.Stiltskin', I don't really know anything to do with parsing so I guess I'm going to have to read up on that. Nevertheless, what you have suggested sounds interesting. In regards to learning another language - again sounds interesting, but I plan to stick with c++ since it is what I am familiar with.

If you guys are still confused as to what I want to do, I think this site should help explain.

http://www.softmath.com/index.html

Effectively, I want to do this in c++ but without the flashy GUI (graphical user interface) and of course without the cash payment!

7. parsing is a task that is done quite frequently. Basically, you scan input for smaller components. So you can parse a sentence into individual words, and you can parse a word into individual char.

In this case you can parse an algebraic equation into two algebraic expressions and an equal sign. Each algebraic expression can have one or more terms, one or more mathematical operators, and a left and right parenthesis. Each term can have coefficient, one or more pairs of left and right parenthesis, and a variable. Each coefficient can have a base that may or may not be surrounded by paretnesis maybe an exponent sign and an exponent that may or may not have parenthesis. Each base and exponent can have a sign and a numerical type (double, float, int, rational number) Each numerical type must have some digits, may a single decimal point, but not more than one, and may have a /, but not more than one. I may not have even covered all the possibilities or I may have gone overboard with the possible parsing components, that will be up to you.

Once you have a system worked out then you can figure out that like terms has to do with variables, and you can then just add the coefficients, etc. The remainder of the steps you have outlined can also be assembled from the various components of the parsing process.

Bottom line, it's not straight forward.

8. treenef, I canl help you write the parser if you want. I can do this using lex and yacc, and turn the your algebra expression in some sort of tree. You'll then have to apply a number of transformations to the tree, somehow or other doing pattern matching and trial-and-error on the tree. Also, I'm going to suggest that you only keep the exponent at 2. There's no simple algebraic way to solve algebraic solutions.

9. treenef, are you still trying to do this or have you already found/written a program? I just finished writing one myself using Zach's suggested method.

It basically expands the left and right sides of the equation (showing the steps) according to proper order-of-operation, moves all variables to the left, and then solves (by successive approximation, although for first-order polynomials there should be no major difference). The only major drawbacks I've noticed with it is that you can't do 3(4) etc. - it would have to be 3 * 4, since the parsing requires all operators to be explicitly present - and also, it doesn't support exponents/squareroots etc. For simple +-* problems though, it works a charm - and for problems involving division too, as long as the numerator is divisible by the denominator (assuming they're polynomials - division will always succeed if the denominator has no x terms).

If you like, I can post the program here and you can get some ideas from it, or just use it if it works as you wanted.

**EDIT**
Yes, I know it's a bump - but I figured it wasn't too long, and it's relevant.

10. That would be great Hunter2.

Yes if you could post it here I would be most greatful. I read Zach's suggested method however, I am unfamiliar with the concepts of 'trees' although I read something about them when I was messing around with AI.

5(6+7x) = 30 + 35x ?

Is that the bit you were having problems with since it doesn't have the operator '*' ?

Treenef

11. Yes, my parsing algorithm requires that all operators be explicitly stated - although expressions like "35x" are interpreted as polynomial values. For the above statement to be valid, it would have to be changed to:
5 * (6 + 7x)
And to have a valid equation, for example:
5 * (6 + 7x) = x + 2 * (x + 2)

The expression would then be parsed, and stored in an expression tree as follows:
Code:
```LHS:
* (root)
/ \
5   +
/ \
6  7x

RHS:
+ (root)
/ \
x   *
/ \
2   +
/ \
x   2```
The LHS is then recursively expanded:
6 + 7x => 6+7x
5 * (6+7x) => 30+35x

RHS is expanded:
x + 2 => x+2
2 * (x+2) => 2x+4
x + (2x+4) => 3x+4

LHS - RHS:
(30+35x) - (3x+4) = 0
32x+26 = 0

And then solves the system.

I'll post the code when I get home.

12. Ok, here's the code - just finished putting some last touches on it, i.e. error checking and stuff. You can compile/tweak it yourself, to make sure it isn't some virus/trojan I'm sending you (and also because CBoard won't let me upload zip files ).

Hope you like it!

13. Treenef humbly bows down to hunter2. What you have created is really amazing. I especially like the idea of using 'trees' -parent/child nodes to go about finding a solution-genius (although zach originally first suggested it)

I take my hat off to you and I would add to your reputation if it wasn't already full!

You must of spent a lot of time on that-more so than I ever did and yours works amazingly.

When I finished mine I'll be sure to post it on the net so you can comment and suggest changes.

Much thanks

Treenef,

14. I'm glad I was of help

Actually, after doing a quick search on the web for Newton's Method, I changed my solve() and findRoot() functions. It's much simpler, and (I think) will yield better results for the same number of iterations. The code for solveNewton() and findRootNewton() is:
Code:
```double findRootNewton(const Polynomial& p, const Polynomial& dp, double x1, double x2, int prec = 100)
{
double x = (x1 + x2) / 2;

for(int i = 0; i < prec; ++i)
x -= (p.evaluate(x) / dp.evaluate(x));

return x;
}

std::deque<double> solveNewton(Polynomial& p)
{
std::deque<double> ret;

if(p.order() < 1)
return ret;

if(p.order() == 1)
{
ret.push_back(-(p.coefficient(0) / p.coefficient(1)));
return ret;
}

Polynomial der = p.derivative();
std::deque<double> extrema = solveNewton(der);
if(extrema.size() > 0)
{
extrema.push_front(extrema.front() - 1.);
extrema.push_back(extrema.back() + 1.);
}
else
{
extrema.push_front(-1.);
extrema.push_back(1.);
}

std::deque<double>::size_type i, j;
j = extrema.size() - 1;
for(i = 0; i < j; ++i)
{
double root = findRootNewton(p, der, extrema[i], extrema[i + 1]);
if(root != std::numeric_limits<double>::min())
ret.push_back(root);
}

return ret;
}```
The only potential problem I see, is that I have no idea how Newton's Method really works (just grabbed the formula "x_(n+1) = x - f(x)/f'(x)" from somewhere) - and so I don't know for sure if this method will only converge on a root between the extrema on the left and right of the current x value, or if it will potentially find the same root several times while omitting others. So far as I have tested, however, it seems to hold up OK.

15. Originally Posted by Hunter2
int prec = 100
Isn't 100 a little overkill? I would think that 5-10 will be enough.

Newton's method work by taking the tangent of the function curve at x(n). x(n+1) is where the tangent intersects the x-axis.

Page 1 of 2 12 Last