converting string to decimal digits?

[hellfire1]

Hello there!

This is the first time actually posting here, forgive me if I do something wrong. I'm a beginner C++ student, we just started with arrays and strings. :)

Anyhow, the problem I'm having is with a problem I was assigned the other day, involving strings and very long integers (numbers of up to 100 digits).

The problem is like this:

Problem [Very Long Integer]
Definition: A very long integer (VLI) is a nonnegative integer that has no more than 100 decimal digits and it is represented as a pair of two variables <size, arr>, where:
size – the current number of decimal digits of the VLI;
arr - an array of decimal digits (each decimal digit is stored in one array element).

Example:
const int MAXDIGITS = 100;
int arr[MAXDIGITS] = {1,2,3,4,5,6,7,8,9,0,9,8,7,6,5,4,3,2,1,0,9};

// The curent content of VLN is: 123456789098765432109
// There are 21 decimal digits in this VLI.
// The current number of digits is size = 21


A. List of Subproblems
Write a C++ function named inputVLI that inputs a VLI as a string of characters and transforms the string into the corresponding vli (Every character is converted into a decimal digit)
Prototype: void inputVLI(int vli[], int& size);

Write a C++ function named outputVLI that outputs a VLI.
Prototype: void outputVLI(int vli[], int size);

Write a C++ function named addVLI that calculates and “returns” the sum of two VLIs (vli3 = vli1 + vli2)
Prototype: void addVLI(int vli1[], int vli2[] int vli3[],
int size1, int size2, int& size3);

Write a C++ function named compVLI that compares two VLIs.
Prototype: int compVLI (int vli1[], int vli2[],
int size1, int size2);

The value returned by the addVLI function is:
-1, if vli1 < vli2
0, if vli1 == vli2
1, if vli1 > vli2

Write a main function that:
Declares three VLI: vli1, vli2 and vli3
Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
Outputs vli1 and vli2 (using outputVLI function)
Calculates vli3 (vli3 = vli1 + vli2, using addVLI function)
Compares vli1 and vli3 (using compVLI function)

(Sorry for the length, but I thought the info might help)

I have the main skeleton of the program already made, but I'm hitting a major roadblock with this problem, specifically at the first part, the input. I'm really new to strings in general, so I'm unsure of how they work, when I input a string of numbers into an array, are they automatically split into decimal digits, or do I have to do so myself? And if so, ideas on how?

I don't need the problem solved, but some pointers on good ways to go about this would be nice! I've included the skeleton code if it helps understand. :)

I've bolded the part that I'm currently stuck on.

#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

const int MAX_DIGITS = 100;

//prototypes

void inputVLI(int vli[], int& size);

void outputVLI(int vli[], int size);

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3);

int compVLI (int vli1[], int vli2[],
int size1, int size2);

/*
Write a main function that:
Declares three VLI: vli1, vli2 and vli3
Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
Outputs vli1 and vli2 (using outputVLI function)
Calculates vli3 (vli3 = vli1 + vli2, using addVLI function)
Compares vli1 and vli3 (using compVLI function)
*/

//main function

void main()
{

}

//Function definitions

void inputVLI(int vli[], int& size)
{
	
}

void outputVLI(int vli[], int size)
{

}

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3)
{

}

int compVLI (int vli1[], int vli2[],
int size1, int size2)
{

}

Many Thanks!
-Drew

[Chervil]

Since you are using <cstring>, you will need to allocate a character buffer (an array of char) to hold the user input.

After getting the input into this buffer, you can step through the array one character at a time. You will need to convert each char into an integer. But the char will probably be in ASCII, where '0' = decimal 48, and '9' = decimal 57 etc.

You could convert it something like this. For simplicity, I won't use an array here.

char ch = '6'; // for example. Should be user input here.
int digit;
digit = ch - '0';  // subtract character code for digit '0' to give decimal digit. 

It's probably a good idea to validate the input to confirm that each digit is in the range 0 to 9. There might be some letters 'O' or 'I' or 'l' in there perhaps. (Validation is often ignored in example programs so you may not need this. But you should be aware of it).

[hellfire1]

