PDA

View Full Version : Overloading the + operator for linked lists(binary numbers)




computerexpert
Mar 1, 2013, 05:33 PM
I have tried to understand the concept of linked lists and I have read the assigned chapter 2 times. My teacher is a little laid back when it comes to teaching! This is only a portion of my program. This function is supposed to add 2 binary numbers 11101+1101 and store the result in the temp list. The answer I get is 10000.I don't think that it is adding the carry. If there is anything wrong with the way I have asked this question, please let me know!


#include <iostream>
#include <fstream>
#include <cctype>
using namespace std;
#include "binary.h"

ostream & operator<<(ostream & outfile, const binary & outclass)
{
nodetype *current;
current=outclass.head_ptr;
while(current!=NULL)
{
outfile<<current->info<<" ";
current=current->link;
}

return outfile;
}
istream & operator>>(istream & infile, binary & inclass)
{

nodetype *newnode,*last;
char ch;
int intch;
list_clear(inclass.head_ptr);
inclass.head_ptr=NULL;
last=NULL;
infile>>ws;
infile.get(ch);


while( isdigit(ch)and infile)
{


intch = ch -'0';


newnode= new nodetype;
newnode->info=intch;
newnode->link=NULL;
if (inclass.head_ptr==NULL)
{
inclass.head_ptr=newnode;

}
else
{
last->link=newnode;

}
last=newnode;
infile.get(ch);

}


return infile;
}
binary operator+( binary num1, binary num2)
{
binary temp;
int carry, sum;
nodetype *current1, *current2, *newnode;
reverselist(num1.head_ptr);
reverselist(num2.head_ptr);
current1=num1.head_ptr;
current2=num2.head_ptr;
temp.head_ptr = NULL;
carry = 0;
while(current1!=NULL && current2!=NULL)
{
newnode=new nodetype;
newnode->link = temp.head_ptr;
temp.head_ptr=newnode ;
sum = current1->info + current2->info + carry;
temp.head_ptr->info = sum% 2;
carry = sum/2;
current1=current1->link;
current2=current2->link;
}

while(current1!=NULL)
{
newnode=new nodetype;
newnode->link = temp.head_ptr;
temp.head_ptr=newnode ;

sum = current1->info + carry;
temp.head_ptr->info = sum%2;
carry = sum/2;
current1=current1->link;


}
while (current2!=NULL)
{
newnode=new nodetype;
newnode->link = temp.head_ptr;
temp.head_ptr=newnode ;

sum = current2->info + carry;
temp.head_ptr->info = sum%2;
carry = sum/2;

current2=current2->link;

}

if (carry)
{
newnode=new nodetype;
newnode->link = temp.head_ptr;
temp.head_ptr=newnode ;
newnode->info=carry;
}

return temp;

}
binary::binary()
{
head_ptr=NULL;
count=0;

}
binary::binary(const binary & inclass)
{
nodetype *tail_ptr;
list_copy(inclass.head_ptr,head_ptr,tail_ptr);

}
binary::~binary()
{
list_clear(head_ptr);

}
const binary & binary::operator =(const binary & otherlist)
{
nodetype *tail_ptr;
if(this != &otherlist)
list_clear(head_ptr);
list_copy(otherlist.head_ptr,head_ptr,tail_ptr);
return otherlist;




}
int binary::getcount() const
{

}
void list_clear(nodetype*& head_ptr)
{
nodetype *removeptr;
while(head_ptr!=NULL)
{
removeptr=head_ptr;
head_ptr=head_ptr->link;
delete removeptr;
}
}
void list_copy(const nodetype*source_ptr, nodetype*& head_ptr, nodetype*& tail_ptr)
{
nodetype *temp;
head_ptr=NULL;
tail_ptr=NULL;
if(source_ptr==NULL)
return;

head_ptr=new nodetype;
head_ptr->link=NULL;
head_ptr->info=source_ptr->info;
tail_ptr=head_ptr;

source_ptr=source_ptr->link;
while(source_ptr !=NULL)
{
temp= new nodetype;
temp->link=NULL;
temp->info=source_ptr->info;
tail_ptr->link=temp;
tail_ptr=tail_ptr->link;
source_ptr=source_ptr->link;
}
}
void reverselist(nodetype*& mylist)
{
nodetype *templist, *tempnode;

templist = NULL;
while(mylist !=NULL)
{
tempnode = mylist;


mylist = mylist->link;
tempnode->link = templist;
templist = tempnode;

}
mylist = templist;

}





