To gain experience of using STL containers and iterators. Modify the BigInt clas
ID: 667203 • Letter: T
Question
To gain experience of using STL containers and iterators.
Modify the BigInt class by
adding the > operation to determine whether one BigInt object is bigger than another.
adding the subtraction operation - to class BigInt: int1 - int2 which should return 0 if int1 is less than int2.
(Bonus) adding the multiplication operation * to class BigInt.
the BigInt.cpp------
---------------------------------------------------------------------------------------------------------------------------------------------------------
the BigInt.H
----------------------------------------------------------------------------------------------------------------------------------------------------------------
This test run cpp should work for the program to work--
----------------------------------------------------------------------------------------------------------------------------------------------------------------
The Sample run looks like this --
Enter a big integer:
Enter 3-digit blocks, separated by spaces.
Enter a negative integer in last block to signal the end of input.
347 965 434 213 -1
Enter another big integer:
298 432 678 984 -1
The sum of
347,965,434,213 + 298,432,678,984
is
646,398,113,197
The bigger number of
347,965,434,213
and
298,432,678,984
is
347,965,434,213
The subtraction of
347,965,434,213 - 298,432,678,984
is
49,532,755,229
BONUS part:
The multiplication of
347,965,434,213 * 298,432,678,984
is
103,844,256,726,016,399,679,592
Add more integers (Y or N)? Y
Enter a big integer:
453 213 345 -1
Enter another big integer:
892 -1
The sum of
453,213,345 + 892
is
453,214,237
The bigger number of
453,213,345
and
892
is
453,213,345
The subtraction of
453,213,345 - 892
is
453,212,453
BONUS part:
The multiplication of
453,213,345 * 892
is
404,266,303,740
Add more integers (Y or N)? N
Press any key to continue
------------------------------------------------------------------------------------------------------------------------------------------------------
Explanation / Answer
#include <iostream>
#include <cmath>
using namespace std;
#include "BigInt.h"
void BigInt::read(short int temp)
{
short int block;
block=temp-48;
myList.push_back(block);
}
//-----------display
void BigInt::display(ostream & out) const
{
for(List<short int>::iterator it = myList.begin();;)
{
if (it == myList.end()) return;
out<<*it;
it++;
}
}
BigInt BigInt::removeZero(BigInt origin)
{
List<short int>::iterator
it2=origin.myList.begin();
while (it2!=origin.myList.rend())
{
if (*it2!=0) return origin;
else origin.myList.pop_front();
it2++;
}
origin.myList.push_back(0);
return origin;
}
void BigInt::removeNumber()
{
myList.clear();
}
int BigInt::size()
{
return myList.size();
}
bool BigInt::operator>(BigInt compare)
{
List<short int>::reverse_iterator
it1=--myList.rend(),
it2=--compare.myList.rend();
if (myList.size()>compare.myList.size())return true;
else if(myList.size()<compare.myList.size()) return false;
else
{
while(it1 != myList.rend() || it2 != compare.myList.rend())
{
if((*it1)>(*it2)) return true;
else if((*it1)<(*it2)) return false;
else
{
it1--;
it2--;
}
}
return false;
}
}
bool BigInt::operator<(BigInt compare)
{
if(*this>compare)
return false;
else
return true;
}
bool BigInt::operator==(BigInt Right)
{
List<short int>::reverse_iterator
it1=--myList.rend(),
it2=--Right.myList.rend();
if (myList.size()!=Right.myList.size()) return false;
else
{
while(it1 != myList.rend() || it2 != Right.myList.rend())
{
if((*it1)!=(*it2)) return false;
else
{
it1--;
it2--;
}
}
}
return true;
}
bool BigInt::operator>=(BigInt Right)
{
return ((*this>Right)||(*this==Right));
}
BigInt BigInt::operator+(BigInt addend2)
{
BigInt sum;
short int first,
second, )
result,
carry = 0;
List<short int>::reverse_iterator
it1=myList.rbegin(),
it2=addend2.myList.rbegin();
while (it1 != myList.rend() || it2 != addend2.myList.rend())
{
if (it1 != myList.rend())
{
first = *it1;
it1++ ;
}
else
first = 0;
if (it2 != addend2.myList.rend())
{
second = *it2;
it2++ ;
}
else
second = 0;
short int temp = first + second + carry;
result = temp % 10;
carry = temp / 10;
sum.myList.push_front(result);
}
if (carry > 0)
sum.myList.push_front(carry);
return sum;
}
//------operator
BigInt BigInt::operator-(BigInt subtractor)
{
BigInt dif;
short int first,
second,
carry = 0;
List<short int>::reverse_iterator
it1=myList.rbegin(),
it2=subtractor.myList.rbegin();
while (it1 != myList.rend() || it2 != subtractor.myList.rend())
{
if (it1 != myList.rend())
{
first = *it1;
it1++ ;
}
else
first = 0;
if (it2 != subtractor.myList.rend())
{
second = *it2;
it2++ ;
}
else
second = 0;
if (*this>=subtractor)
{
short int temp=0;
if (first>second||((first==second)&&(carry==0)))
{
temp = first-second-carry;
carry=0;
}
else
{
first+=10;
temp = first -carry- second;
carry=1;
}
dif.myList.push_front(temp);
}
else
{
dif=subtractor-*this;
*(--dif.myList.rend())=0-(*(--dif.myList.rend()));
}
}
return dif.removeZero(dif);
}
BigInt BigInt::operator*(BigInt multiplier)
{
BigInt pro;
BigInt tmp;
short int first, second, result, carry = 0;
List<short int>::reverse_iterator
it1=myList.rbegin(),
it2=multiplier.myList.rbegin();
while (it2 != multiplier.myList.rend())
{
if (it2 != multiplier.myList.rend())
{
second = *it2;
it2++;
}
else
second = 0;
while (it1 != myList.rend())
{
if (it1 != myList.rend())
{
first = *it1;
it1++ ;
}
else
first = 0;
short int temp = first * second + carry;
result = temp % 10;
carry = temp / 10;
tmp.myList.push_front(result);
}
if (carry > 0)
tmp.myList.push_front(carry);
for ( List<short int>::reverse_iterator it=multiplier.myList.rbegin()->_prev;it!=it2;it++)
{
tmp.myList.push_back(0);
}
carry=0;
pro=pro+tmp;
tmp.myList.clear();
it1=myList.rbegin();
}
return pro;
}
BigInt BigInt::operator/(BigInt divisor)
{
BigInt quo;
BigInt tmp;
if((*this)<divisor)
{
quo.myList.push_back(0);
return quo;
}
List<short int>::iterator
it1=myList.begin(),
it2=divisor.myList.begin();
while (it2!=divisor.myList.end())
{
tmp.myList.push_back(*it1);
it1++;
it2++;
}
for(--it1;it1!=myList.end(); it1++)
{
int i=0;
while (tmp>divisor||tmp == divisor)
{
tmp =tmp-divisor;
i++;
}
tmp.myList.push_back(it1->_next->_value);
quo.myList.push_back(i) ;
tmp=tmp.removeZero(tmp) ;
}
quo=quo.removeZero(quo) ;
return quo;
}
BigInt BigInt::operator%(BigInt divisor)
{
BigInt mod;
if((*this)<divisor)
{
return *this;
}
List<short int>::iterator
it1=myList.begin(),
it2=divisor.myList.begin();
while (it2!=divisor.myList.end())
{
mod.myList.push_back(*it1);
it1++;
it2++;
}
for(--it1;it1!=myList.end(); it1++)
{
int i=0;
while (mod>divisor|mod == divisor)
{
mod =mod-divisor;
i++;
}
if (it1->_next!=myList.end())
mod.myList.push_back(it1->_next->_value);
mod=mod.removeZero(mod) ;
}
return mod;
}
BigInt BigInt::operator^(BigInt divisor)
{
BigInt bigInt2;
bigInt2.myList.push_back(2);
BigInt bigInt1;
bigInt1.myList.push_back(1);
BigInt bigInt0;
bigInt0.myList.push_back(0);
if (divisor== bigInt2)
return (*this)*(*this);
else if (divisor== bigInt1)
return *this;
else if (divisor == bigInt0)
return bigInt1;
else
{
int n = *(divisor.myList.rbegin());
if (n % 2 == 0)
return
((*this)^(divisor/bigInt2))*((*this)^(divisor/bigInt2));
else
return
((*this)^(divisor/bigInt2))*((*this)^(divisor/bigInt2))*(*this);
}
}
BigInt.h
#include <iostream>
#include <iomanip>
#include "List.h"
#ifndef BIGINT
#define BIGINT
class BigInt
{
public:
void read(short int temp);
void display(ostream & out) const;
BigInt operator+(BigInt addend2);
BigInt operator-(BigInt subtrahend);
BigInt operator*(BigInt multiplier);
BigInt operator/(BigInt divisor);
BigInt operator^(BigInt divisor);
BigInt operator%(BigInt divisor);
BigInt removeZero(BigInt origin);
bool operator>(BigInt compare);
bool operator<(BigInt compare);
bool operator==(BigInt Right);
bool operator>=(BigInt Right);
void removeNumber();
int size();
private:
List<short int> myList;
};
inline ostream & operator<<(ostream & out, const BigInt & number)
{
number.display(out);
return out;
}
#endif
main.cpp
#include <iostream>
#include "List.h"
#include "BigInt.h"
#include "Cal.h"
#include <string>
using namespace std;
int main(int argc, const char * argv[]) {
Cal start;
start.calculate();
}
List.h
#ifndef LIST
#define LIST
#include <iostream>
#include <new>
#include <cassert>
using namespace std;
template <typename value_type>
class List
{
private:
struct Node
{
public:
value_type _value;
Node * _next = nullptr;
Node * _prev = nullptr;
Node(){}
Node(value_type Val)
{
_value = Val;
}
Node(value_type Val, Node* Prev, Node* Next) :
_value(Val),
_prev(Prev),
_next(Next)
{ }
};
typedef Node* node_pointer;
typedef const Node* const_node_pointer;
node_pointer _front;
node_pointer _back;
public:
class Iterator
{
private:
node_pointer _list_ite;
public:
Iterator(node_pointer Ptr = nullptr):
_list_ite(Ptr)
{ }
/*** ++Iterator ***/
Iterator& operator++()
{
_list_ite = _list_ite->_next;
return *this;
}
/*** Iterator++ ***/
Iterator operator++(int origin)
{
Iterator Iter = _list_ite;
_list_ite = _list_ite->_next;
return Iter;
}
/*** --Iterator ***/
Iterator& operator--()
{
_list_ite = _list_ite->_prev;
return *this;
}
/*** Iterator-- ***/
Iterator operator--(int origin)
{
Iterator Iter = _list_ite;
_list_ite = _list_ite->_prev;
return Iter;
}
void operator=(const Iterator& Right)
{
_list_ite = Right._list_ite;
}
const bool operator==(const Iterator& Right)const
{
return _list_ite == Right._list_ite;
}
const bool operator!=(const Iterator& Right)const
{
return _list_ite != Right._list_ite;
}
value_type& operator*()
{
return _list_ite->_value;
}
node_pointer operator->()
{
return _list_ite;
}
node_pointer operator&()
{
return &_list_ite;
}
operator Node*()
{
return _list_ite;
}
};
typedef Iterator iterator;
typedef const Iterator const_iterator;
class ReverseIterator
{
private:
node_pointer _list_ite;
public:
ReverseIterator(node_pointer Ptr = nullptr) :
_list_ite(Ptr)
{ }
/*** ++Iterator ***/
ReverseIterator& operator++()
{
_list_ite = _list_ite->_prev;
return *this;
}
/*** Iterator++ ***/
ReverseIterator operator++(int origin)
{
ReverseIterator Iter = _list_ite;
_list_ite = _list_ite->_prev;
return Iter;
}
/*** --Iterator ***/
ReverseIterator& operator--()
{
_list_ite = _list_ite->_next;
return *this;
}
/*** Iterator-- ***/
ReverseIterator operator--(int origin)
{
ReverseIterator Iter = _list_ite;
_list_ite = _list_ite->_next;
return Iter;
}
void operator=(const ReverseIterator& Right)
{
_list_ite = Right._list_ite;
}
const bool operator==(const ReverseIterator& Right)const
{
return _list_ite == Right._list_ite;
}
const bool operator!=(const ReverseIterator& Right)const
{
return _list_ite != Right._list_ite;
}
value_type& operator*()
{
return _list_ite->_value;
}
const value_type& operator*() const
{
return _list_ite->_value;
}
node_pointer operator->()
{
return _list_ite;
}
node_pointer operator&()
{
return &_list_ite;
}
operator Node*()
{
return _list_ite;
}
};
typedef ReverseIterator reverse_iterator;
typedef const ReverseIterator const_reverse_iterator;
List() :
_front(new Node),
_back(_front)
{
_front->_next = _front;
_front->_prev = _front;
}
List(const List<value_type>& Right) :
List()
{
if (!Right.empty())
{
for (auto p : Right)
this->push_back(p);
}
}
~List()
{
clear();
}
void push_back(const value_type& Val)
{
iterator Iter = _back->_prev;
iterator tmpIter=new Node(Val);
Iter->_next = tmpIter;
Iter->_next->_next = _back;
Iter->_next->_prev = Iter;
_back->_prev = Iter->_next;
if (empty())
_front = _front->_next;
}
void push_front(const value_type& Val)
{
Iterator tmpIter=new Node(Val);
_back->_next = tmpIter;
_back->_next->_next = _front;
_back->_next->_prev = _back;
_front->_prev = _back->_next;
_front = _front->_prev;
}
void insert(Iterator Where, const value_type& Val)
{
iterator Prev = Where->_prev;
iterator IterIns = new Node(Val);
Prev->_next = IterIns;
IterIns->_next = Where;
IterIns->_prev = Prev;
Where->_prev = IterIns;
Prev = nullptr;
IterIns = nullptr;
if (empty())
_front = _front->_next;
}
value_type front()
{
assert(!empty());
return _front->_value;
}
const value_type front() const
{
assert(!empty());
return _front->_value;
}
value_type& back()
{
assert(!empty());
return _back->_prev->_value;
}
const value_type& back() const
{
assert(!empty());
return _back->prev->_value;
}
bool empty() const
{
return _front == _back;
}
void clear()
{
if (!empty())
{
while (_back != _front)
{
Iterator Iter = _front;
_front = _front->_next;
delete Iter;
}
_back->_next = _back;
_back->_prev = _back;
}
}
void pop_back()
{
assert(!empty());
iterator IterDel = _back->_prev;
iterator Iter = _back->_prev->_prev;
Iter->_next = _back;
_back->_prev = Iter;
if (IterDel == begin())
_front = _front->_next;
delete IterDel;
}
void pop_front()
{
assert(!empty());
iterator Iter = _front;
_front = _front->_next;
_back->_next = _front;
_front->_prev = _back;
delete Iter;
}
iterator begin()
{
return iterator(_front);
}
const iterator begin()const
{
return iterator(_front);
}
iterator end()
{
return iterator(_back);
}
const iterator end()const
{
return iterator(_back);
}
reverse_iterator rbegin()
{
return reverse_iterator(_back->_prev);
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(_back->_prev);
}
reverse_iterator rend()
{
return reverse_iterator(_back);
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(_back);
}
int size() const
{
Iterator Iter = _front;
int size = 0;
while (Iter != end())
{
Iter = Iter->_next;
size++;
}
return size;
}
void operator=(const List<value_type>& Right)
{
clear();
if (!Right.empty())
{
for (auto p : Right)
this->push_back(p);
}
}
};
#endif
Cal.h
#ifndef BigIntCal_Cal_h
#define BigIntCal_Cal_h
class Cal
{
private:
BigInt number1;
BigInt number2;
BigInt result;
BigInt* Point;
char ope;
string expression;
public:
Cal();
void calculate();
void readExp();
BigInt mod(string m);
};
#endif
cal.cpp
#include <iostream>
#include "List.h"
#include "BigInt.h"
#include "Cal.h"
#include <string>
#include <ctime>
#include <fstream>
using namespace std;
Cal::Cal():Point(&number1){}
void Cal::readExp()
{
for (auto p:expression)
{
int tmp=p;
if(tmp>47&&tmp<58)
{
Point->read(tmp);
}
else if(tmp==42||tmp==43||tmp==45||tmp==47||tmp==94||tmp==37)
{
if (ope==' ') {
ope=tmp;
Point=&number2;
}
else
{
cerr<<" ";
number1.removeNumber();
number2.removeNumber();
Point=&number1;
calculate();
}
}
else
{
cerr<<" ";
number1.removeNumber();
number2.removeNumber();
Point=&number1;
calculate();
}
}
}
BigInt Cal::mod(string m)
{
BigInt n;
BigInt bm;
BigInt BigInt2;
BigInt2.read(50);
for (auto p:m)
{
int tmp=p;
if(tmp>47&&tmp<58)
bm.read(tmp);
else
{
cerr<<" ";
number1.removeNumber();
number2.removeNumber();
Point=&number1;
calculate();
}
}
n=BigInt2^bm;
return n;
}
void Cal::calculate()
{
cout<<"() ";
ope=' ';
while(cin>>expression)
{
if (expression=="f")
{
ifstream ifile;
ifile.open("expression.txt");
ifile>>expression;
ifile.close();
}
if (expression=="q")
{ cout<<" ";
exit(0);
}
readExp();
string m;
cout<<"" ";
cin>>m;
time_t TimeStart = time(0);
switch (ope)
{
case '+':
result=number1+number2; break;
case '-':
result=number1-number2; break;
case '*':
result=number1*number2; break;
case '/':
result=number1/number2; break;
case '%':
result=number1%number2; break;
case '^':
result=(number1^number2); break;
default:
break;
}
ofstream ofile;
ofile.open("expression.txt");
cout<<" "<<result%mod(m)<<endl;
cout<<""<<result.size()<<" "<<endl;
ofile<<" "<<result%mod(m)<<endl;
ofile<<""<<result.size()<<" "<<endl;
time_t TimeEnd = time(0);
cout << " " << (TimeEnd - TimeStart) << " s." << " ";
ofile << " " << (TimeEnd - TimeStart) << " s." << " ";
ofile.close();
ope=' ';
number1.removeNumber();
number2.removeNumber();
Point=&number1;
cout<<" ";
}
}