Hello,
It's the TC again, I've spent another day on this and am still just as stumped as I was a week ago...

I just can't for the life of me figure out how to get the input to work. According to the problem, I need to use the inputVLI function to input a VLI and then convert it to integers...

But I can't figure out what I'm supposed to do...

The prototype is this, as listed above:

void inputVLI(int vli[], int& size);

but I'm confused. I don't know how to use what it gives me to make the function work... I need to use the int vli[], and the reference parameter int& size, but am at a loss.

Does this mean I already have to have the array converted to integers before the function? That doesn't make sense though, because this function is called input. So, that leads me to think that this function, since it's a void function, simply assigns the VLI in decimal form, after the original VLI is entered in a string of characters?

Also, above everything else, how to I enter into an array from a keyboard?
Exactly what we're told to do is shown below...

Write a C++ function named inputVLI that inputs a VLI as a string of characters and transforms the string into the corresponding vli (Every character is converted into a decimal digit)

Apparently the idea posted to me above just didn't jog my problem solving skills enough, can someone at least get me started? I'm having a bit of a meltdown here...

If someone can help me get the code for inputing a VLI as a string of characters, and tell me exactly what I'm supposed to use int& size for, I can most likely get things from there.

[Chervil]

I look at it like this:

Write a main function that:
1. Declares three VLI: vli1, vli2 and vli3
2. Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
3. Outputs vli1 and vli2 (using outputVLI function)
4. etc. etc.

Now it seems to me that you are trying to start with step 2.
That looks like the reason for some of the confusion.

To begin, you are supposed to declare three VLIs. Now since the array and size values are tied together in their meaning and purpose, I'd be tempted to use a structure to hold them.

On the other hand, the function prototypes refer to the two parts separately, so it doesn't matter very much which way you do it.

At any rate, you will start with something like this (but you don't have to follow the names I use).

At the global scope (outside of any function)
const int MAXDIGITS = 100;
In function main():

int VLIoneArray[MAXDIGITS];
int VLIoneSize = 0;

The reason for placing the constant at the global level is that the other functions may need to use its value.

Next call the function inputVLI(VLIoneArray, VLIoneSize); The code for that function is the thing which now needs to be written. Now the purpose of the function is to:

a) ask the user to input the number

b) get the input as a string of characters

c) check that the string is no longer than MAXDIGITS. If it's longer you could simply truncate the string, but it might be better to issue a warning message and ask the user to try again.

d) use a loop to step through the input string one character at a time. Convert the character to the corresponding (integer) decimal digit. Store that digit in the VLI array at the corresponding index position. (each char in the string corresponds to one element in the array).

e) when you get to the end of the input string, store the count of the number of digits which were stored, into the VLI size value.

Since the array is passed to the function as an address, and the size is passed by reference, the values will directly affect the input parameters. Thus the function can now simply end.

If you follow this approach, of breaking down each task into smaller subtasks, you should be able to write the code.

When you are ready to write the code for the next function, before writing any code, write down the list of steps that the function will need to follow, before you start.

Coding is actually the relatively easy part, it's just translating human words into a computer-speak version. The important part is the design stage. When doing this, you will be thinking in terms of what the computer will need to do, and how, but you will express this in ordinary English, not in code.


One thing which I've not addressed is whether to process the input string from left to right or from right to left. Normally when we read, we proceed from left to right. However, in the case of a number, it may be better to proceed from the right-hand end. The reason for that is to start with the units (ones), then the tens, then hundreds, and so on.

[hellfire1]

Thanks so much!!

I guess I was just thinking about this whole problem the wrong way. I like the problem solving that programming makes me do, but it gives me major headaches sometimes.

I'll start the way you suggested, and go from there. :)

[hellfire1]

Eh, actually, I've run into a question already again...

Why am I not allowed to input a value as string?

For instance, I get an error message when I say:

 
string x;
cin >> x;

IntelliSense: no operator ">>" matches these operands
operand types are: std::istream >> std::string

why is this?
My book says I should be able to do this, but my compiler will not allow it...
I'm using Visual Studio 2012 Express, and the book is C++ Programming edition 5 by D.S. Malik.

