Expression Simplification (Adding like terms) [C++]

Galib · 10-06-2010, 07:56 PM

I am having a little trouble understanding how to loop through 6x^2 + 10x^2 + 9x^2 + 6x^1 + 15x^1 + 9 to combine like terms.

Each polynomial is stored as a LinkedList holding a coefficient and exponent. Thus, I can just compare the exponents to see if they match, and if they do, add them together and insert into new LinkedList. If they don't match, then add them into the LinkedList.

I actually used the List ADT to create a list of polynomials. So I've got a list of polynomials, each containing a struct that stores a coefficient and exponent.

I am having a hard time combining like terms... I know what I need to do, but I just can't seem to get it in code form.

6x^3 + 10x^2 + 9x^2 + 6x^1 + 15x^1 + 9
should turn into
6x^3 + 19x^2 + 21x^1 + 9

We can assume that the list will always be sorted in descending order.
Thank you!

graemef · 10-06-2010, 11:49 PM

Hint: Write a function that receives a single argument the exponent value. This function will step through the linked list and return the node with the matching exponent value or null if there is no match.

Galib · 10-07-2010, 01:23 AM

I've gotta use iterators, I've written a simplify that works using pointers. This is due to having access to next, which I don't with iterators.

Some pseudo code,

Code:

for(i = list.begin(); i != list.end(); i++) {
if(i->exp == (this is where I would have i->next->exp)) // to check to see if the next exponent is the same value
} 

if it was the same, then it just added the coefficients and input them into a new list

My problem is combining like terms using iterators and the list ADT.

Thank you.

graemef · 10-07-2010, 01:43 AM

Well unless you know that the equation has been entered in order you will need a second iterator to step through each node in the original list. Although I suspect that given you will have two lists you can work with two iterators one on each list.

Galib · 10-07-2010, 02:48 AM

I have one list, which stores 6x^3 + 10x^2 + 9x^2 + 6x^1 + 15x^1 + 9 .

EDIT: I actually found a fix, but it's very ghetto yet works. I am still interested if any of you know how to combine like terms using iterators.

graemef · 10-07-2010, 03:28 AM

So on that example you iterate through the list getting the node and then add it to your result list. You will insert the node to the list if the previous node (of the result list) has a different exponent otherwise you will increment the coefficient of the previous node if the exponent is the same. The trick is with the first time through when the previous node doesn't exist and so you will need to add a comparison to null to your test.

However this would not work with a list stored as follows: 10x^2 + 6x^3 + 9x^2 + 6x^1 + 15x^1 + 9 .

dwhitney67 · 10-07-2010, 10:53 PM

Quote:

Originally Posted by Galib

I have one list, which stores 6x^3 + 10x^2 + 9x^2 + 6x^1 + 15x^1 + 9 .

EDIT: I actually found a fix, but it's very ghetto yet works. I am still interested if any of you know how to combine like terms using iterators.

Please show your solution. Since this task seems like a school-work problem, showing you a solution would be a breach of the (homework) code of conduct for this forum.

dwhitney67 · 10-07-2010, 10:58 PM

Quote:

Originally Posted by graemef

...
However this would not work with a list stored as follows: 10x^2 + 6x^3 + 9x^2 + 6x^1 + 15x^1 + 9 .

Since the OP is apparently using the STL list, he could always sort the list before attempting to simplify the equation.

graemef · 10-07-2010, 11:43 PM

Quote:

Originally Posted by dwhitney67

Since the OP is apparently using the STL list, he could always sort the list before attempting to simplify the equation.

Sure but using a second iterator on the second (condensed list) would be more efficient. As I was hinting at in an earlier post

johnsfine · 10-08-2010, 07:06 AM

Quote:

Originally Posted by Galib

We can assume that the list will always be sorted in descending order.

That assumption eliminates the issue graemef and dwhitney67 have been discussing, as well as eliminating anything that would make the project non trivial.

The fact that you are reading one list and writing a new one (vs. modifying the original list in place) makes the task even simpler.

It's hard to guess why using iterators for this task is in any way inconvenient.

If you have code that is more awkward than you would like, post the code and you probably will get some suggestions about what you might do better.