C++ Hexadecimal Calculator Multiplication

Question

I'm having issues where my multiplication method is only handling one row, it's currently not advancing to the next row. The add function is working properly, and I'm able to update the current hex number, but for some reason I can only get one line of multiplication to work.

Example input:
111# * 333# = 333
123# * 123# = 369

Here is the code in question:

    LList* Calculator::multiply(LList& left, LList& right) {
    int product, carry = 0, lval = 0, rval = 0, zeros = 0;
    bool calculating = true;
    listnode *leftNode;
    vector <LList*> addList;
    listnode *rightNode;
    LList* newHex;
    while(calculating) {

        leftNode = left.next();
        if(leftNode == NULL) {
            break;
        }
        else {
            lval = leftNode->data;
        }


        //leftNode = left.next();
        right.reset();

        if(leftNode == NULL) {
            calculating = false;
            if(carry != 0) {
                //newHex->insertTail(carry);
            }
            lval = 0;
            break;
        }

        LList* curList = new LList;
        addList.push_back(curList);

        while(rightNode != NULL) {

            // Add however zeros we need for
            // each entry based on the zero counter
            for(int i = 0; i < zeros; i++) {
                curList->insertTail(0);
            }

            rightNode = right.next();


            if(rightNode == NULL) {

            } 
            else {
            rval = rightNode->data;

            product = lval * rval + carry;
            carry = 0;
            if(product >= 16) {
                carry = (product / 16);
                product = (product % 16);
            }
            curList->insertTail(product);
            }
        }
        zeros++;


    }

    Calculator calc;
    LList* temp;
    // Add up everything in the addList
    for(int i = 0; i < addList.size() - 1; i++) {
        if(temp == NULL)
            temp = calc.add(*addList[i], *addList[i+1]);
        else
            temp = calc.add(*addList[i+1], *temp);
    }

    newHex = temp;

    // Delete it
    for(int i = 0; i < addList.size(); i++) {

    }

    return newHex;
};

Here is the next method:

listnode* LList::next() {
    listnode* temp = view;
    if(temp != NULL)
        view = view->next;

    if(view == NULL) {
    }
    return temp;
};

FUll PROGRAM:

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <string>
using namespace std;
#undef NULL
const int NULL = 0;
const char SENTINEL = '#';
typedef int element;

class listnode {
    public:
        element data;
        listnode * next;
};

class LList {
    private:
        listnode * head;
        listnode * tail;
        listnode * view;

    public:
        LList();
        ~LList();
        void read();
        listnode* next();
        void reset();
        void print();
        void insertTail(element val);
        void clean();

        element deleteHead();
};

class Calculator {
    public:
        Calculator();
        inline LList* add(LList& left, LList& right);
        inline LList* multiply(LList& left, LList& right);
};

Calculator::Calculator() {

};

LList* Calculator::add(LList& left, LList& right) {
    int sum, carry = 0, lval = 0, rval = 0;
    bool calculating = true;
    listnode *leftNode;
    listnode *rightNode;
    LList* newHex = new LList;
    while(calculating) {
        leftNode = left.next();
        rightNode = right.next();

        if(leftNode == NULL) {
            lval = 0;
        }
        else
            lval = leftNode->data;

        if(rightNode == NULL) {
            rval = 0;
        }
        else
            rval = rightNode->data;


        if(leftNode == NULL && rightNode == NULL) {
            calculating = false;
            if(carry != 0) {
                newHex->insertTail(carry);
            }
            break;
        }

        sum = lval + rval + carry;
        carry = 0;
        if(sum >= 16) {
            carry = 1;
            sum -= 16;
        }

        newHex->insertTail(sum);

    }

    return newHex;
};


LList* Calculator::multiply(LList& left, LList& right) {
    int product, carry = 0, lval = 0, rval = 0, zeros = 0;
    bool calculating = true;
    listnode *leftNode;
    vector <LList*> addList;
    listnode *rightNode;
    LList* newHex;
    while(calculating) {

        leftNode = left.next();
        if(leftNode == NULL) {
            break;
        }
        else {
            lval = leftNode->data;
        }


        //leftNode = left.next();
        right.reset();

        if(leftNode == NULL) {
            calculating = false;
            if(carry != 0) {
                //newHex->insertTail(carry);
            }
            lval = 0;
            break;
        }

        LList* curList = new LList;
        addList.push_back(curList);

        while(rightNode != NULL) {

            // Add however zeros we need for
            // each entry based on the zero counter
            for(int i = 0; i < zeros; i++) {
                curList->insertTail(0);
            }

            rightNode = right.next();


            if(rightNode == NULL) {

            } 
            else {
            rval = rightNode->data;

            product = lval * rval + carry;
            carry = 0;
            if(product >= 16) {
                carry = (product / 16);
                product = (product % 16);
            }
            curList->insertTail(product);
            }
        }
        zeros++;


    }



    Calculator calc;
    LList* temp;
    // Add up everything in the addList
    for(int i = 0; i < addList.size() - 1; i++) {
        if(temp == NULL)
            temp = calc.add(*addList[i], *addList[i+1]);
        else
            temp = calc.add(*addList[i+1], *temp);
    }

    newHex = temp;

    // Delete it
    for(int i = 0; i < addList.size(); i++) {

    }

    return newHex;
};