#include <iostream>
#include <cstdlib>
using namespace std;
struct nodetype
{
int info;
nodetype *link;
};
class binary
{
friend ostream & operator<<(ostream & outfile, const binary & outclass);
friend istream & operator>>(istream & infile, binary & inclass);
friend binary operator+( binary num1, binary num2);

public:
binary();
binary(const binary & inclass);
~binary();
const binary & operator =(const binary & otherlist);
int getcount() const;
private:
nodetype *head_ptr;
int count;
};
void list_clear(nodetype*& head_ptr);
void list_copy(const nodetype*source_ptr, nodetype*& head_ptr, nodetype*& tail_ptr);
void reverselist(nodetype*& head_ptr);



chown33
Mar 1, 2013, 06:17 PM
You haven't posted any code that shows the structure of the class (member variables, member functions, etc.), so anything working with class member variables is unknown code we have to guess at.

Instead of guessing, I'll just describe a debugging strategy.

Since you suspect carry isn't being handled correctly, use the debugger to watch carry. Next, create the simplest test case that should produce a carry.

In binary, the simplest carry-generating case is 1 + 1, so make two numbers with the value 1, and add them together while watching carry in the debugger.

If you don't know how to use the debugger, now is a good time to learn it.

If you can't visualize what the code is doing simply be looking at it or "running it in your head", then you need a visualization tool that shows you what the code actually does, when you actually run it. That tool is the debugger.

Summary:
1. Make test cases.
2. Run the test cases.
3. Use the debugger.

computerexpert
Mar 1, 2013, 06:28 PM
You haven't posted any code that shows the structure of the class (member variables, member functions, etc.), so anything working with class member variables is unknown code we have to guess at.

Instead of guessing, I'll just describe a debugging strategy.

Since you suspect carry isn't being handled correctly, use the debugger to watch carry. Next, create the simplest test case that should produce a carry.

In binary, the simplest carry-generating case is 1 + 1, so make two numbers with the value 1, and add them together while watching carry in the debugger.

If you don't know how to use the debugger, now is a good time to learn it.

If you can't visualize what the code is doing simply be looking at it or "running it in your head", then you need a visualization tool that shows you what the code actually does, when you actually run it. That tool is the debugger.

Summary:
1. Make test cases.
2. Run the test cases.
3. Use the debugger.

I have edited my post. This information seems like it will steer me in the right direction as I don't know how to trace my steps using my brain...my teacher never mentioned this method.I will give it a try. But let me know if you find anything or if you are finished helping :).




I have edited my post again. I have given my implementation file followed by my specification.

subsonix
Mar 1, 2013, 07:22 PM
You should probably try to separate your linked list code from your binary numbers code. That way you can test your 'add' function separately, then when that works, try to overload the + operator. Just my opinion.

computerexpert
Mar 1, 2013, 07:27 PM
You should probably try to separate your linked list code from your binary numbers code. That way you can test your 'add' function separately, then when that works, try to overload the + operator. Just my opinion.

Are you referring to the debug method that the previous poster was hinting at? I have no idea how to debug.

subsonix
Mar 1, 2013, 07:39 PM
Are you referring to the debug method that the previous poster was hinting at? I have no idea how to debug.

No, but you have a binary number class that implements a linked list. Why not make a linked list as a separate class, then make a linked list of binary numbers. Where a binary number is also a separate class, that way you can create and test your binary 'add' function in isolation, (overloaded operator or not).

computerexpert
Mar 1, 2013, 07:48 PM
Ok I am going to skip that idea for a brief moment as I am recieving help from other forums. Apparently my code is fine. It is just my main program.


This code clears my outfile. Do you know why?

int main()
{
ifstream infile;
ofstream outfile;
binary binobj1;
binary binobj2;
infile.open("program2in.txt");

if(!infile)
{
cout << "Failure to open program2in.txt." << endl;
system ("pause");
return 1;
}

outfile.open("program2out.txt");
if(!infile)
{
cout << "Failure to open program2out.txt." << endl;
system ("pause");
return 1;
}

while( (infile>>binobj1) && (infile>>binobj2) )
{
outfile << binobj1 << " + " << binobj2 << " = " << binobj1 + binobj2 << endl;
}

infile.close();outfile.close();
system ("pause");
return 0;
}

subsonix
Mar 1, 2013, 08:02 PM
This code clears my outfile. Do you know why?


What do you want/expect to happen? You can open a file in different modes, such as append for example.

computerexpert
Mar 1, 2013, 08:05 PM
I expect the overloaded insertion operator to display the sum in my outfile along with the lists.

subsonix
Mar 1, 2013, 08:09 PM
I expect the overloaded insertion operator to display the sum in my outfile along with the lists.

With regards to a file that has previously been written to.

But it seems, you don't know if the problem is your implementation of the operator or if you have opened the file in the wrong mode, basically, we don't know if we are looking at the correct code.