[Chervil]

Did you put

#include <iostream> 
#include <string> 

at the top?

[hellfire1]

I had:

#include <iostream>
#include <cstring> 

What is the difference between <cstring>, <string.h> and <string>?
Because <string> works fine apparently...

[Moschops]

<cstring>is the string.h library from the C programming language given a C++ remix (which generally means putting it all into the std namespace).

<string.h> is the string.h library from the C programming language.

<string>is the string library from the C++ programming language. This contains the C++ class known as string.

[hellfire1]

Thanks for clearing up my mistake! :)

I'll quit bugging you guys for now ;)

Thanks again for the help,
-Drew

[hellfire1]

Question again!
Sorry guys, I know I've asked a lot of questions, but I'm making major progress! :)

Here's what I have so far, and it works, for the most part:

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

const int MAX_DIGITS = 100;

//prototypes

void inputVLI(int vli[], int& size);

void outputVLI(int vli[], int size);

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3);

int compVLI (int vli1[], int vli2[],
int size1, int size2);

/*
Write a main function that:
Declares three VLI: vli1, vli2 and vli3
Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
Outputs vli1 and vli2 (using outputVLI function)
Calculates vli3 (vli3 = vli1 + vli2, using addVLI function)
Compares vli1 and vli3 (using compVLI function)
*/

//main function

void main()
{
	int vli1[MAX_DIGITS], vli2[MAX_DIGITS], vli3[MAX_DIGITS];
	int size1, size2, size3;

	cout << "Step 1: INPUT\n"
		 << "------------------------------------------------------------------\n";
	cout << "A very long integer is a number of up to 100 decimal digits. \n"
		 << "Please enter a very long integer: \n";
	inputVLI(vli1, size1);
	cout << endl << "Please enter a second very long integer: \n";
	inputVLI(vli2, size2);
	
	cout << "Step 2: OUTPUT\n"
		 << "------------------------------------------------------------------\n";
	outputVLI(vli1, size1);
	cout << endl;
	outputVLI(vli2, size2);
	cout << endl;

	cout << "Step 3: ADDITION\n"
		 << "-------------------------------------------------------------------\n";
	addVLI(vli1,vli2,vli3,size1,size2,size3);
	outputVLI(vli3,size3);
}

//Function definitions

void inputVLI(int vli[], int& size)
{
	string vli1_string;
	bool no_error = true;

	do //enters the VLI as a string
	{
		cin >> vli1_string;
		cout << endl;
		size = vli1_string.length();  //claculates the size using .length
		for (int number = 0; number < size ; number++)
		{
			if (!isdigit((char)vli1_string[number])) //checks if string is entirely numbers
			{
				cout << "Your input was not all numbers. Input must be only numbers! \n\n"
					 << "Try again...\n";
				no_error = false;
				break;
			}
			else if (size >= MAX_DIGITS) //verifies that string is within max digits
			{
				cout << "Your input is over 100 digits long!\n"
					 << "Please enter a number with less than 100 digits... \n\n";
				no_error = false;
				break;
			}
			else // reassigns each character as an integer value
			{
				//takes each character of the array and converts it to an integer,
				//by subtracting the char '0'.
				no_error = true;
				vli[number] = vli1_string[number] - '0';
			}
		}
	}
	while (no_error == false); //keeps re-running until there is no errors...
}

void outputVLI(int vli[], int size)
{
	//simply takes each value of the array and outputs it with a space behind it.
	for(int number = 0; number < size; number++)
    {
        cout << vli[number] << " ";
    }
    cout << endl;
}

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3)
{
	int vli1_int, vli2_int; //uses the integer changed arrays

	//Determines which of the two numbers is bigger, to make the size of VLI3.
    if(size1 > size2)
    {
        size3 = size1;
    }
    else
    {
        size3 = size2;
    }

	//cycles through each index, until it reaches the size of vli3.
    for(int number = 0; number <= size3; number++)
    {
        if(size1 - number >= 0)
            vli1_int = vli1[size1 - number];
		//takes the numbers from right to left, unless there are none
        else
            vli1_int = 0;
		//if no numbers, value defaults to 0
        if(size2 - number >= 0)
            vli2_int = vli2[size2 - number];
		//also takes the numbers from right to left, unless none exist
        else
            vli2_int = 0;
		//if no numbers in array, value is 0;

        vli3[size3 - number] = (vli1_int + vli2_int)%10; //assigns individual numbers to vli3 index's
		//does this by taking the two other int arrays, and then taking the remainder.
		//this shaves of the individual number and assigns it to the individual cell.
	}
        
}

int compVLI (int vli1[], int vli2[],
int size1, int size2)
{
	return 0;
}

The problem now is the addition. It adds perfectly fine, if there are no numbers that carry over, but as soon as something carries, it has issues. How would I make it carry a digit?

Forgive me if there are a few unneeded fragments here and there, I think I cleaned up all of it, but I've been changing stuff for most of the morning.

[Chervil]

I've not studied your code thoroughly, but at first glance it looks like good progress.

Regarding the add and carry, you need to think back to how you add two numbers manually (without using a calculator). You may do much of this in your head, without even realising the steps involved. But go back to the time when you first learned addition of numbers with more than just one digit.

Perhaps you would write the numbers down on paper, and maybe write down part of the answer and a small carry digit as you went along. Basically, doing this with a computer will replicate the same methods that you use to do the addition by hand.

You may find the integer divide / and modulus % operators useful in order to manipulate the intermediate results of adding two digits. (divide by 10 or find remainder when dividing by 10).

[hellfire1]

Hey guys, hope everyone had a good thanksgiving!

It's me again, I was working on this problem again, on and off for a few days now, and I still can't get this adding problem to work.

Here's what I've got, so you can see my thought process.

#include <iostream>
#include <cstdlib>
#include <string>
using namespace std;

const int MAX_DIGITS = 100;

//prototypes

void inputVLI(int vli[], int& size);

void outputVLI(int vli[], int size);

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3);

int compVLI (int vli1[], int vli2[],
int size1, int size2);

/*
Write a main function that:
Declares three VLI: vli1, vli2 and vli3
Enters values for two VLIs : vli1 and vli2 (using inputVLI function)
Outputs vli1 and vli2 (using outputVLI function)
Calculates vli3 (vli3 = vli1 + vli2, using addVLI function)
Compares vli1 and vli3 (using compVLI function)
*/

//main function

void main()
{
	int vli1[MAX_DIGITS], vli2[MAX_DIGITS], vli3[MAX_DIGITS+1]; //+1 is for a possible carried digit
	int size1, size2, size3;

	cout << "Step 1: INPUT\n"
		 << "------------------------------------------------------------------\n";
	cout << "A very long integer is a number of up to 100 decimal digits. \n"
		 << "Please enter a very long integer: \n";
	inputVLI(vli1, size1);
	cout << endl << "Please enter a second very long integer: \n";
	inputVLI(vli2, size2);
	
	cout << "Step 2: OUTPUT\n"
		 << "------------------------------------------------------------------\n";
	outputVLI(vli1, size1);
	cout << endl;
	outputVLI(vli2, size2);
	cout << endl;

	cout << "Step 3: ADDITION\n"
		 << "-------------------------------------------------------------------\n";
	addVLI(vli1,vli2,vli3,size1,size2,size3);
	outputVLI(vli3,size3);
}

//Function definitions

void inputVLI(int vli[], int& size)
{
	string vli1_string;
	bool no_error = true;

	do //enters the VLI as a string
	{
		cin >> vli1_string;
		cout << endl;
		size = vli1_string.length();  //claculates the size using .length
		for (int number = 0; number < size ; number++)
		{
			if (!isdigit((char)vli1_string[number])) //checks if string is entirely numbers
			{
				cout << "Your input was not all numbers. Input must be only numbers! \n\n"
					 << "Try again...\n";
				no_error = false;
				break;
			}
			else if (size >= MAX_DIGITS) //verifies that string is within max digits
			{
				cout << "Your input is over 100 digits long!\n"
					 << "Please enter a number with less than 100 digits... \n\n";
				no_error = false;
				break;
			}
			else // reassigns each character as an integer value
			{
				//takes each character of the array and converts it to an integer,
				//by subtracting the char '0'.
				no_error = true;
				vli[number] = vli1_string[number] - '0';
			}
		}
	}
	while (no_error == false); //keeps re-running until there is no errors...
}

