//file CBigInt009.cpp
//date 02/11/2005
//author aou
///////////////////////////////////////////////////////////
//includes
///////////////////////////////////////////////////////////
#include <iostream>
using namespace std;
///////////////////////////////////////////////////////////
//constants
///////////////////////////////////////////////////////////
const int MAX_DIGITS = 50;
const int BASE = 10;
///////////////////////////////////////////////////////////
//class CBigInt
///////////////////////////////////////////////////////////
class CBigInt
{
private:
int _base;
char _sign;
char _digits[MAX_DIGITS];
bool isValid(char s[]);
void retrieveValue(char s[]);
public:
CBigInt(void);//constructor/auto-initializer
void display(void);
void initialize(void);
CBigInt(char s[]); //CBigInt bi("+12345");
void input(void);
void displayMinimized(void);
void add(CBigInt a, CBigInt b, CBigInt &c);
CBigInt add(CBigInt a, CBigInt b);
void add(CBigInt a);
//add(a, b, c);
//add(a, b);
//add(b);
//CBigInt abs(void);
//CBigInt pow(int expo);
};
void test_add(void);
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void main(void)
{
test_add();
/*
CBigInt b;
cout << "b = "; b.display();
CBigInt a("667627001667627001667627001");
cout << "a = "; a.display();
CBigInt c("+667627001667627001667627001");
cout << "c = "; c.display();
CBigInt d("-667627001667627001667627001");
cout << "d = "; d.display();
CBigInt e("667-627001667627001667627001");
cout << "e = "; e.display();
cout << "Enter a big integer " ;
a.input();
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
cout << "Enter a big integer " ;
a.input();
cout << "a = "; a.display();
cout << "a = "; a.displayMinimized();
*/
//cin >> a; a.input();
//cin >> b;
//cin >> c;
//c = a + b; add(a, b, c);
//cout << c; c.display();
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::add(CBigInt a, CBigInt b, CBigInt &c)
{
/*
Description:
c = a+b
Examples:
a=3, b=5, c=a+b=>c=8
Algorithms:
Algorithms0:
if a and b are same base and positive then
carry = 0
from rightmost to leftmost digits do
add digits and carry
put the sum in c
do not forget the carry
end do
*/
int carry = 0;
for (int i= MAX_DIGITS-1; i>=0; i--)
{
int ad = a._digits[i]-48;
int bd = b._digits[i]-48;
int sd = carry + ad + bd;
carry = sd/BASE;
sd = sd%BASE;
c._digits[i] = sd+48;
}
c.display();
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void test_add(void)
{
CBigInt a("123"), b("999"), c, t;
a.display();
b.display();
t.add(a,b,c);
c.display();
}
///////////////////////////////////////////////////////////
// void CBigInt::displayMinimized(void)
///////////////////////////////////////////////////////////
void CBigInt::displayMinimized(void)
{
/*
Description:
This function displays the big integer in minimized form
Examples:
+00000000000000000000000000000000000000000000000123[10]
displays as +123
-00000000000000000000000000000000000000000000000023[10]
displays as -23
Algorithms:
Algorithm0:
display the sign
get the position of first non-zero digit in nz
(take care of all zeros possibility)
for i=nz to MAX_DIGITS-1
display digit[i]
end for
Algorithm1:
display the sign
//get the position of first non-zero digit in nz
//(take care of all zeros possibility)
nz = MAX_DIGITS-1
for i=0 to MAX_DIGITS-2
if digits[i] <> '0' then nz = i, exit for loop
end for
for i=nz to MAX_DIGITS-1
display digit[i]
end for
*/
cout << _sign;
//get the position of first non-zero digit in nz
//(take care of all zeros possibility)
int nz = MAX_DIGITS-1;
for (int i=0; i<=MAX_DIGITS-2; i++)
if (_digits[i] != '0')
{
nz = i;
break;
}
for (i=nz; i<=MAX_DIGITS-1; i++)
cout << _digits[i];
cout << endl;
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::retrieveValue(char s[])
{
/* get big integer from s
assumes that s has a valid number
Algorithm0:
if there is a sign then
get the sign and the remaining digits
else
assume the sign as +ve
get the all the digits
end if
Algorithm1:
if the first digit is + or - then
get the sign from the first digit
get the remaining digits
else
set the sign as +ve
get the all the digits
end if
Algorithm2:
if s[0] is + or - then
sign = s[0]
//get the remaining digits
else
sign = '+'
//get the all the digits
end if
Algorithm3:
if s[0] is + or - then
sign = s[0]
//get the remaining digits
j = MAX_DIGITS-1
for i = length(s)-1 to 1
digits[j] = s[i]
j--
end for
else
sign = '+'
//get the all the digits
j = MAX_DIGITS-1
for i = length(s)-1 to 0
digits[j] = s[i]
j--
end for
end if
*/
if (s[0] == '+' || s[0] == '-')
{
_sign = s[0];
//get the remaining digits
int j = MAX_DIGITS-1;
for (int i = strlen(s)-1; i>=1; i--)
{
_digits[j] = s[i];
j--;
}
}
else
{
_sign = '+';
//get the all the digits
int j = MAX_DIGITS-1;
for (int i = strlen(s)-1; i>=0; i--)
{
_digits[j] = s[i];
j--;
}
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
bool CBigInt::isValid(char s[])
{
/*
check if s has a valid integer
possibilities:
first character is +, -, or a digit 0 to 9
rest of the characters should be 0 to 9
Algorithm0:
if s[0] is not a digit or + or - then
return false
else
if rest of the digits are not 0 to 9 then
return false
else
return true
Algorithm1:
if (s[0] is not a digit) and (s[0] <> '+') and (s[0]<>'-') then
return false
else
if rest of the digits are not 0 to 9 then
return false
else
return true
Algorithm2:
if ((s[0]<'0' or s[0]>'9') and (s[0] <> '+') and (s[0]<>'- ') then
return false
else
for i=1 to strlen(s)-1
if s[i] is not 0 to 9 then
return false
end for
return true
*/
if ((s[0]<'0' || s[0]>'9') && (s[0] != '+') && (s[0] != '-'))
return false;
else
{
for (int i=1; i<=strlen(s)-1; i++)
if (s[i]<'0' || s[i]>'9')
return false;
return true;
}
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::input(void)
{
char s[MAX_DIGITS+2];
cin >> s;
initialize();
if (!isValid(s))
return;
retrieveValue(s);
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
CBigInt::CBigInt(char s[])
{
initialize();
if (!isValid(s))
return;
retrieveValue(s);
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::display(void)
{
cout << _sign;
for (int i=0; i<=MAX_DIGITS-1; i++)
cout << _digits[i];
cout << '[' << _base << "]\n";
}
///////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////
void CBigInt::initialize(void)
{
_base = BASE;
_sign = '+';
for (int i=0; i<=MAX_DIGITS-1; i++)
_digits[i] = '0';
}
///////////////////////////////////////////////////////////
// CBigInt::CBigInt(void)
///////////////////////////////////////////////////////////
CBigInt::CBigInt(void)
{
initialize();
}
/*
Output:
+00000000000000000000000000000000000000000000000123[10]
+00000000000000000000000000000000000000000000000999[10]
+00000000000000000000000000000000000000000000001122[10]
+00000000000000000000000000000000000000000000001122[10]
Press any key to continue
*/
|