computerexpert
Mar 1, 2013, 08:15 PM
With regards to a file that has previously been written to.

But it seems, you don't know if the problem is your implementation of the operator or if you have opened the file in the wrong mode, basically, we don't know if we are looking at the correct code.

My overload insertion should be sound. My teacher looked over it and sad that it should be a traversal.

subsonix
Mar 1, 2013, 08:18 PM
My overload insertion should be sound. My teacher looked over it and sad that it should be a traversal.

Ok, I guess your code works then.

Let me explain. You said that your code "clears your file". I then said that you can open a file in different modes, such as append. To that you responded how you expect your overloaded operator to work, indicating that's the place where the problem is.

computerexpert
Mar 1, 2013, 08:23 PM
I then said that you can open a file in different modes, such as append.
Yea I don't understand this. Maybe this is where I got lost in communication. I'm not sure where the problem is:o

subsonix
Mar 1, 2013, 08:26 PM
Yea I don't understand this. Maybe this is where I got lost in communication. I'm not sure where the problem is:o

You can add arguments to open, if you open a file in append mode then new data is appended to the end of the file. Is that what you want to happen?

computerexpert
Mar 1, 2013, 08:30 PM
You can add arguments to open, if you open a file in append mode then new data is appended to the end of the file. Is that what you want to happen?

Hmm.... I have an infile which contains binary numbers. I have a blank outfile. The program should read the infile and write/display to the outfile.

Im not sure about the append concept.

subsonix
Mar 1, 2013, 08:36 PM
Hmm.... I have an infile which contains binary numbers. I have a blank outfile. The program should read the infile and write/display to the outfile.

Im not sure about the append concept.

Ok, but what exactly do you mean by:

This code clears my outfile.

It gives the impression that it erases previous information on your outfile.

computerexpert
Mar 1, 2013, 08:40 PM
Ok, but what exactly do you mean by:



It gives the impression that it erases previous information on your outfile.

Hehe, sorry. my previous code:
while(infile)
{
infile>>binobj2;
outfile<<binobj1<<endl;
outfile<<binobj2<<endl;
outfile<<binobj1+binobj2<<endl;



infile>>binobj1;
}

displayed output in my outfile.

the new code makes the outfile blank.

subsonix
Mar 1, 2013, 08:44 PM
Hehe, sorry. my previous code displayed output in my outfile.


Change back to your previous code.

computerexpert
Mar 1, 2013, 08:47 PM
Change back to your previous code.

Yea my previous works but it outputs the wrong sum. I'm gonna call it quits on this. I mean my teacher never showed me debugging, so it's not important to him and I'm not gonna try to figure it out I have other studies to attend to. Thanks for your help.

RiskyMr
Mar 1, 2013, 09:00 PM
This function is supposed to add 2 binary numbers 11101+1101 ...
The answer I get is 10000.


I didn't look at any of your code, but note that 11101 - 1101 = 10000.

ArtOfWarfare
Mar 1, 2013, 09:16 PM
I didn't look at any of your code, but note that 11101 - 1101 = 10000.

Yeah, but if you fail to carry, 1 + 1 = 0 and 0 + 0 = 0, so 11101 + 1101 (without proper carrying) = 10000.

I suppose a good test to verify it isn't that it's performing subtraction would be to have input along the lines of

11001 + 1101. If its actually performing subtraction, your result will be 1100. If it's performing addition but failing to carry, your result will be 10100.

computerexpert
Mar 1, 2013, 09:43 PM
Yeah, but if you fail to carry, 1 + 1 = 0 and 0 + 0 = 0, so 11101 + 1101 (without proper carrying) = 10000.

I suppose a good test to verify it isn't that it's performing subtraction would be to have input along the lines of

11001 + 1101. If its actually performing subtraction, your result will be 1100. If it's performing addition but failing to carry, your result will be 10100.

Yea so it's something wrong with adding the carry. I will look at it more.

I had to cut my computer off.....for some reason everything works. Thanks for all of your help!

ArtOfWarfare
Mar 1, 2013, 09:56 PM
I read over your code and can't see anything obviously wrong with it (although I would suggest adding comments to it to make things clearer.)

One suggestion would be reducing how much you repeat the same lines of code. You have:

newnode=new nodetype;
newnode->link = temp.head_ptr;
temp.head_ptr=newnode ;

Written 4 times within your + function. Suppose you discover an issue with one of those lines of code. You'll have to fix, not one, but four lines of code, and you'll have to make sure you fixed it the same way each time.

You could clean up your code by combining your 3 while loops into a single while loop that ORs the two pointers together instead of ANDs them and then have an IF or two to make sure each pointer is still valid before you try accessing it.

Just a thought.