Multiplication and Addition for Doubly Linked List

[thuynh97]

I am attempting to make infinite arithmetic calculator for multiplication and addition. I tried about everything including divide and conquer for writing the operator overloads. I need tips!

This is the header file for a program that would read stuff in a text file and answer it.
TextFile:
0*0
0+1
123456*2593
2*2000000000000000
2*3
1+10
10000000000000000+1
1234567890123456789+8765432109876543210
999999999999999999999+1

  #include <string>
#include <vector>
struct Node
{
	long data;
	Node* prev;
	Node* next;
	Node(long x)
	{
		data = x;
		next = prev = NULL;
	}
};
class DoubleLinkedList
{
	friend long mult(DoubleLinkedList n1, DoubleLinkedList n2);
private:
	Node* head;
	Node* tail;
	int m_digitsPerNode, size = 0;
public:
	DoubleLinkedList()
	{
		head = tail = NULL;
	}
	~DoubleLinkedList()
	{
		while (head)
		{
			Node* temp = head;
			head = head->next;
			delete temp;
		}
	}
	DoubleLinkedList(const DoubleLinkedList& list) 
	{
		Node *temp = (Node*)malloc(sizeof(Node));
		temp = list.head;
		do
		{
			insertAtTail(temp->data);
		} while ((temp = temp->next) != NULL);

	}
	DoubleLinkedList(const std::string& num, int digitsPerNode)
	{
		m_digitsPerNode = digitsPerNode;
		int c1 = num.length() / digitsPerNode;
		int c2 = num.length() % digitsPerNode;
		if (c2)
		{
			string strl = num.substr(0, c2);
			insertAtTail(stoi(strl));
		}
		for (int i = 0; i < c1; i++)
		{
			string strl = num.substr(c2+i*digitsPerNode, digitsPerNode);
			insertAtTail(stoi(strl));
		}
	}
	Node* createNode(long x)
	{
		Node *newNode = (Node*)malloc(sizeof(Node));
		newNode->data = x;
		newNode->prev = NULL;
		newNode->next = NULL;
		size++;
		return newNode;
	}
	void insertAtHead(long x)
	{
		Node* newNode = createNode(x);
		if (head == NULL)
		{
			head = newNode;
			return;
		}
		head->prev = newNode;
		newNode->next = head;
		head = newNode;
	}
	void insertAtTail(long x)
	{
		Node* newNode = createNode(x);
		if (head == NULL)
		{
			head = newNode;
			return;
		}
		Node* temp = head;
		while (temp->next != NULL) 
		{
			temp = temp->next;
		}
		newNode->prev = temp;
		temp->next = newNode;

	}
	void print()
	{
		Node* temp = head;
		printf("Forward:  ");
		while (temp != NULL)
		{
			cout << temp->data << " ";
			temp = temp->next;
		}
		printf("\n");
	}
	const Node* GetHead() const 
	{
		return head;	
	}
	const Node* GetTail() const
	{
		return tail;
	}
	string toString(int digitsPerNode)
	{
		string res = "";
		Node *cur = head;
		if (!cur)
			return res;
		while (cur)
		{
			string numstr = to_string(cur->data);
			int l = numstr.length();
			for (int i = 0; i < digitsPerNode - 1; i++)
				res += "0";
			res += numstr;
		}
		return res;
	}
	DoubleLinkedList operator+(const DoubleLinkedList& list);
	DoubleLinkedList operator*(const DoubleLinkedList& list);
};

[dhayden]

Why are you using a list? I'd use a vector instead with item 0 being the least significant digit and item N being the most significant. That way you have easy access to any digit you want.

[thuynh97]

Why are you using a list? I'd use a vector instead with item 0 being the least significant digit and item N being the most significant. That way you have easy access to any digit you want.

I am using a list because it is the required data structure for the given assignment.

[jonnin]

what exactly do you mean by add and multiply? Are the lists the same size, and is it a simple (in array terms for easy of reading)
L3[0] = L1[0] + L2[0] and L3[0] = L1[0] * L2[0]

??

or X*L1 (X * every item in the list)

or some sort of inner/outer/vector multiplication thing?

or is it store the whole text file FIRST then do each requested function on the numbers provided??

[thuynh97]

what exactly do you mean by add and multiply? Are the lists the same size, and is it a simple (in array terms for easy of reading)
L3[0] = L1[0] + L2[0] and L3[0] = L1[0] * L2[0]

??

or X*L1 (X * every item in the list)

or some sort of inner/outer/vector multiplication thing?

or is it store the whole text file FIRST then do each requested function on the numbers provided??

The user inputs the number of digits per node and the program reads a whole line like the file above and places a = separator then the answer.

digitsPerNode = 3
carry = 0

Addition:

123 456 789
+ 987 654 321
carry 1 1 1 0
----------------------------
1 111 111 110


Multiplication:

123 456 789
* 987 654 321
----------------------------
123 456 789
* 321
carry 146 253 0
----------------------------
list1 39 629 629 269

+ 123 456 789
* 654 000
carry 298 359 0
----------------------------
list2 80 740 583 784 000


+ 123 456 789
* 987 000 000
list3 xxxxxxxxx 000 000
----------------------------
result = list1 + list2 + list3

*A program using arrays to store long numbers will receive a failing
grade (below 50). However, arrays for parameters or other auxiliary variables are acceptable.

[jonnin]

lets get + to work.

The list already killed performance, so you could be one of "those" students and define all the others in terms of addition (multiply is add N times, subtract is add negative, division is repeated subtraction)

that aside, lets get + to work.

I think you have the right idea. You need to right justify, or in other words, work from the least significant digits up the chain.

so lets talk math.

I am pretty sure you can do this 1 digit at a time, and should. say you have

