you will implement an algorithm that uses stacks to add numbers of any size. (C

ID: 3863724 • Letter: Y

Question

you will implement an algorithm that uses stacks to add numbers of any size. (C or C++)

The largest magnitude of integers is limited. We are not able to add 18,274,364,583,929,273,748,525 and 8,129,498,165,026,350,236 because integer variables cannot hold such large values, let alone their sum.

The problem can be solved if we treat these numbers as strings of numerals, store the numbers corresponding to these numerals on two stacks, and then perform addition by popping from the stacks. The pseudocode for this algorithm is as follows:

addLargeNumbers(number1, number2)

read the numerals of the first number and store them on one stack read the numerals of the second number and store them on another stack

var result := 0

while at least one stack is not empty

pop a numeral from each nonempty stack and add them to result push the unit part of addition onto a new stack called the result stack store the carry part of the addition in result

push result onto the result stack if it is not zero

pop numbers from the result stack and display them

a) (6 point) Implement the addLargeNumbers function with the following prototype:

void addLargeNumbers(const char *pNum1, const char *pNum2);

This function should output the result of adding the two numbers passed in as strings. Here is an example call to this function with the expected output:

/* Sample call to addLargeNumbers */

addLargeNumbers("592", "3784");

/* Expected output */

4376

b) (3 points) Implement a test program that demonstrates adding at least three pairs of large numbers (numbers larger than can be represented by a long).

Explanation / Answer

PROGRAM CODE:

/*
* largeNumbers.cpp
*
* Created on: 19-Mar-2017
* Author: kasturi
*/

#include <iostream>
#include <vector>

using namespace std;
void addLargeNumbers(const char *pNum1, const char *pNum2);

int main()
{
   addLargeNumbers("134567892", "7634956");
   addLargeNumbers("235682760926", "1824986235");
   addLargeNumbers("99999999999923", "888888888888843");
   return 0;
}

void addLargeNumbers(const char *pNum1, const char *pNum2)
{
   vector<int> v1, v2, resultStack;
   int result = 0, counter=0;
   if(strlen(pNum1) > strlen(pNum2))
   {
       counter = strlen(pNum1);
       for(int i=strlen(pNum2); i<counter; i++)
           v2.push_back(0);
   }
   else if(strlen(pNum2) > strlen(pNum1))
   {
       counter = strlen(pNum2);
       for(int i=strlen(pNum1); i<counter; i++)
           v1.push_back(0);
   }
   else
       counter = strlen(pNum1);
   for(int i=0; i<strlen(pNum1); i++)
   {
       v1.push_back(pNum1[i] - '0');
   }
   for(int i=0; i<strlen(pNum2); i++)
   {
       v2.push_back(pNum2[i] - '0');
   }
   while(!v1.empty() && !v2.empty())
   {
       //cout<<v1[counter-1]<<" "<<v2[counter-1]<<endl;
       result += v1[counter-1]+ v2[counter-1];
       resultStack.push_back(result%10);
       result = result/10;
       v1.pop_back();
       v2.pop_back();
       counter--;
   }
   if(result > 0)
       resultStack.push_back(result);
   cout<<"Adding "<<pNum1<< " and "<<pNum2<<endl;
   cout<<"Result: ";
   for(int i=resultStack.size()-1; i>=0; i--)
   {
       cout<<resultStack[i];
   }
   cout<<endl<<endl;
}

OUTPUT:

Adding 134567892 and 7634956

Result: 142202848

Adding 235682760926 and 1824986235

Result: 237507747161

Adding 99999999999923 and 888888888888843

Result: 988888888888766

Navigate

you will have to turn in the worksheet. The remaining time will be spent going o

you will investigate some of these sorting algorithms: *Bidirectional Bubble Sor

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

you will implement an algorithm that uses stacks to add numbers of any size. (C

Question

Explanation / Answer

Related Questions

Navigate