DHU programming exercise

9 Long integer addition

1. Problem description
hypothesis 2 An integer of any length x、y Two way linked list A and B Storage , Now it is required to design an algorithm , Realization x+y. The calculation results are stored in the linked list C in .

explain ：

because A and B The output needs to be traversed from beginning to end , When adding, you need to traverse from tail to head , So use a two-way linked list to store .

You can split from the low order of a long integer （4 Bit is a group. , Not more than 9999 Non-negative integer ）, It is stored in the data field of each node of the linked list in turn ; The data field of the header node stores the positive and negative number flag （ Positive or 0：1, negative ：-1）.

2. Enter description
first line ： long integer x

The second line ： long integer y
3. The output shows that
first line ： Formatted long integer x（ Every... From low to high 4 Bit use "," Separate ）

The second line ： Formatted long integer y（ Every... From low to high 4 Bit use "," Separate ）

The third line ： Blank line

In the fourth row ： Single chain list C Traversal result of

The fifth row ： Formatted calculation results （ Every... From low to high 4 Bit use "," Separate ）

（ Input and output are separated by a blank line ）

4. Example
Input
-53456467576846547658679870988098
435643754856985679
Output
-5345,6467,5768,4654,7658,6798,7098,8098
43,5643,7548,5698,5679

5345->6467->5768->4611->2014->9250->1400->2419
-5345,6467,5768,4611,2014,9250,1400,2419
5. Code

#include <iostream>
#include <string> //cin>>s1>>s2;
#include <math.h>
#include<algorithm> // Use reverse() function 
using namespace std;

// The data field of the header node stores the positive and negative number flag （ Positive or 0：1, negative ：-1） head->num=1(0 Or a positive number )
struct node {
            
	int num;
	struct node* pre;
	struct node* next;
};

struct node* create(string s) {
       // Because the linked list is added from the tail to the head , So the results are inserted by head inserting method 

	//1. Create a new header node and initialize 
	struct node* head = new node;
	head->next = NULL;
	head->pre = NULL;

	//2. Calculate the real length of the linked list 
	int len=s.length();

	if (s[len - 1] == '-') {
    
		len = s.length() - 1;
		head->num = -1;
	}
	else {
    
		len = s.length();
		head->num = 1;
	}
	//3. Do addition work ,num Save result values ,cnt Used to control the addition of every four bits 
	int cnt = 0;
	int num = 0;
	for (int i = 0; i < len; i++) {
    

		//num += (int)(s[i] - '0') * (pow(10, cnt) + 0.1);// Change here to num +=(s[i] - '0') * pow(10, cnt);
		num += (s[i] - '0') * pow(10, cnt);
		cnt++;
		if (cnt == 4 || i == len - 1) {
        // When reading 4 Number of reset 

			struct node* p = new node;
			struct node* q = head->next;
			p->num = num;//p Refers to a new node 

			head->next = p;
			p->pre = head;
			p->next = q;
			// In the linked list, except for the head node , There are other nodes 
			if (q)
				q->pre = p;

			cnt = 0;
			num = 0;
		}

	}   
	return head;
}

void display(struct node* head) {
    

	if (head->next) {
      // When data exists 

		if (head->num == -1)
			cout << '-';
		struct node* p = head->next;
		cout << p->num;
		p = p->next;
		while (p) {
    
			printf(",%04d", p->num);
			p = p->next;
		}

	}
	else
		cout << 0; // Note that there is no data to consider here 
}

struct node* add(struct node* num1, struct node* num2) {
       // The addition of two linked lists  , It is similar to the operation of merging linked lists 

	struct node* head = new node;
	head->next = NULL;
	head->pre = NULL;
	
	struct node* p = num1;
	struct node* q = num2;
	
	while (p->next)
		p = p->next;
	
	while (q->next)
		q = q->next;