void outputVLI(int vli[], int size)
{
	//simply takes each value of the array and outputs it with a space behind it.
	for(int number = 0; number < size; number++)
    {
        cout << vli[number] << " ";
    }
    cout << endl;
}

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3)
{
int vli1_int, vli2_int; //uses the integer changed arrays
int carried = 0; //realized I needed a way to figure out the carried numbers

//Determines which of the two numbers is bigger, to make the size of VLI3.
    if(size1 > size2)
    {
        size3 = size1;
    }
    else
    {
        size3 = size2;
    }

//cycles through each index, until it reaches the size of vli3.
    for(int number = 0; number <= size3; number++)
    {
	if (size1 - number >= 0)
		vli1_int = vli1[size1 - number];
	else 
		vli1_int = 0;
	//takes the numbers from right to left, unless there are none, then defaults to zero
	//this is to avoid an error with unknown array values
        
        if (size2 - number >= 0)
		vli2_int = vli2[size2 - number];
	else
		vli1_int = 0;
	//also takes the numbers from right to left, unless none exist, then defaults to zero
	//this is to avoid an error with unknown array values

	//States that if the value for the cell is over 9, it should be split into stored and carried digit.
	if (vli1_int + vli2_int + carried > 9)
	{
		vli3[size3 - number]= (vli1_int + vli2_int + carried)%10;
		carried = (vli1_int + vli2_int + carried)/10;
	}
	else
	{
		vli3[size3 - number]= (vli1_int + vli2_int + carried);
		carried = 0;
	}
		
	//If final number is over 9, it expands the array, and then shifts all values to the right.
	//It then places the carried digit in the new space created.
	if (vli3[0] > 9)
	{
		++size3;
		for (int number = 0; number <= size3; number++)
		vli3[size3 - number] = vli3[size3 - number + 1];
		vli3[0]= 1;
		vli3[1]= vli3[1]%10;
	}
    } 
}

int compVLI (int vli1[], int vli2[],
int size1, int size2)
{
	return 0;
}

Now, I have it all written out on paper how it should work. Obviously, if I add the first two numbers of the arrays, starting from the right, and they turn out to be over 9, the carried digit would be that number divided by 10 right? Then this number would be added to the next index, while the number%10 would give the rightmost digit to be assigned to that current index...

Then the carried digit would store, and add to the next two array numbers. Again, if that were over nine, the same process would repeat. This means I would have to have it in loop, which I did.

Then at the very end, if the final number was over 9, I would have to expand the array to make room for it, and then assign the digits to the old and the new slot.

Maybe I've just been looking at this so long it starts to blur together, but what I have works for numbers that don't carry. For example, it adds 111 and 111 just fine, and produces 2 2 2. But when I have to carry a number, it still won't work, and it's very frustrating....

Can someone tell me what I am still doing wrong?

EDIT:
I still need help. I redocumented the code so it's easier to understand, and I fixed an error with my shifted values. However, there is still a problem somewhere, and I cannot find it.

I should be getting an output of 1001 when I input 999 and 2. However, I get 231???. Clearly there is still an error somewhere.

It works for values like 1555 and 1555.

Thanks,
-Drew

[hellfire1]

Still need help...

The messed up output is here:

Step 1: INPUT
------------------------------------------------------------------
A very long integer is a number of up to 100 decimal digits.
Please enter a very long integer:
999


Please enter a second very long integer:
2

Step 2: OUTPUT
------------------------------------------------------------------
9 9 9

2

Step 3: ADDITION
-------------------------------------------------------------------
2 3 1
Press any key to continue . . .

Again, clearly I have it at least carrying a digit, since it works with 1555 + 1555, but there is still a major flaw that I cannot find.

[Chervil]

Just a quck answer for now, I'll try to give more details later.
I tried this:
1234512345+
       543
----------
1234512888
and this was the output:

Step 2: OUTPUT
--------------------
1 2 3 4 5 1 2 3 4 5

5 4 3

Step 3: ADDITION
----------------------
5 5 5 5 5 5 5 5 8 8 8

There's clearly something wrong, as this example should not even need a carry.

My first, instinctive feeling from glancing at the code is that the addition looks more complex than it needs to be - but I need to look again before I can say anything really useful.

One comment I would make, perhaps because I've tried similar problems before, is that I would store the digits in the array in the reverse sequence.
For example 4159265 would be stored like this:

vli[0] = 5
vli[1] = 6
vli[2] = 2
vli[3] = 9
vli[4] = 5
vli[5] = 1
vli[6] = 4

This follows the normal convention that the least significant digit 5 is stored in the lowest-numbered element of the array.

It makes the input and output just a tiny bit more complex, but it's not really earth-shattering.

If you do that, the addition should be reasonably straightforward.

That's not to say you current approach can't be fixed, it probably can.

[Chervil]

Well, I had a proper look at the add() function and found several errors.
Original code (comments to follow)

void addVLI(int vli1[], int vli2[], int vli3[],
int size1, int size2, int& size3)
{
int vli1_int, vli2_int; //uses the integer changed arrays
int carried = 0; //realized I needed a way to figure out the carried numbers

//Determines which of the two numbers is bigger, to make the size of VLI3.
    if(size1 > size2)
    {
        size3 = size1;
    }
    else
    {
        size3 = size2;
    }

//cycles through each index, until it reaches the size of vli3.
    for(int number = 0; number <= size3; number++)
    {
        if (size1 - number >= 0)
            vli1_int = vli1[size1 - number];
        else 
            vli1_int = 0;
        // takes the numbers from right to left, 
        // unless there are none, then defaults to zero
        // this is to avoid an error with unknown array values
            
        if (size2 - number >= 0)
            vli2_int = vli2[size2 - number];
        else
            vli1_int = 0;
        // also takes the numbers from right to left, 
        // unless none exist, then defaults to zero
        // this is to avoid an error with unknown array values

        // States that if the value for the cell is over 9, 
        // it should be split into stored and carried digit.
        if (vli1_int + vli2_int + carried > 9)
        {
            vli3[size3 - number]= (vli1_int + vli2_int + carried)%10;
            carried = (vli1_int + vli2_int + carried)/10;
        }
        else
        {
            vli3[size3 - number]= (vli1_int + vli2_int + carried);
            carried = 0;
        }
            
        // If final number is over 9, it expands the array,
        // and then shifts all values to the right.
        // It then places the carried digit in the new space created.
        if (vli3[0] > 9)
        {
            ++size3;
            for (int number = 0; number <= size3; number++)
                vli3[size3 - number] = vli3[size3 - number + 1];
                
            vli3[0]= 1;
            vli3[1]= vli3[1]%10;
        }
    } 
}

(Actually I adjusted the indentation for better readability).

Comments:
Line 18, for loop. for(int number = 0; number <= size3; number++)
the condition should be number < size3;, currently this would exceed the boundaries of the data (and give garbage results).

Line 20: if (size1 - number >= 0)
the test should be (size1 - number - 1 >= 0)
Let's say size=4 and number=0. size-number will equal 4, again this is outside the data (valid subscripts range from 0 to 3 in this case).

Line 21: similarly, this vli1[size1 - number] should be this: vli1[size1 - number - 1]

This same error occurs throughout the code, I won't list them all.

Line 31: vli1_int = 0; Should be vli2_int

Lines 49-60. Testing for a carry beyond the last digit. First, and most important, this code is within the for-loop (begun on line 18). This block should be moved so it executes after the end of that loop.
Line 52: if (vli3[0] > 9). The preceding code has ensured (all being well) that a value bigger than 9 will never be stored in the array, so this test won't work. Instead, use if (carried)

There are also the same errors with subscript too large by one as described earlier, so the values will need tweaking.

Well, that's about it, if these errors are fixed the code should work.
After that, you might look at simplifying / shortening it a bit, but get it working first. Good luck!