bignum — реализация большого числа в переполнении стека
Я пытаюсь реализовать Big Number в C ++ со строками.
Сначала я делаю перегрузку оператора для оператора «+», добавление для длины цифры> 3 происходит правильно, но для менее чем 3 дает значение мусора после результата. Я не понимаю, почему это происходит.
Вот мой код
#include<iostream>
#include<cstring>
#define SIZE 100
using namespace std;
class BigNumber
{
char *chNumber;
long nLength,nMaxLength;
public :
BigNumber()
{
nLength = nMaxLength = 0;
Init();
}
BigNumber(long length)
{
nLength = length;
nMaxLength = length;
Init();
}
BigNumber(const char *str,long length)
{
nLength = strlen(str);
nMaxLength = length;
Init();
memset(chNumber,0,sizeof(char));
strncpy(chNumber,str,length);
}
/*** copy constructor **/
BigNumber(const BigNumber &source)
{
nLength = strlen(source.chNumber);
nMaxLength = source.nMaxLength;
if(source.chNumber)
{
Init();
strncpy(chNumber,source.chNumber,nLength);
}
else
chNumber = 0;
}
void Init()
{
chNumber = new char[nMaxLength + 5];
memset(chNumber,0,sizeof(char));
}
~BigNumber()
{
delete[] chNumber;
chNumber = 0;
nLength = 0;
}
char* getNumber()
{
return chNumber;
}
const long size() const
{
return nLength;
}
const long capacity() const
{
return nMaxLength;
}
friend long maxsize(BigNumber &obj1,BigNumber &obj2)
{
return (obj1.size() > obj2.size()) ? obj1.size():obj2.size();
}
friend ostream& operator<<(ostream &out,BigNumber &obj)
{
//out<<"String is "<<obj.chNumber<<" of length "<<obj.nLength
// <<" and max length allocated is "<<obj.nMaxLength;
out<<obj.chNumber;
return out;
}
friend istream& operator>>(istream &in,BigNumber &obj)
{
obj.Init();
in>>obj.chNumber;
obj.nLength = strlen(obj.chNumber);
return in;
}
BigNumber &operator=(const BigNumber &obj)
{
if(this == &obj)
{
return *this;
}
delete[] chNumber;
chNumber = 0;
nLength = strlen(obj.chNumber);
Init();
strncpy(chNumber,obj.chNumber,nLength);
return *this;
}
void operator=(char * str)
{
nLength = strlen(str);
Init();
strncpy(chNumber,str,nLength);
}
friend BigNumber reverse(const BigNumber &obj1)
{
long length = obj1.size();
int m=0;
BigNumber obj2(length+5);
for(int i=length-1;i>=0;--i)
{
obj2.chNumber[m++]=obj1.chNumber[i];
}
obj2.chNumber[m]='\0';
//cout<<obj2.chNumber<<endl;
obj2.nLength = m;
return obj2;
}
friend BigNumber operator+(BigNumber &obj1,BigNumber &obj2)
{
long newLength = maxsize(obj1,obj2);
BigNumber obj3(newLength + 5);
int length1 = obj1.size();
int length2 = obj2.size();
int i,j,carry=0,num,m=0;
for(i=length1-1,j=length2-1; i>=0 || j>=0 ; --i,--j)
{
if(i>=0 && j>=0)
{
num = (obj1.chNumber[i]-'0') + (obj2.chNumber[j]-'0') + carry;
}
else if(i>=0)
{
num = obj1.chNumber[i] - '0' + carry;
}
else if(j>=0)
{
num = obj2.chNumber[j] - '0' + carry;
}
carry = num/10;
num = num%10;
obj3.chNumber[m++] = num+'0';
}
obj3.chNumber[m]='\0';
obj3.nLength = m;
BigNumber obj4 = reverse(obj3);
cout<<obj4<<endl;
return reverse(obj3);
}
};
void test_addition()
{
BigNumber n1("42",3),n2("1",2),n3;
n3 = n1 + n2;
cout<<n3<<endl;
n1 = "123";
n2 = "345";
n3 = n1 + n2;
cout<<n3<<endl;
}
int main()
{
test_addition();
return 0;
}
Перед возвратом из функции operator + () я печатаю сумму, которая дает правильный вывод, а после возврата я печатаю выдачу ненужных значений после результата.
Благодарю вас
Решение
В вашей реализации есть некоторые проблемы, а именно:
- плохое управление памятью
- отсутствующий конструктор копии
operator+не учитывает ненулевойcarryпосле выхода из цикла или учета возможности того, что сумма может иметь большую длину, чем два входных значения.
Попробуйте это вместо этого:
#include <iostream>
#include <cstring>
#include <iomanip>
#define SIZE 100
class BigNumber
{
private:
char *chNumber;
long nLength, nMaxLength;
public :
BigNumber()
{
nLength = nMaxLength = 0;
Init();
}
BigNumber(long initialCapacity)
{
nLength = 0;
nMaxLength = initialCapacity;
Init();
}
BigNumber(const char *str)
{
nLength = nMaxLength = strlen(str);
Init();
memcpy(chNumber, str, nLength);
}
BigNumber(const BigNumber &source)
{
nLength = source.nLength;
nMaxLength = source.nMaxLength;
Init();
memcpy(chNumber, source.chNumber, nLength);
}
void Init()
{
chNumber = new char[nMaxLength + 5];
memset(chNumber, 0, nMaxLength + 5);
}
~BigNumber()
{
delete[] chNumber;
chNumber = 0;
nLength = nMaxLength = 0;
}
const char* getNumber() const
{
return chNumber;
}
const long size() const
{
return nLength;
}
const long capacity() const
{
return nMaxLength;
}
friend long maxsize(const BigNumber &obj1, const BigNumber &obj2)
{
return (obj1.size() > obj2.size()) ? obj1.size(): obj2.size();
}
friend ostream& operator<<(ostream &out, const BigNumber &obj)
{
//out<<"String is "<<obj.chNumber<<" of length "<<obj.nLength
// <<" and max length allocated is "<<obj.nMaxLength;
out << obj.chNumber;
return out;
}
friend istream& operator>>(istream &in, BigNumber &obj)
{
char tmp[SIZE+1];
memset(tmp, 0, SIZE);
in >> setw(SIZE) >> tmp;
obj = tmp;
return in;
}
BigNumber &operator=(const BigNumber &obj)
{
if (this != &obj)
{
delete[] chNumber;
chNumber = 0;
nLength = obj.nLength;
nMaxLength = obj.nMaxLength;
Init();
memcpy(chNumber, obj.chNumber, nLength);
}
return *this;
}
BigNumber& operator=(const char* str)
{
delete[] chNumber;
chNumber = 0;
nLength = nMaxLength = strlen(str);
Init();
memcpy(chNumber, str, nLength);
}
friend BigNumber reverse(const BigNumber &obj1)
{
long length = obj1.size();
int m = 0;
BigNumber obj2(length);
for(int i = length-1; i >= 0; --i)
{
obj2.chNumber[m++] = obj1.chNumber[i];
}
obj2.chNumber[m] = '\0';
//cout << obj2.chNumber << endl;
obj2.nLength = m;
return obj2;
}
friend BigNumber operator+(const BigNumber &obj1, const BigNumber &obj2)
{
long newCapacity = maxsize(obj1, obj2) + 1;
BigNumber obj3(newCapacity);
int length1 = obj1.size();
int length2 = obj2.size();
int carry = 0, num, m = 0;
for(int i = length1-1, j = length2-1; (i >= 0) || (j >= 0); --i, --j)
{
if ((i >= 0) && (j >= 0))
{
num = (obj1.chNumber[i]-'0') + (obj2.chNumber[j]-'0') + carry;
}
else if (i >= 0)
{
num = obj1.chNumber[i] - '0' + carry;
}
else
{
num = obj2.chNumber[j] - '0' + carry;
}
carry = num/10;
num %= 10;
obj3.chNumber[m++] = num+'0';
}
if (carry != 0)
obj3.chNumber[m++] = carry+'0';
obj3.chNumber[m]='\0';
obj3.nLength = m;
return reverse(obj3);
}
};
С учетом сказанного, я настоятельно рекомендую вам изменить свой внутренний буфер, чтобы использовать std::string вместо char[] массив, а также использовать стандартные функции STL вместо написания своих собственных. Это немного упростит реализацию:
#include <iostream>
#include <cstring>
#include <iomanip>
#include <algorithm>
#define SIZE 100
class BigNumber
{
private:
std::string chNumber;
public:
BigNumber()
{
}
BigNumber(const BigNumber &src)
: chNumber(src.chNumber)
{
}
BigNumber(long initialCapacity)
{
chNumber.reserve(initialCapacity);
}
BigNumber(const char *str)
: chNumber(str)
{
}
const char* getNumber() const
{
return chNumber.c_str();
}
const long size() const
{
return chNumber.size();
}
const long capacity() const
{
return chNumber.capacity();
}
friend ostream& operator<<(ostream &out, const BigNumber &obj)
{
//out<<"String is " << obj.chNumber << " of length " << obj.size()
// << " and max length allocated is " << obj.capacity();
out << obj.chNumber.c_str();
return out;
}
friend istream& operator>>(istream &in, BigNumber &obj)
{
char tmp[SIZE+1];
memset(tmp, 0, SIZE);
in >> std::setw(SIZE) >> tmp;
obj = tmp;
return in;
}
BigNumber& operator=(const BigNumber &obj)
{
chNumber = obj.chNumber;
return *this;
}
friend BigNumber operator+(const BigNumber &obj1, const BigNumber &obj2)
{
BigNumber obj3(std::max(obj1.size(), obj2.size())+1);
int length1 = obj1.size();
int length2 = obj2.size();
int carry=0, num;
for (int i = length1-1, j = length2-1; (i >=0) || (j >= 0); --i,--j)
{
if ((i >= 0) && (j >= 0))
{
num = (obj1.chNumber[i] - '0') + (obj2.chNumber[j] - '0') + carry;
}
else if (i >= 0)
{
num = (obj1.chNumber[i] - '0') + carry;
}
else
{
num = (obj2.chNumber[j] - '0') + carry;
}
carry = num / 10;
num %= 10;
obj3.chNumber += ('0'+num);
}
if (carry != 0)
obj3.chNumber += ('0'+carry);
std::reverse(obj3.chNumber.begin(), obj3.chNumber.end());
return obj3;
}
};
void test_addition()
{
BigNumber n1("42"), n2("1"), n3;
n3 = n1 + n2;
std::cout << n3 << std::endl;
n1 = "123";
n2 = "345";
n3 = n1 + n2;
std::cout << n3 << std::endl;
}
int main()
{
test_addition();
return 0;
}
Другие решения