Create a gist now

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#define THOUSAND_SEPARATOR ","
#include<iostream> // cin, cout
#include<cmath> // math functions
#include<string> // string functions
using namespace std;
struct digit {
int value;
digit* link;
};
typedef digit* digitPtr; //shortcut for digit pointer type
class bigNumber {
friend istream& operator>> (istream&, bigNumber&);
friend ostream& operator<< (ostream&, const bigNumber&);
friend bigNumber operator+ (const bigNumber&, const bigNumber&);
friend bigNumber operator- (const bigNumber&, const bigNumber&);
friend bigNumber operator* (const bigNumber&, const bigNumber&);
friend int cmp (const bigNumber&, const bigNumber&, bool);
public:
bigNumber();
~bigNumber();
void cleanup();
void trim();
digitPtr getHead() const;
bool addDigit(int);
bool addDigit(int,bool);
int numberOfDigits() const;
bool getSign() const;
bool setSign(bool);
bigNumber& operator= (int);
bigNumber& operator= (const bigNumber&);
bigNumber& operator+= (const bigNumber&);
bigNumber& operator-= (const bigNumber&);
bigNumber& operator*= (const bigNumber&);
private:
digitPtr digit_head;
bool positive; //true = positive, false = negative
};
//Constructor
bigNumber::bigNumber() {
this->digit_head = NULL;
this->positive = true;
}
//Destructor
bigNumber::~bigNumber() {
this->cleanup();
}
//Cleanup all allocated memory for this bigNumber's digits
void bigNumber::cleanup() {
digitPtr digit_current, digit_previous;
digit_current = this->digit_head;
while (digit_current != NULL) {
digit_previous = digit_current->link;
delete digit_current;
digit_current = digit_previous;
}
this->digit_head = NULL;
this->positive = true;
}
//Remove zeros at the beginning of the bigNumber if any
void bigNumber::trim() {
digitPtr digit_current, digit_previous;
digit_previous = NULL;
digit_current = this->getHead();
while (digit_current->link != NULL) {
digit_previous = digit_current;
digit_current = digit_current->link;
}
if (digit_current->value == 0 && digit_previous != NULL) {
digit_previous->link = NULL; //remove the tail digit
delete digit_current;
if (digit_previous->value == 0) this->trim();
}
}
//Return the head of the linked-list digits
digitPtr bigNumber::getHead() const {
return this->digit_head;
}
//Add digit to the linked-list
//Support 2 directions
bool bigNumber::addDigit(int digit_value, bool direction) {
digitPtr digit_new, digit_current;
//Create a digit
digit_new = new digit;
digit_new->value = digit_value;
if (direction == true) {
digit_new->link = this->digit_head; //point new-digit's link back to current head
//Swap current head with the newly created digit
this->digit_head = digit_new;
} else {
digit_new->link = NULL; //point new-digit's link to nothing (as it will be the last digit)
if (this->digit_head == NULL) {
this->digit_head = digit_new; //no digit yet
} else {
digit_current = this->getHead();
//Find the last digit
while (digit_current->link != NULL) {
digit_current = digit_current->link;
}
digit_current->link = digit_new; //the new-digit now become the tail digit
}
}
return true;
}
//A wrapper which adds the digit to the head
bool bigNumber::addDigit(int digit_value) {
return this->addDigit(digit_value,true);
}
//Count the number of digits
int bigNumber::numberOfDigits() const {
digitPtr digit_current;
int count = 0;
digit_current = this->getHead();
while (digit_current->link != NULL) {
count++;
digit_current = digit_current->link;
}
return count;
}
//Return the sign of the bigNumber
bool bigNumber::getSign() const {
return this->positive;
}
//Assign the sign of the bigNumber
bool bigNumber::setSign(bool positive) {
this->positive = positive;
return true;
}
//Assigning with an integer's value
bigNumber& bigNumber::operator= (int i) {
this->cleanup();
this->positive = (i > 0);
i = abs(i);
while (i > 0) {
this->addDigit(i % 10,false);
i /= 10;
}
return *this;
}
//Assigning with an other bigNumber's value
bigNumber& bigNumber::operator= (const bigNumber& theOtherNumber) {
digitPtr digit_current;
if (this != &theOtherNumber) {
this->cleanup();
this->positive = theOtherNumber.positive;
digit_current = theOtherNumber.getHead();
while (digit_current != NULL) {
this->addDigit(digit_current->value,false);
digit_current = digit_current->link;
}
}
return *this;
}
//Self-increasing
bigNumber& bigNumber::operator+= (const bigNumber& theOtherNumber) {
int thisValue, otherValue, currentResult;
digitPtr thisPtr, otherPtr, tmpPtr;
if (this->getSign() == theOtherNumber.getSign()) {
//if 2 numbers have the same sign
//do basic adding
int remember = 0;
thisPtr = this->getHead();
otherPtr = theOtherNumber.getHead();
#ifdef DEBUG
cout << "Calculating: " << *this << " + " << theOtherNumber << endl;
#endif
while (thisPtr != NULL || otherPtr != NULL) {
//Get 2 values
if (thisPtr != NULL) {
thisValue = thisPtr->value;
} else {
thisValue = 0;
}
if (otherPtr != NULL) {
otherValue = otherPtr->value;
} else {
otherValue = 0;
}
//Adding
currentResult = thisValue + otherValue + remember;
#ifdef DEBUG
cout << thisValue << " + " << otherValue << " (+ " << remember << ")";
#endif
if (currentResult > 9) {
remember = currentResult / 10;
currentResult %= 10;
} else {
remember = 0;
}
#ifdef DEBUG
cout << " -> " << currentResult << " (remember: " << remember << ")" << endl;
#endif
//Update our value
if (thisPtr != NULL) {
thisPtr->value = currentResult;
thisPtr = thisPtr->link; //Process to next digit
} else {
this->addDigit(currentResult,false);
}
//Process to next digit
if (otherPtr != NULL) {
otherPtr = otherPtr->link;
} else {
//do nothing
}
}
//Additional check for remembered value
while (remember > 0) {
this->addDigit(remember % 10,false);
remember /= 10;
}
//finised with adding 2 same-sign numbers
} else {
//different sign numbers
int borrow = 0;
bool swapped = false;
bigNumber subtractNumber;
if (cmp(*this,theOtherNumber,false) == -1) {
//*this < theOtherNumber
//swap
subtractNumber = *this;
*this = theOtherNumber;
this->setSign(!this->getSign());
subtractNumber.setSign(!subtractNumber.getSign());
swapped = true;
} else {
subtractNumber = theOtherNumber;
}
thisPtr = this->getHead();
otherPtr = subtractNumber.getHead();
#ifdef DEBUG
cout << "Calculating: " << *this << " + " << subtractNumber << endl;
#endif
while (thisPtr != NULL || otherPtr != NULL) {
//Get 2 values
if (thisPtr != NULL) {
thisValue = thisPtr->value;
} else {
thisValue = 0;
}
if (otherPtr != NULL) {
otherValue = otherPtr->value;
} else {
otherValue = 0;
}
otherValue = 10 - otherValue;
//Subtracting
if (borrow > 0) {
#ifdef DEBUG
cout << thisValue;
#endif
thisValue -= borrow;
#ifdef DEBUG
cout << " = " << thisValue << " (due to borrowed) ";
#endif
}
currentResult = thisValue + otherValue;
#ifdef DEBUG
cout << thisValue << " + " << otherValue << " = " << currentResult;
#endif
if (currentResult > 9) {
currentResult %= 10;
borrow = 0;
} else {
borrow = 1;
}
#ifdef DEBUG
cout << " -> " << currentResult << " (borrow: " << borrow << ")" << endl;
#endif
//Update our value
if (thisPtr != NULL) {
thisPtr->value = currentResult;
thisPtr = thisPtr->link; //Process to next digit
} else {
this->addDigit(currentResult,false);
}
//Process to next digit
if (otherPtr != NULL) {
otherPtr = otherPtr->link;
} else {
//do nothing
}
}
//Assign back the sign if neccessary
if (swapped) {
this->setSign(!this->getSign());
}
//trim number
this->trim();
}
return *this;
}
//Self-decreasing
bigNumber& bigNumber::operator-= (const bigNumber& theOtherNumber) {
bigNumber theOtherNumber_tmp;
theOtherNumber_tmp = theOtherNumber;
theOtherNumber_tmp.setSign(!theOtherNumber.getSign());
*this += theOtherNumber_tmp;
return *this;
}
//Self-multiplying
bigNumber& bigNumber::operator*= (const bigNumber& theOtherNumber) {
int count, i;
digitPtr thisPtr, otherPtr;
bigNumber tmp1, tmp2;
thisPtr = this->getHead();
count = 0;
#ifdef DEBUG
cout << "Calculating: " << *this << " * " << theOtherNumber << endl;
#endif
while (thisPtr != NULL) { //start looping through our digits
tmp2.cleanup();
for (i = 0; i < count; i++) tmp2.addDigit(0,false);
otherPtr = theOtherNumber.getHead();
while (otherPtr != NULL) { //start looping through theOtherNumber digits
tmp2.addDigit(thisPtr->value * otherPtr->value,false); //add the multiplied value to tmp2
otherPtr = otherPtr->link; //process to next digit
}
#ifdef DEBUG
cout << thisPtr->value << " * " << theOtherNumber << " = " << tmp2 << endl;
#endif
tmp1 += tmp2; //add tmp2 back to tmp1
count++;
thisPtr = thisPtr->link;
}
//Assign the sign of the result
//If 2 numbers have the same sign: result will be positive
//Otherwise, it will be negative. Obvious!
tmp1.setSign(this->getSign() == theOtherNumber.getSign()?true:false);
*this = tmp1; //copy tmp1 value
return *this;
}
//Get value from input
istream& operator>> (istream& input, bigNumber& theNumber) {
char tmp;
bool foundNumber = false;
theNumber.cleanup();
while (!input.eof()) {
input.get(tmp);
if (tmp >= '0' && tmp <= '9') {
foundNumber = true;
theNumber.addDigit(tmp - '0');
} else {
if (foundNumber == false) {
//not found number yet, continue
if (tmp == '-') {
theNumber.setSign(false);
}
} else {
//finished with the number, return
if (tmp != ' ') input.putback(tmp);
return input;
}
}
}
}
//Output value
ostream& operator<< (ostream& output, const bigNumber& theNumber) {
digitPtr digit_current;
char tmp[2];
string str;
int digit_count = 0;
digit_current = theNumber.getHead();
tmp[1] = 0;
str = "";
while (digit_current != NULL) {
tmp[0] = char(digit_current->value + '0');
#ifdef THOUSAND_SEPARATOR
if (digit_count > 0 && digit_count % 3 == 0) {
str.insert(0,THOUSAND_SEPARATOR);
}
#endif
str.insert(0,tmp);
digit_current = digit_current->link;
digit_count++;
}
if (str.length() > 0) {
if (theNumber.getSign()) {
//do not display "+" for positive numbers, yet
} else {
output << "-";
}
output << str;
} else {
output << 0;
}
return output;
}
//Adding 2 bigNumbers, call the += function
bigNumber operator+ (const bigNumber& x, const bigNumber& y) {
bigNumber result;
result = x;
result += y;
return result;
}
//Subtrect y from x, call the -= function
bigNumber operator- (const bigNumber& x, const bigNumber& y) {
bigNumber result;
result = x;
result -= y;
return result;
}
//Multiply 2 bigNumber, call the *= function
bigNumber operator* (const bigNumber& x, const bigNumber& y) {
bigNumber result;
result = x;
result *= y;
return result;
}
//Main comparison function
int cmp (const bigNumber& x, const bigNumber& y, bool checkSign) {
digitPtr x_ptr, y_ptr;
bool x_sign, y_sign;
int x_count, y_count, tmp_count, i;
int result;
x_ptr = x.getHead();
y_ptr = y.getHead();
result = 1;
if (checkSign) {
x_sign = x.getSign();
y_sign = y.getSign();
if (x_sign == y_sign) {
if (x_sign == true) {
result = 1;
} else {
result = -1;
}
} else {
if (x_sign == true) {
return 1;
} else {
return -1;
}
}
}
x_count = x.numberOfDigits();
y_count = y.numberOfDigits();
#ifdef DEBUG
cout << "Comparing: " << x << " & " << y << " with checkSign = " << (checkSign?"true":"false") << endl;
cout << "Number of Digits: " << x_count << " & " << y_count << endl;
#endif
if (x_count > y_count) {
return 1 * result; //x > y
} else if (x_count < y_count) {
return -1 * result; //x < y
} else {
tmp_count = x_count;
do {
i = 0;
x_ptr = x.getHead();
y_ptr = y.getHead();
while (i < tmp_count) {
x_ptr = x_ptr->link;
y_ptr = y_ptr->link;
i++;
}
#ifdef DEBUG
cout << "Comparing " << x_ptr->value << " & " << y_ptr->value << endl;
#endif
if (x_ptr->value > y_ptr->value) {
return 1 * result; //x > y
} else if (x_ptr->value < y_ptr->value) {
return -1 * result; //x < y
}
tmp_count--;
} while (tmp_count >= 0);
}
return 0; //x == y
}
//Default comparison function (with checkSign)
int cmp (const bigNumber& x, const bigNumber& y) {
return cmp(x,y,true);
}
//Greater-than comparison
bool operator> (const bigNumber& x, const bigNumber& y) {
return (cmp(x,y) == 1?true:false);
}
//Less-than comparison
bool operator< (const bigNumber& x, const bigNumber& y) {
return (cmp(x,y) == -1?true:false);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment