/*************************************
*
* Description: The program can do addition, substraction and multiplication for
* arbitrary large numbers.
* For example, after reading in
* 29384987634765182734
* 18293784765342891872
* *
* the program will print
* 537562639122656557670471733298083338048
*************************************/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
using namespace std;
/**
* 1. Least significant digit is in the right end of the list
* 2. List is implemented as double linked list with dummy head
**/
struct Node{
unsigned digit;
Node* next;
Node* previous;
};
void insertTail(Node* const list, unsigned digit);
void insertHead(Node* const list, unsigned digit);
void removeTail(Node* const list);
Node* constructList(string str);
void printReverse(Node* const list);
Node* large_add(Node* const operand1, Node* const operand2);
Node* large_substract(Node* const operand1, Node* const operand2);
Node* large_multiply(Node* const operand1, Node* const operand2);
void clear(Node* list);
// pre: list is a linked list with dummy head
// post: insert a node to the end of a list
void insertTail(Node* const list, unsigned digit){
Node* old_tail = list->previous;
Node* new_tail = new Node();
//insert the new tail node
new_tail->digit = digit;
new_tail->next = list;
new_tail->previous = old_tail;
//adjust the original tail node
old_tail->next = new_tail;
list->previous = new_tail;
}
// pre: list is a linked list with dummy head
// post: insert a node to the beginning of the list.
void insertHead(Node* const list, unsigned digit){
Node* old_head = list->next;
Node* new_head = new Node();
//insert the new head node
new_head->digit = digit;
new_head->next = old_head;
new_head->previous = list;
//adjust the old head node
old_head->previous = new_head;
list->next = new_head;
}
// pre: list is a linked list with dummy head
// post: remove the last node of the list
void removeTail(Node* const list){
if(list->previous == list)
return;
Node* tail = list->previous;
list->previous = tail->previous;
tail->previous->next = list;
delete tail;
}
// pre: str is the string representing the integer.
// post: construct a list which represents the integer
Node* constructList(string str){
Node* list = new Node();
list->next = list->previous = list;
for(size_t i = 0; i < str.size(); ++i){
unsigned digit = static_cast<unsigned>(str[i] - '0');
insertHead(list, digit);
}
return list;
}
// pre: list is a linked list
// post: print the contents of the list in reversed order.
void printReverse(Node* const list){
Node* p = list->previous;
while(p != list){
cout << p->digit;
p = p->previous;
}
cout << endl;
}
// pre: list is a double linked list
// post: empty the list and release all the memory
void clear(Node* list){
Node* p = list->next;
while(p != list){
Node* tmp = p->next;
delete p;
p = tmp;
}
delete list;
}
// pre: operand1 and operand2 are two linked lists
// post: add two intergers represented as linked list
Node* large_add(Node* const operand1, Node* const operand2){
Node* p1 = operand1->next;
Node* p2 = operand2->next;
Node* sum = new Node();
sum->next = sum->previous = sum;
int carry = 0;
while(p1 != operand1 || p2 != operand2){
int s = 0;
if(p1 == operand1)
s = p2->digit + carry;
else if(p2 == operand2)
s = p1->digit + carry;
else //neither p1 and p2 reaches the end
s = p1->digit + p2->digit + carry;
carry = s / 10;
s %= 10;
insertTail(sum, static_cast<int>(s));
if(p1 != operand1)
p1 = p1->next;
if(p2 != operand2)
p2 = p2->next;
}
if(carry != 0)
insertTail(sum, carry);
return sum;
}
// pre: operand1 and operand2 are two linked lists
// Ensure operand1 >= operand2
// post: substract operand1 from operand2.
Node* large_substract(Node* const operand1, Node* const operand2){
Node* p1 = operand1->next;
Node* p2 = operand2->next;
Node* diff = new Node();
diff->next = diff->previous = diff;
int borrow = 0;
while(p1 != operand1){
int d = 0;
if(p2 == operand2)
d = p1->digit - borrow;
else
d = p1->digit - p2->digit - borrow;
if(d < 0){
d += 10;
borrow = 1;
}else
borrow = 0;
insertTail(diff, static_cast<unsigned>(d));
if(p2 != operand2)
p2 = p2->next;
p1 = p1->next;
}
//remove the zeors at the most significant digits.
while(diff->previous != diff->next && diff->previous->digit == 0)
removeTail(diff);
return diff;
}
// pre: operand1 and operand2 are two linked lists
// post: multiplication of operand1 and operand2
Node* large_multiply(Node* const operand1, Node* const operand2){
Node* p1 = operand1->next;
Node* p2 = operand2->next;
Node* product = new Node();
product->next = product->previous = product;
int digit_num = 0;
while(p1 != operand1){
int carry = 0;
//in each iteration, mutiply one digit of p1 with p2
Node* tmp = new Node();
tmp->next = tmp->previous = tmp;
while(p2 != operand2){
int d = p1->digit * p2->digit + carry;
carry = d / 10;
d %= 10;
insertTail(tmp, static_cast<int>(d));
p2 = p2->next;
}
if(carry != 0)
insertTail(tmp, carry);
for(int i = 0; i < digit_num; ++i)
insertHead(tmp, 0);
//add the tmp result.
Node* sum = large_add(product, tmp);
clear(product);
product = sum;
p1 = p1->next;
p2 = operand2->next;
++digit_num;
}
return product;
}
int main(){
string filename;
cin >> filename;
ifstream in(filename.c_str());
if(in.fail())
return 0;
string str1, str2;
while(getline(in, str1)){
if(str1 == "") //blank line
continue;
Node* operand1 = constructList(str1);
in >> str2;
Node* operand2 = constructList(str2);
char op;
in >> op;
Node* result;
switch(op){
case '+':{
result = large_add(operand1, operand2);
printReverse(result);
break;
}
case '-':{
//test whether the result is negative;
bool negative = false;
if(str1.size() < str2.size())
negative = true;
else if(str1.size() == str2.size() && (str1 < str2))
negative = true;
if(negative){ //swap these two operands
Node* tmp;
tmp = operand1;
operand1 = operand2;
operand2 = tmp;
}
result = large_substract(operand1, operand2);
if(negative)
cout << '-';
printReverse(result);
break;
}
case '*':{
result = large_multiply(operand1, operand2);
printReverse(result);
break;
}
default:
break;
}
clear(operand1);
clear(operand2);
clear(result);
}
return 0;
}