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.
/*
*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*/
/**THESE ARE THE ONLY FUNCTIONS YOU ARE REQUIRED TO FILL
*You are allowed to define additional global functions.
*Note: Remove/Comment the helper functions, if you are not implementing them.
*/
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;
}*/
No comments:
Post a Comment