	//1. Linked list num1,num2 It's not empty 
	while (p != num1 && q != num2) {
              // Traverse from tail to head 

		struct node* t = new node;
		struct node* f = head->next;

		t->num = num1->num*p->num + num2->num*q->num;  //num1->num Representative linked list L1 The symbol of  , num2->num Representative linked list L2 The symbol of  
		//t->num = p->num + q->num; This should not work , because Line ：155 At the beginning of the symbol processing 

		head->next = t;
		t->pre = head;
		t->next = f;
		if (f)
			f->pre = t;

		p = p->pre;
		q = q->pre;
	}
	//2. Linked list num1 Non empty ,num2 It's empty 
	while (p != num1) {
         // Similar to merging ordered tables , The method of header insertion is used for nodes without operation 

		struct node* t = new node;
		struct node* h = head->next;

		t->num = num1->num * p->num;

		head->next = t;
		t->pre = head;
		t->next = h;
		if (h)
			h->pre = t;
		p = p->pre;
	}
	//3. Linked list num2 Non empty ,num1 It's empty 
	while (q != num2) {
    

		struct node* t = new node;
		struct node* o = head->next;

		t->num = num2->num * q->num;

		head->next = t;
		t->pre = head;
		t->next = o;
		if (o)
			o->pre = t;
		q = q->pre;
	}

	//4. Judge whether the final value is positive or negative 
	if (head->next->num > 0)   
		head->num = 1;
	else
		head->num = -1;

	p = head;
	while (p->next)
		p = p->next;
	q = p;//q Point to the end node of the linked list 

	/* It is important to understand the following parts ！！！*/
	//5. Handle carry  p Point to the end of the list , Step forward 
	while (p != head) {
                     //p Point to the end node of the linked list 

		// The key ： Handle carry cases 
		if (p->num * head->num < 0) {
      // Minus one in positive numbers , Negative debit plus 1
			if (head->num > 0) {
     // Positive numbers 
				p->num += 10000;
				p->pre->num -= 1;
			}
			else {
    
				p->num -= 10000;
				p->pre->num += 1;
			}
		}

		p = p->pre; // Traverse from tail to front 
	}
	
	

	//6. Restore the original signed data nodes to the normal form , That is, there are only header nodes head->num==1||head->num==-1 Represents a positive or negative number or 0
	p = head->next;
	while (p) {
    
		p->num = abs(p->num);
		p = p->next;
	}
	//7. Handle carry , Pay attention to and 5 Distinguish 
	//q==head->next Refers to the first data node of the linked list （ Non head node ）
	while (q != head->next) {
              // Carry out carry processing 
		if (q->num >= 10000) {
    
			q->num -= 10000;
			q->pre->num += 1;
		}
		q = q->pre;
	}

	if (q && q->num >= 10000) {
      // When a carry condition occurs 

		struct node* t = new node;
		t->next = q;
		q->pre = t;
		head->next = t;
		t->pre = head;
		t->num = q->num / 10000;
		q->num = q->num % 10000;
	}

	//8. Delete the previous as 0 The node of 
	p = head->next; 
	// The current edge appears 0 Delete this node  
	while (p && p->num == 0) {
    

		p->pre->next = p->next; //p The node point data is 0 , send P The precursor node of the node points to P The successor node of   Handle P Of the precursor node next Point to  

		if (p->next)
			p->next->pre = p->pre; // Handle P The successor node of pre Pointer to 

		p = p->next;
	}
	return head;
};
void display_2(struct node* head) {
    

	if (head->next) {
    
		struct node* p = head->next;

		cout << p->num;
		p = p->next;
		while (p) {
    
			printf("->%04d", p->num);  //%04d Ensure that the data output is in the form of four digits , If it is insufficient, fill zero on the left 
			p = p->next;
		}
		cout << endl;
	}
	else
		cout << 0 << endl;
}

int main() {
    


	string s1, s2;
	struct node *num1, *num2, *c;

	cin >> s1;
	cin >> s2;


	reverse(s1.begin(), s1.end());
	num1 = create(s1);
	display(num1);
	cout << endl;

	reverse(s2.begin(), s2.end());
	num2 = create(s2);
	display(num2);
	cout << endl << endl;

	c = add(num1, num2);

	display_2(c);
	display(c);

	return 0;
}