12345
and
12845

and group by 3.

5+5 is 10, that's 0 carry the 1. This is digit #1, we don't need to show this carry.

4+4 is 8, +1 carried is 9, carry 0, this is digit 2 and we don't care.

8+3 is 11 + 0 is 1, carry the 1. This is digit 3, show this carry!

... and so on.

that is logically the same as adding
345
845

and showing
1190 = 190 carry the 1, right?

Does this help you to see what to do??

[thuynh97]

I am seeing what to do but am unsure how to implement it as a function or operator+.

So would I do

	Node* add(DoubleLinkedList n1, DoubleLinkedList n2)
	{
		Node *l1, *l2, *temp, *res, *prev = NULL;
		DoubleLinkedList *resultant = NULL;
		int carry = 0, sum;
		l1 = n1.tail;
		l2 = n2.tail;
		while (l1 != NULL || l2 != NULL)
		{
			sum = carry + (l1 ? l1->data : 0) + (l2 ? l2->data : 0);
			carry = (sum >= 10^(m_digitsPerNode-1)) ? 1 : 0;
			sum = sum % 10 ^ (m_digitsPerNode-1);
			temp = createNode(sum);
			if (res == NULL)
				res = temp;
			else
				prev->next = temp;
			prev = temp;
			if (l1) l1 = l1->next;
			if (l2) l2 = l2->next;
		}
		if (carry > 0)
			temp->next = createNode(carry);
		return res;
	}

This is most likely completely wrong. This assignment is due tonight so I'm kind of brain dead for spending so long on it.

[jonnin]

style. I *highly* recommend you replace l1 and l2 with just about anything else. it looks like 11 and 12 in many fonts. Also, the :? statements are frowned upon in most code. I like them too, but most programmers can't read this, esp non c coders used to java or c-ish languages.

general: if you are burnt looking at it too long, take 30 min away. Youll do better when you get back. Better to break and come back than to keep making more bugs and get more frustrated.

are you into operator overloading?

looks like

classname& operator+ (classname&a);

classname& classname::operator+ (classname&a)
{
classname cnvar; //if we cared about performance this might be a private class member.
/// do the work
return cnvar;
}


it looks OK without digging into it. Try to run it with some simple numbers to see if it works... if not, what did you get.... the bad answer is a clue to the error. Try 0+0, 1+1, 19 + 21, etc ... start small, see if it works for anything, and if it breaks, where does it break...

[mbozzi]

Also ternary-if expressions are frowned upon in most code ... most programmers can't read this, esp. non-C coders used to Java or C-like languages.

I've never heard that one before. Both C and Java support triadic-if.

I think that the assertion "most programmers can't read ?:, so they should be avoided" is an awful suggestion for two reasons:
1. "most programmers can't read this" is apparently a fabrication; and
2. if a programmer doesn't understand ?: they're welcome to go look it up before reasoning about a program they don't understand.

Readability is a concern but being too lazy to look up semantics is an entirely different issue.

Edit:
Also
classname cnvar; //if we cared about performance this might be a private class member.
Why? This seems counter-intuitive.

@OP:
Be careful with (sum >= 10^(m_digitsPerNode-1)) ? 1 : 0;

^ is not exponentiation, but bitwise XOR.
Also the pattern
(expr)? 1: 0 is equivalent in this context to static_cast<bool>(expr) or !!(expr) assuming built-in operator!.

[dhayden]

Ouch. This is a tough assignment for beginners. You have to manage a doubly linked list and you have to program variable length arithmetic. Both are tough.

Looking at your original code:
Delete line 37. It just leaks memory.
Lines 37 and 47: you have to initialize all the members of DoubleLinkedList.
Lines 63-66: Don't use malloc. Use Node's constructor:
Node *newNode = new Node(x);
Line 75: You also must set tail.
Line87: You also muset set tail.
Lines 90-96: One point of having the tail pointer is that you can insert there quickly.
Line 118: don't pass digitsPerNode. The list already has that value.

As for arithmetic:
It looks like the head of the list is the most significant digit. You should state that.

			carry = (sum >= 10^(m_digitsPerNode-1)) ? 1 : 0;
			sum = sum % 10 ^ (m_digitsPerNode-1);

^ isn't the exponentiation operation. You must use pow() instead. I suggest that you create a private data member to hold pow(10,m_digitsPerNode) and set it in the constructor.

Do you have to handle negative numbers?? That will add a whole different level of pain.

[jonnin]

Edit:
Also
classname cnvar; //if we cared about performance this might be a private class member.
Why? This seems counter-intuitive.

------
If you do a LOT of math on the same objects, this keeps it around instead of allocating it every time. Similar to static. Creating a full bore object each time you add in a loop for example would be sluggish. If on the other hand you create and destroy a bunch of the things, its worse. Granted, here, its a LL and already sluggish due to excessive (by requirement) pointer manipulations.

I agree with you about :?; as I said, I like it myself. I am not making it up, the last 2 places I wrote C++ explicitly said not to do it in their standards due to readability. I thought it was dumb too, but it bothers someone out there.

[dhayden]

Regarding ?:, I use it when it make sense, which mostly means places where you'd otherwise say if (condition) var = val1; else var = val2;
To increase readability, I usually but it on multiple lines:

var = (condition ?
       val1 :
       val2);

For really simple expressions like this I might put it on one line, but with anything more complex, multiple lines makes it really clear.

The parentheses help with readability, but I mostly use them to help with auto-indenting in my editor.

[mbozzi]

this keeps it around instead of allocating it every time

You're right, but when you return a local variable you can eliminate a copy. I think this needs to be measured in context.
http://en.cppreference.com/w/cpp/language/copy_elision