listnode* LList::next() {
    listnode* temp = view;
    if(temp != NULL)
        view = view->next;

    if(view == NULL) {
    }
    return temp;
};

void LList::reset() {
    view = head;
}


LList::LList(){
    /*
    next:
    This is used to set the linked
    list to NULL.
    */
    head = NULL;
    view = NULL;
};


void LList::print() {
    listnode * temp;
    int i = 0;
    string printValues;
    temp = head;
    while(temp != NULL) {
        int var = temp -> data;
        char character = ' ';
        if(i % 3 == 0 && i != 0)
            printValues += ',';
        i++;    
        if(var > 9 && var < 16) {
            character = static_cast <char>(var + 65 - 10);
        };
        if (var <= 9 && var >= 0) {
            character = static_cast <char>(var + 48);
        };
        if (var > 96 && var < 103) {
            character = static_cast <char>(var + 97 + 10);
        };

        printValues += character;
        temp = temp -> next;

    }
    string tempValues;
    for(int i = printValues.length() - 1; i >= 0; i--)
        tempValues += printValues[i];
    cout << tempValues;
    cout << endl;
};

 void LList::read() {
    string userval;
    int i;
    bool parsing = true;
    char curval;
    vector <int> values;
    clean();
    while(parsing) {
        cin >> userval;
        for(unsigned int i = 0; i < userval.length(); i++) {
            curval = userval[i];    
            if(curval >= 48 && curval <= 57)
                values.push_back(static_cast <int>(curval - 
            48));

            if(curval >= 65 && curval <= 70)
                values.push_back(static_cast <int>(curval - 
            65 + 10));

            if(curval >= 97 && curval <= 102)
                values.push_back(static_cast <int>(curval - 
            97 + 10)); 

            if(curval == ' ')
                break;

            if(curval == SENTINEL) {
                parsing = false;
                break;
            }   
        }
    }
    for(int i = values.size() -1; i >= 0; i--) {
        insertTail(values[i]);
    }
}; 

void LList::insertTail(element val) {
    listnode * temp;
    temp = new listnode;
    temp -> data = val;
    temp -> next = NULL;

    if(head == NULL) {
        head = temp;
        view = head;
    }
    else
        tail -> next = temp;
    tail = temp;
};

void LList::clean() {
    while(head != NULL)
        deleteHead();
};

void validCommands() {
    cout << "Valid commands are:" << endl;
    cout << "  e enter  enter the current ";
    cout << "hexadecimal ";
    cout << "number from the keyboard" << endl;
    cout << "  a add        add a new hexadecimal ";
    cout << "number to the current hex. number" << endl;
    cout << "  m multiply   ";
    cout << "multiply a new hexadecimal number ";
    cout << "by the current hex. number" << endl;
    cout << "  h help   show this help menu" << endl;
    cout << "  q quit   quit the program" << endl << endl;
};

element LList::deleteHead() {
    listnode * temp;
    temp = head;
    head = head -> next;
    delete temp;
    return temp -> data;
};

LList::~LList(){
    delete head;
};

int main() {
    LList L, add,multiply;
    Calculator calc;
    L.insertTail(0);
    char option;
    bool run;
    cout << "Hexadecimal Calculator, Ver 1.0.0 \n";



    do {
        /*
    This do while is used to continuosly run the 
    program until the user decides to end.
    */
    cout << "Current Hexadecimal number is: ";
    L.print();
    cout << endl;

    cout << "Command (h for help): ";
    cin >> option;

    cout << endl << endl;
        switch(option) {
            case 'e' : 
                cout << "Enter a hexadecimal number ";
                cout << "followed by #: ";
                L.read();
                cout << endl << "Entering completed.";
                cout << endl << endl;
            break;
            case 'a' :  
                cout << "Adding a new hexadecimal number ";
                cout << "to the current hex. number" << endl;
                cout << endl;
                cout << "Enter a hexadecimal ";
                cout << "number, follow by #: ";
                add.read();
                cout << endl << "Addition completed.";
                cout << endl;
                L = *calc.add(L, add);
                cout << endl;
                break;
            case 'm' : 
                cout << "Multiplying a new hexadecimal ";
                cout << "number ";
                cout << "to the current hex. number" << endl;
                cout << endl;
                cout << "Enter a hexadecimal ";
                cout << "number, follow by #: ";
                multiply.read();
                cout << endl << "Multiplication completed.";
                cout << endl;
                L = *calc.multiply(L, multiply);
                cout << endl;
                break;
            case 'h' : validCommands();
            break;
            case 'q' : run = false;
            break;
        };
    } while (run);
        exit(0);

}

Answer 1

The first evaluation of while(rightNode != NULL) uses an uninitialized value for rightNode, which happens to be non-NULL when you run the program. After this check, before it is dereferenced, rightNode is set to a valid node pointer value from right.next(). But for the next left digit, rightnode is still NULL from the previous loop, because it is not updated after right.reset(), so for every digit after the first, while(rightNode != NULL) always starts off with rightNode set to NULL, so all loops after the first one are skipped.

