Overloading the + operator for linked lists(binary numbers)

Discussion in 'Mac Programming' started by computerexpert, Mar 1, 2013.

  1. computerexpert, Mar 1, 2013
    Last edited: Mar 1, 2013

    macrumors newbie

    Joined:
    Mar 1, 2013
    #1
    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!


    Code:
    #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;
         
    }
    


    Code:
    #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);
    
     
  2. macrumors 603

    Joined:
    Aug 9, 2009
    #2
    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.
     
  3. computerexpert, Mar 1, 2013
    Last edited: Mar 1, 2013

    thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #3
    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.
     
  4. macrumors 68040

    Joined:
    Feb 2, 2008
    #4
    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.
     
  5. thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #5
    Are you referring to the debug method that the previous poster was hinting at? I have no idea how to debug.
     
  6. macrumors 68040

    Joined:
    Feb 2, 2008
    #6
    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).
     
  7. computerexpert, Mar 1, 2013
    Last edited by a moderator: Mar 1, 2013

    thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #7
    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?
    Code:
    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;
    }
    
     
  8. macrumors 68040

    Joined:
    Feb 2, 2008
    #8
    What do you want/expect to happen? You can open a file in different modes, such as append for example.
     
  9. thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #9
    I expect the overloaded insertion operator to display the sum in my outfile along with the lists.
     
  10. macrumors 68040

    Joined:
    Feb 2, 2008
    #10
    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.
     
  11. thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #11
    My overload insertion should be sound. My teacher looked over it and sad that it should be a traversal.
     
  12. macrumors 68040

    Joined:
    Feb 2, 2008
    #12
    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.
     
  13. thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #13
    Yea I don't understand this. Maybe this is where I got lost in communication. I'm not sure where the problem is:eek:
     
  14. macrumors 68040

    Joined:
    Feb 2, 2008
    #14
    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?
     
  15. thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #15
    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.
     
  16. macrumors 68040

    Joined:
    Feb 2, 2008
    #16
    Ok, but what exactly do you mean by:

    It gives the impression that it erases previous information on your outfile.
     
  17. computerexpert, Mar 1, 2013
    Last edited by a moderator: Mar 1, 2013

    thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #17
    Hehe, sorry. my previous code:
    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.
     
  18. macrumors 68040

    Joined:
    Feb 2, 2008
    #18
    Change back to your previous code.
     
  19. thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #19
    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.
     
  20. macrumors newbie

    Joined:
    Apr 8, 2009
    #20
    I didn't look at any of your code, but note that 11101 - 1101 = 10000.
     
  21. macrumors 603

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #21
    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.
     
  22. computerexpert, Mar 1, 2013
    Last edited: Mar 1, 2013

    thread starter macrumors newbie

    Joined:
    Mar 1, 2013
    #22
    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!
     
  23. macrumors 603

    ArtOfWarfare

    Joined:
    Nov 26, 2007
    #23
    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:

    Code:
    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.
     

Share This Page