NPTEL Online Course Week 5 Big Int Addition Assignment
1.BigInt::add(BigInt A ), returns the result in another BigInt, without altering the numerical value of the caller.
Primitive int data type handles integers
each of which can be stored using 32 bits. Similarly long data type also has a limit.
In this assignment you have to implement a data type which handles numbers
larger than int , long and long long.
You are given a
number in decimal form. You need to build a data structure called BigInt which
can store that data, and perform the following basic operations on that data
type:
1.BigInt::add(BigInt A ), returns the result in another BigInt, without altering the numerical value of the caller.
2.BigInt::print(), this function must print Most significant digit at the
beginning and must not print any leading zeroes.
Ex: 123 (correct )
0123 (incorrect)
3.populate(BigInt &A, char * str), populates the List in BigInt using
public methods of BigInt.
Note that populate(BigInt
&A, char * str) method is not a function of BigInt.
Input:
Input will have two lines, each line
contains a single BigInt.
Sample Input:
8132393963283
216396739263921391
Output:
Output contains the result of the
addition in a single line.
Output of the above sample input is as
follows.
Sample Output:
216404871657884674
Constraints:
1 ≤ Input length of
BigInt ≤ 40 digits.
Input for BigInt is
always positive
Hints: (optional)
Store the numbers in
reverse order, as addition is performed from Least Significant Digit. For
example store the number 122 as 2->2->1, instead of 1->2->2.
Note: To get the initial template code, delete everything in editor and submit.
Note: To get the initial template code, delete everything in editor and submit.
/*
*THE BELOW CODE WILL BE PREPENDED BEFORE
COMPILATION.
*ALL NECESSARY FUNCTIONS OF LIST, LISTNODE ARE
IMPLEMENTED.
*
*/
#include <iostream>
#include <cstring>
using namespace std;
class ListNode{
private:
int data;
ListNode * next;
public:
ListNode(){}
ListNode(int num){
data=num;
next = NULL;
}
int getData();
void setData(int);
void setNext(ListNode *);
ListNode* getNext();
};
/*
*Implementation of Node Methods
*/
int ListNode::getData(){
return data;
}
void ListNode::setData(int x){
data
= x;
}
ListNode * ListNode::getNext(){
return next;
}
void ListNode::setNext(ListNode * P){
next = P;
}
/***End Of Node Methods Implementation**/
class List{
private:
ListNode * Head;
public:
List(){
Head=NULL;
}
~List(){}
/*Already
Implemented Methods.You can use them in your
*functions
**/
ListNode * getHead();
void setHead(ListNode *);
ListNode * last();
void append(int);
void prepend(int);
void popBack();
void print();
void copy(List);
void printReverse(); //prints the list
from Tail to Head.
/*Implement the follwing if required. Not mandatory*/
ListNode * prevNode(ListNode* P);
void popFront();
};
/*
****List Methods Implementaion***
*/
ListNode * List::getHead(){
return Head;
}
ListNode * List::last(){
ListNode * temp=Head;
if(Head==NULL) return NULL;
while(temp->getNext()!=NULL){
temp=temp->getNext();
}
return temp;
}
void List::setHead(ListNode * P){
Head = P;
}
void List::append(int num){
ListNode * new_node = new ListNode(num);
ListNode * temp=Head;
if(temp==NULL){
Head = new_node;
return;
}
while(temp->getNext()!=NULL)
temp=temp->getNext();
temp->setNext(new_node);
}
void List::prepend(int num){
ListNode * new_node = new ListNode(num);
new_node->setNext(Head);
Head = new_node;
}
/*
*Removes the Tail Node
*/
void List::popBack(){
ListNode * temp=Head,*prev=NULL;
//NULL list
if(Head==NULL){cout<<"List is
Empty\n";}
//single element
if(Head->getNext()==NULL){
delete Head;
Head=NULL;
return;
}
while(temp->getNext()!=NULL){
prev
= temp;
temp=temp->getNext();
}
delete temp;
prev->setNext(NULL);
}
void List::print(){
ListNode * temp=Head;
while(temp!=NULL){
cout<<temp->getData();
temp=temp->getNext();
}
}
//copy values of L into this list
void List::copy(List L){
Head = NULL;
ListNode * temp = L.Head;
while(temp!=NULL){
this->append(temp->getData());
temp=temp->getNext();
}
}
void List::printReverse(){
ListNode * curr=Head;
ListNode * prev_last=NULL;
while(Head!=NULL && prev_last!=Head){
curr
= Head;
while(curr->getNext()!=prev_last){
curr
= curr->getNext();
}
cout<<curr->getData();
prev_last
= curr;
}
}
/*****End Of List Methods
Implementation************************/
/* This is the data type you need to write the
required methods*/
class BigInt{
private:
List L;
public:
BigInt(){}
~BigInt(){}
/*Must write code for append(),prepend(), add(), print() Methods*/
void append(int num);
void prepend(int num);
BigInt add(BigInt A);
void print();//mandatory
/*Helper Functions,
not mandatory to implement
*Hint: Implement removeZeroes(), call it in
print().
*/
void removeZeroes();
void copy(BigInt B);
};
/*UPTO THIS LINE, THE CODE WIL BE PREPENDED BEFORE
YOUR FUNCTIONS*/
Solutions:
int l1,l2,count=0;
void
populate(BigInt &A, char * str){
/*write
your code here**/
int
i=0,k;
while(str[i]!=0)
{
k=(int)str[i]-48;
A.prepend(k);
i++;
}
if(count==0)
{l1=i;
count++;
}
else
l2=i;
}
void
BigInt::append(int num){
/*write
your code here**/
L.append(num);
}
void
BigInt::prepend(int num){
/*write
your code here**/
L.prepend(num);
}
BigInt
BigInt::add(BigInt A){
/**write
your code here*/
int
t;
t=l1-l2;
if(t>0)
{
while(t!=0)
{
A.append(0);
t--;
}
}
else
if(t<0)
{
while(t!=0)
{
append(0);
t++;
}
}
else
{
}
ListNode
* temp1=L.getHead();
ListNode
* temp2=A.L.getHead();
int
x,carry=0;
while(temp1!=NULL)
{
x=temp1->getData()+temp2->getData()+carry;
carry=0;
if(x<10)
{
temp2->setData(x);
}
else
{
x=x%10;
temp2->setData(x);
carry=1;
}
temp1=temp1->getNext();
temp2=temp2->getNext();
}
if(carry==1)
{
A.L.append(1);
}
return
A;
}
void
BigInt::removeZeroes(){
/**write
your code here
*Hint:
Implement removeZeroes(), call it in print().
*/
ListNode
* temp=L.getHead();
while(temp->getNext()!=0) temp=temp->getNext();
if(temp->getData()==0)
{
L.popBack();
}
}
void
BigInt::print(){
/*write
your code here*/
ListNode
* temp=L.getHead();
removeZeroes();
removeZeroes();
while(temp->getNext()!=NULL) temp=temp->getNext();
L.printReverse();
}
/*Warning::
The following code given below will be appended
*at the end
of your code before compilation.
*You must
not write main function.
**/
/*
int
main(){
char
str[40];
BigInt
A,B;
cin>>str;
populate(A,str);
cin>>str;
populate(B,str);
(A.add(B)).print();
return
0;
}*/
hello sir,
ReplyDeleteplease overview the removezeroes function coding because it is not removing zeros.
awaiting for your reply.
thank you.