Once this is fixed, another bug will be exposed: zeros are added to curList inside the right-digit loop, so the zeros get added whenever a right-digit is processed. Instead the zeros should be added before the right-digit loop, after curList is created within the left-digit loop.

There is another bug (I think) -- after the right-digit loop ends, any carry value is not added to the last digit of curList -- instead it gets saved for the beginning of the next right-digit loop. This might be intentional, but I don't think it will always end up in the correct digit position (but maybe I'm wrong on this point -- I haven't dedicated much thought to the possibilities).

For debugging your problem, I had to duplicate your code, fill in missing parts and fix the bugs. Also, there were some style issues which are not actual mistakes or bugs, but are known to promote problems. So here are changes I made to my version for testing:

• LList contains a stateful iterator (view) accessed with next() and reset(). In the future, multiple sections of your code might want to iterate over the same LList, at the same time, but they will not be able to share the single iteration state held by the LList object. Iterator objects solve this problem.

• Use of raw pointers in "user" code: Pointer manipulation should be avoided, if possible, or restricted to "library" code -- like within the LList object. There is no need to handle pointers inside the Calculator class.

• Variables should be declared inside the innermost scope required for their use. The code's first problem, where rightNode was carrying a value over from a previous loop, could not have happened if this style point was being followed.

• There was no need to keep a vector (addList) of terms to sum up at the end of the function. My version keeps a running sum as the LList named prodSum.

Here is my version of the code, including my own LList and Calculator::add, because you did not make those available. Note that LList works with iterators here, not a view member. My iterators can be "dereferenced" when at their end position, giving a zero. This was done for convenience, because an infinite string of high-order zeros above the highest digit is implied for any value:

#include <iostream>
#include <string>
#include <vector>

struct listnode {
    int data;
    listnode *next;
    listnode(int data=0) : data(data), next(0) {}
};

class LList {
    listnode *head, *tail;  // head is least significant end
    void delNodes() {
        listnode* node = head;
        while(node) {
            listnode* todel = node;
            node = node->next;
            delete todel;
        }
        head = tail = 0;
    }
public:
    LList() : head(0), tail(0) {}
    LList(std::string digits) : head(0), tail(0) {
        for(auto it = digits.rbegin(); it != digits.rend(); ++it) {
            if(*it >= '0' && *it <= '9') insertTail(*it - '0');
            else if(*it >= 'a' && *it <= 'f') insertTail(*it - 'a' + 10);
            else if(*it >= 'A' && *it <= 'F') insertTail(*it - 'A' + 10);
    }   }
    LList(const LList& src) : head(0), tail(0) {
        for(int data : src) { insertTail(data); }
    }
    ~LList() { delNodes(); }
    LList& operator = (const LList& src) {
        delNodes();
        for(int data : src) { insertTail(data); }
        return *this;
    }
    void insertTail(int value) {
        listnode *newnode = new listnode(value);
        if(!head) {
            head = tail = newnode;
        } else {
            tail->next = newnode;
            tail = newnode;
    }   }
    class iterator {
        friend LList;
        const listnode* node;
        iterator(const listnode* node) : node(node) {}
    public:
        iterator& operator ++ () { if(node) node = node->next; return *this; }
        int operator * () const { return node ? node->data : 0; }
        bool operator != (iterator iter) const { return iter.node != node; }
        bool operator == (iterator iter) const { return iter.node == node; }
    };
    iterator begin() const { return iterator(head); }
    iterator end()   const { return iterator(0); }
    std::string get_digits() const {
        static const char da[] = "0123456789abcdef";
        std::string digits;
        for(int d : *this) {
            digits = da[d] + digits;
        }
        return digits;
    }
};

LList add(const LList& left, const LList& right) {
    LList sum;
    auto liter = left.begin();
    auto riter = right.begin();
    int carry = 0;
    while(liter != left.end() || riter != right.end()) {
        int s = *liter + *riter + carry;
        carry = s / 16;
        sum.insertTail(s % 16);
        ++liter;
        ++riter;
    }
    if(carry) sum.insertTail(carry);
    return sum;
}

LList multiply(const LList& left, const LList& right) {
    LList prodSum;
    auto leftNode = left.begin();
    int zeros = 0;
    for(;;) {
        if(leftNode == left.end()) break;
        int lval = *leftNode;
        LList curList;
        for(int i = 0; i < zeros; i++) {
            curList.insertTail(0);
        }
        auto rightNode = right.begin();
        int carry = 0;
        while(rightNode != right.end()) {
            int rval = *rightNode;
            int product = lval * rval + carry;
            carry = product / 16;
            product %= 16;
            curList.insertTail(product);
            ++rightNode;
        }
        while(carry) {
            curList.insertTail(carry % 16);
            carry /= 16;
        }
        prodSum = add(prodSum, curList);
        ++leftNode;
        ++zeros;
    }

    return prodSum;
}

int main() {
    LList a("111");
    LList b("333");
    LList c = multiply(a, b);  // 36963
    std::cout << c.get_digits() << '\n';
}