// CBigInt006.cpp
// 04/30/2004
// Author: AOU
//////////////////////////////////////////////////////////////////////
// include files
//////////////////////////////////////////////////////////////////////
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
#include <time.h>
//////////////////////////////////////////////////////////////////////
// constants
//////////////////////////////////////////////////////////////////////
const int MAX_DIGITS = 5; //artificial limit
const int TEST_COUNT = 20;
const int BASE = 10;
/*
const char *TEST_DATA[] =
{
"0", "1", "12", "123", "1234", "123450", "1234506", "12345067",
"123450670", "1234506708", "1234506708", "Hello", "PSU",
"9", "99", "999", "9999", "99999", "999999", "9999999",
"10", "200", "3000", "40000", "500000", "6000000", "70000000",
"800000000", "9000000000", "1090000000000", "11900000000000",
"129000000000000", "1390000000000000", "14900000000000000"
};
*/
const char *TEST_DATA[] =
{
"0", "+1", "-2", "12", "123", "1234", "123450", "1234506", "12345067",
"+0", "++1", "+Hello", "999"
};
const int TEST_DATA_COUNT = sizeof(TEST_DATA)/sizeof(TEST_DATA[0]);
//////////////////////////////////////////////////////////////////////
// class CDigit
//////////////////////////////////////////////////////////////////////
class CDigit
{
private:
CDigit * _prev;
CDigit * _next;
char _digit;
public:
CDigit(void);
CDigit(char d);
friend class CBigInt;
friend ostream & operator << (ostream &bob, const CDigit &d);
friend ostream & operator << (ostream &bob, const CBigInt &bi);
};
//////////////////////////////////////////////////////////////////////
// class CBigInt
//////////////////////////////////////////////////////////////////////
class CBigInt
{
private:
CDigit * _first;
CDigit * _last;
char _sign;
unsigned long int _size;
void initialize(void);
public:
CBigInt(void);
bool insertDigitToLeft(char d); //2004.04.14
bool insertDigitToRight(char d); //2004.04.19
friend ostream & operator << (ostream &bob, const CBigInt &bi);
void displayR2L(void);
CBigInt(char ch);
bool deleteFirst(void); //2004.04.26
bool deleteLast(void); //2004.04.28
~CBigInt(void); //2004.04.28
int deleteAll(void);
int populate(char ch);
int populate(int n, char sign='+');
int minimize(void);
bool isValid(void);
bool operator ==(const CBigInt &bi2);
bool operator < (const CBigInt &bi2);
bool operator <= (const CBigInt &bi2);
bool operator > (const CBigInt &bi2);
bool operator >= (const CBigInt &bi2);
bool operator != (const CBigInt &bi2);
void displayMinimized(void);
CBigInt(char d[]);
void displayScientific(void);
CBigInt(short int x); // [SHRT_MIN, SHRT_MAX] = [-32767,32767]
CBigInt(unsigned short int x); // [0, USHRT_MAX] = [0, 65535]
CBigInt(long int x); // [LONG_MIN, LONG_MAX] = [-2147483647, 2147483647]
CBigInt(unsigned long int x); // [0, ULONG_MAX] = [0, 4294967295]
void displayWithSeparatorForThousands(void);
CBigInt(const CBigInt &bi);
bool deleteLast(int d=1);
bool deleteFirst(int d=1);
CBigInt operator +(const CBigInt &y);
CBigInt operator -(const CBigInt &y);
CBigInt operator *(const CBigInt &y);
CBigInt operator %(const CBigInt &y);
CBigInt operator /(const CBigInt &y);
public:
};
//////////////////////////////////////////////////////////////////////
// driver function prototypes
//////////////////////////////////////////////////////////////////////
void driver_CDigit_ConstructorDefault(void);
void driver_CBigInt_insertDigitToLeft(void);
void driver_CBigInt_insertDigitToRight(void);
void driver_CBigInt_Constructor_Rand(void);
void driver_CBigInt_deleteFirstDigit(void);
void driver_CBigInt_deleteLastDigit(void);
void driver_CBigInt_destructor(void);
//////////////////////////////////////////////////////////////////////
// void main(void)
//////////////////////////////////////////////////////////////////////
void main(void)
{
srand(time(NULL));
//driver_CDigit_ConstructorDefault();
//driver_CBigInt_insertDigitToLeft();
//driver_CBigInt_insertDigitToRight();
//driver_CBigInt_Constructor_Rand();
//driver_CBigInt_deleteFirstDigit();
//driver_CBigInt_deleteLastDigit();
driver_CBigInt_destructor();
}
//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_destructor(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_destructor(void)
{
cout << "-------------------------\n";
cout << "driver_CBigInt_destructor\n";
cout << "-------------------------\n";
for (int i=0; i<=TEST_COUNT-1; i++)
{
CBigInt *pa;
pa = new CBigInt('d');
cout << "*pa=" << *pa << endl;
delete pa;
cout << "----------------------------------------------------\n";
}
}
/*
while there is a digit in this number
delete it
*/
CBigInt::~CBigInt(void)
{
cout << "Destructor called ";
int n = 0;
while (this->_first != NULL)
{
this->deleteLastDigit();
n++;
}
cout << n << " digits destroyed\n";
}
//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_deleteLastDigit(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_deleteLastDigit(void)
{
cout << "------------------------------\n";
cout << "driver_CBigInt_deleteLastDigit\n";
cout << "------------------------------\n";
for (int i=0; i<=TEST_COUNT-1; i++)
{
CBigInt a('r');
cout << "a=" << a << endl;
a.deleteLastDigit();
cout << "After a.deleteLastDigit();\n";
cout << "a=" << a << endl;
cout << "a="; a.displayR2L(); cout << endl;
cout << "----------------------------------------------------\n";
CBigInt b('d');
cout << "b=" << b << endl;
b.deleteLastDigit();
cout << "After b.deleteLastDigit();\n";
cout << "b=" << b << endl;
cout << "b="; b.displayR2L(); cout << endl;
cout << "----------------------------------------------------\n";
CBigInt c('z');
cout << "c=" << c << endl;
c.deleteLastDigit();
cout << "After c.deleteLastDigit();\n";
cout << "c=" << c << endl;
cout << "c="; c.displayR2L(); cout << endl;
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CBigInt::deleteLastDigit(void)
//////////////////////////////////////////////////////////////////////
/*
Description:
Deletes the last digit
Algorithm:
Possibilities:
size 0, 1, >1
if size = 0 then
return false
else if size =1
delete the digit
first=last=null
size=0
sign=?
return true
else
delete the last digit, and change pointers
size--
return true
end if
\
*/
bool CBigInt::deleteLastDigit(void)
{
if (0==this->_size)
return false;
else if (1==this->_size)
{
delete this->_first;
this->_first = this->_last = NULL;
this->_size = 0;
this->_sign = '?';
return true;
}
else
{
CDigit *p;
p = this->_last;
this->_last = this->_last->_prev;
this->_last->_next = NULL;
delete p;
this->_size--;
return true;
}
}
//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_deleteFirstDigit(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_deleteFirstDigit(void)
{
cout << "-------------------------------\n";
cout << "driver_CBigInt_deleteFirstDigit\n";
cout << "-------------------------------\n";
for (int i=0; i<=TEST_COUNT-1; i++)
{
CBigInt a('r');
cout << "a=" << a << endl;
a.deleteFirstDigit();
cout << "After a.deleteFirstDigit();\n";
cout << "a=" << a << endl;
cout << "a="; a.displayR2L(); cout << endl;
cout << "----------------------------------------------------\n";
CBigInt b('d');
cout << "b=" << b << endl;
b.deleteFirstDigit();
cout << "After b.deleteFirstDigit();\n";
cout << "b=" << b << endl;
cout << "b="; b.displayR2L(); cout << endl;
cout << "----------------------------------------------------\n";
CBigInt c('z');
cout << "c=" << c << endl;
c.deleteFirstDigit();
cout << "After c.deleteFirstDigit();\n";
cout << "c=" << c << endl;
cout << "c="; c.displayR2L(); cout << endl;
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CBigInt::deleteFirstDigit(void)
//////////////////////////////////////////////////////////////////////
/*
Description:
Deletes the first digit
Algorithm:
Possibilities:
size 0, 1, >1
if size = 0 then
return false
else if size =1
delete the digit
first=last=null
size=0
sign=?
return true
else
delete the first digit, and change first
size--
return true
end if
\
*/
bool CBigInt::deleteFirstDigit(void)
{
if (0==this->_size)
return false;
else if (1==this->_size)
{
delete this->_first;
this->_first = this->_last = NULL;
this->_size = 0;
this->_sign = '?';
return true;
}
else
{
CDigit *p;
p = this->_first;
this->_first = this->_first->_next;
this->_first->_prev = NULL;
delete p;
this->_size--;
return true;
}
}
//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_Constructor_Rand(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_Constructor_Rand(void)
{
cout << "-------------------------------\n";
cout << "driver_CBigInt_Constructor_Rand\n";
cout << "-------------------------------\n";
for (int i=0; i<=TEST_COUNT-1; i++)
{
CBigInt a('r');
cout << "a=" << a << endl;
cout << "----------------------------------------------------\n";
CBigInt b('d');
cout << "b=" << b << endl;
cout << "----------------------------------------------------\n";
CBigInt c('z');
cout << "c=" << c << endl;
cout << "----------------------------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// CPosBigInt::CPosBigInt(char ch)
//////////////////////////////////////////////////////////////////////
/*
Purpose: A constructor to create a random big integer
Examples: CPosBigInt x('r'); could give x=667621
Algorithm:
initialize all digits with zeros
set leadingZeros to a random number between 0 and MAX_DIGITS;
do the following for i=leadingZeros to MAX_DIGITS-1
d = random integer between 0 and 9
c = random character betwwe '0' to '9' using d
digits[i] = c
end do
*/
CBigInt::CBigInt(char ch)
{
this->initialize();
if ('r' == ch)
{
int digCount = 1 + rand()%(MAX_DIGITS);
if (rand()%2 == 1)
this->_sign = '+';
else
this->_sign = '-';
for (int i=1; i<=digCount; i++)
{
char c;
c = '0' + rand()%10;
this->insertDigitToRight(c);
//_digits[i] = c;//insert to left or right
}
}
if ('d' == ch)
{
int k = rand()%TEST_DATA_COUNT;
int len = strlen(TEST_DATA[k]);
/*
if the first character is sign then
get the sign and process the rest of the digits
else
set the sign as +
process all the digits
end if
*/
if ('+' == TEST_DATA[k][0] || '-' == TEST_DATA[k][0])
{
this->_sign = TEST_DATA[k][0];
for (int j=1; j<=len-1; j++)
if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
{
this->_sign = '?';
return;
}
for (int i=1; i<=len-1; i++)
this->insertDigitToRight(TEST_DATA[k][i]);
}
else
{
this->_sign = '+';
for (int j=0; j<=len-1; j++)
if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
{
this->_sign = '?';
return;
}
for (int i=0; i<=len-1; i++)
this->insertDigitToRight(TEST_DATA[k][i]);
}
}
if ('z' == ch)
{
// create a random big integer from test data
// with lots of leading and trailing zeros
// Algorithm0:
// initialize
// k = random[0..TEST_DATA_COUNT)
// insert digits from TEST_DATA[k]
// insert random zeros to the left
// insert random zeros to the right
int k = rand()%TEST_DATA_COUNT;
int len = strlen(TEST_DATA[k]);
/*
if the first character is sign then
get the sign and process the rest of the digits
else
set the sign as +
process all the digits
end if
*/
if ('+' == TEST_DATA[k][0] || '-' == TEST_DATA[k][0])
{
this->_sign = TEST_DATA[k][0];
for (int j=1; j<=len-1; j++)
if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
{
this->_sign = '?';
return;
}
for (int i=1; i<=len-1; i++)
this->insertDigitToRight(TEST_DATA[k][i]);
}
else
{
this->_sign = '+';
for (int j=0; j<=len-1; j++)
if (TEST_DATA[k][j] < '0' || TEST_DATA[k][j] >'9')
{
this->_sign = '?';
return;
}
for (int i=0; i<=len-1; i++)
this->insertDigitToRight(TEST_DATA[k][i]);
}
int zL = rand()%10;
for (int i=1; i<=zL; i++)
this->insertDigitToLeft('0');
int zR = rand()%10;
for (i=1; i<=zR; i++)
this->insertDigitToRight('0');
}
}
//////////////////////////////////////////////////////////////////////
// void CBigInt::initialize(void)
//////////////////////////////////////////////////////////////////////
/*
Initializes a big integer with zeros
*/
void CBigInt::initialize(void)
{
this->_sign = '?';
this->_size = 0;
this->_first = NULL;
this->_last = NULL;
}
//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_insertDigitToRight(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_insertDigitToRight(void)
{
cout << "---------------------------------\n";
cout << "driver_CBigInt_insertDigitToRight\n";
cout << "----------------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt bi;
cout << bi << endl;
bi.displayR2L(); cout << endl;
cout << endl;
int k = rand()%TEST_COUNT;
for (int j=1; j<=k; j++)
{
bi.insertDigitToRight('0'+rand()%10);
cout << bi << endl;
bi.displayR2L(); cout << endl;
cout << endl;
}
cout << "--------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CBigInt::insertDigitToRight(char d)
//////////////////////////////////////////////////////////////////////
/*
Inserts a node based on digit d to the left
of big integer.
Examples:
Given: "", 5 => "<-5->"
Given: "<-5->", 6 => "<-5-><-6->"
Algorithm0:
Create a node based on the value of d
insert that node to the left
update the size
Algorithm0:
//Create a node based on the value of d
p = new CDigit
next of p = NULL
digit at p = d
//insert that node to the right
if no digit in the big integer
prev of p = NULL
first = p
last = p
else
prev of p is last
next of last = p
last = p
update the size
size++
*/
bool CBigInt::insertDigitToRight(char d)
{
CDigit * p;
p = new CDigit;
if (NULL == p)
return false;
if ('?'==this->_sign)
this->_sign = '+';//correction
p->_next = NULL;
p->_digit = d;
if (this->_size == 0)
{
p->_prev = NULL;
this->_first = p;
this->_last = p;
this->_size = 1;
}
else
{
p->_prev = this->_last;
this->_last->_next = p;
this->_last = p;
this->_size++;
}
return true;
}
//////////////////////////////////////////////////////////////////////
// void driver_CBigInt_insertDigitToLeft(void)
//////////////////////////////////////////////////////////////////////
void driver_CBigInt_insertDigitToLeft(void)
{
cout << "--------------------------------\n";
cout << "driver_CBigInt_insertDigitToLeft\n";
cout << "--------------------------------\n";
for (int i=1; i<=TEST_COUNT; i++)
{
CBigInt bi;
cout << bi << endl;
bi.displayR2L(); cout << endl;
cout << endl;
int k = rand()%TEST_COUNT;
for (int j=1; j<=k; j++)
{
bi.insertDigitToLeft('0'+rand()%10);
cout << bi << endl;
bi.displayR2L(); cout << endl;
cout << endl;
}
cout << "--------------------------------\n";
}
}
//////////////////////////////////////////////////////////////////////
// bool CBigInt::insertDigitToLeft(char d)
//////////////////////////////////////////////////////////////////////
/*
Inserts a node based on digit d to the left
of big integer.
Examples:
Given: "", 5 => "<-5->"
Given: "<-5->", 6 => "<-6-><-5->"
Algorithm0:
Create a node based on the value of d
insert that node to the left
update the size
Algorithm0:
//Create a node based on the value of d
p = new CDigit
prev of p = NULL
digit at p = d
//insert that node to the left
if no digit in the big integer
next of p = NULL
first = p
last = p
else
next of p is first
first = p
update the size
size++
*/
bool CBigInt::insertDigitToLeft(char d)
{
CDigit * p;
p = new CDigit;
if (NULL == p)
return false;
p->_prev = NULL;
p->_digit = d;
if (this->_size == 0)
{
this->_sign = '+';
p->_next = NULL;
this->_first = p;
this->_last = p;
this->_size = 1;
}
else
{
p->_next = this->_first;
this->_first->_prev = p;
this->_first = p;
this->_size++;
}
return true;
}
//////////////////////////////////////////////////////////////////////
// void CBigInt::displayR2L(void)
//////////////////////////////////////////////////////////////////////
void CBigInt::displayR2L(void)
{
CDigit *p;
cout << "bigInt[" << this->_size << "]=";
p = this->_last;
while (p != NULL)
{
cout << p->_digit;
p = p->_prev;
}
cout << this->_sign;
}
//////////////////////////////////////////////////////////////////////
// ostream & operator << (ostream &bob, const CBigInt &bi)
//////////////////////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const CBigInt &bi)
{
CDigit *p;
bob << "bigInt[" << bi._size << "]=";
bob << bi._sign;
p = bi._first;
while (p != NULL)
{
bob << p->_digit;
p = p->_next;
}
return bob;
}
//////////////////////////////////////////////////////////////////////
// CBigInt::CBigInt(void)
//////////////////////////////////////////////////////////////////////
CBigInt::CBigInt(void)
{
this->initialize();
}
////////////////////////////////////////////////////
////////////////////////////////////////////////////
////////////////////////////////////////////////////
// ostream & operator << (ostream &bob, const CDigit &d)
////////////////////////////////////////////////////
ostream & operator << (ostream &bob, const CDigit &d)
{
bob << d._digit;
return bob;
}
//////////////////////////////////////////////////////////////////////
// void driver_CDigit_ConstructorDefault(void)
//////////////////////////////////////////////////////////////////////
void driver_CDigit_ConstructorDefault(void)
{
CDigit d;
cout << d << endl;
}
//////////////////////////////////////////////////////////////////////
// CDigit::CDigit(void)
//////////////////////////////////////////////////////////////////////
CDigit::CDigit(void)
{
this->_prev = NULL;
this->_next = NULL;
this->_digit = 0;
}
/*
-------------------------
driver_CBigInt_destructor
-------------------------
*pa=bigInt[0]=?
Destructor called 0 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+0
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[2]=+12
Destructor called 2 digits destroyed
----------------------------------------------------
*pa=bigInt[3]=+123
Destructor called 3 digits destroyed
----------------------------------------------------
*pa=bigInt[6]=+123450
Destructor called 6 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+1
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+0
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+1
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+0
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[8]=+12345067
Destructor called 8 digits destroyed
----------------------------------------------------
*pa=bigInt[7]=+1234506
Destructor called 7 digits destroyed
----------------------------------------------------
*pa=bigInt[0]=?
Destructor called 0 digits destroyed
----------------------------------------------------
*pa=bigInt[0]=?
Destructor called 0 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=-2
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[4]=+1234
Destructor called 4 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+1
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[6]=+123450
Destructor called 6 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+1
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[1]=+1
Destructor called 1 digits destroyed
----------------------------------------------------
*pa=bigInt[3]=+999
Destructor called 3 digits destroyed
----------------------------------------------------
Press any key to continue
*/
|