...

# Strings as Integers - Mulltiplication and exponentiation

amol0010
10-05-2009, 07:19 AM
Hi - I am supposed to do the following:

1) In put a main string using getline.
e.g. 124124124+123124124 or 123123123*123412412 or 12312312^123123

2) split this string into three strings - 124124124, + and 123124124 or 123123123, * and 123123123, I guess you get the idea

3) I am supposed to carry out the addition, multiplication and exponentiation operations on these left and right operators using character arrays.

i have written the following program to do this:

#include <iostream>
#include <string>
#include <ctype.h>
using namespace std;

// Global types and constants ///////////////////////////////////

const int MAX_STRING_LENGTH = 45;

//Define a character array (string) and an integer string
//The source is the array of integers
typedef char String[MAX_STRING_LENGTH];
typedef int Integer[MAX_STRING_LENGTH];

//Populate an integer array from the source string
void PopulateIntArray(const String source, int target[]);

//Add the two integers in the string
void AddInteger(const String l, const String r);

//Mulitply the integers in the string
void MultiplyInteger(String l, String r);

//Exponent the integers in the string
void ExponentInteger(String l, String r);

//Initialize the string to ""
void NullString( String& s );

//Extract the integers from the input string
void Extract( const String& source,int& locinSource, String &target_int );

//Extract the integers from the input string
void ExtractOp( const String& source, String &op );

void CharToString( char c, String& s );

int main()
{

//Three strings, left, right and the operator
String source, l, r, op;
Integer left, right, main;

cout<<"Enter the string with the operator in between the intergers, for e.g.\n\nTo add 2 and type in 2+3\n\nTo multiply 2 and 3 type 2*3\n\nTo raise 2 to 3 enter 2^3"<<endl;

cin.getline(source,MAX_STRING_LENGTH);

int locInSource =0;
//Initialize all left and right strings to null
NullString(l);
NullString(r);

Extract(source,locInSource, l);
Extract(source,locInSource, r);
ExtractOp(source, op);

puts(l);
puts(r);
puts(op);

system("PAUSE");
return 0;
}

//Initialize the string to ""
void NullString( String& s )
{ s[0] = '\0';
};

//Extract the integers from the input string
void Extract( const String& source, int &locInSource, String &target_int)
{

NullString(target_int);

String temp;

// Starting at locInSource, skip Leading blanks up
// to first character

while( (source[locInSource] == '+' || source[locInSource] == '*' || source[locInSource] == '^') && ( locInSource < MAX_STRING_LENGTH) )
locInSource++;

while( true )
{ // quit if at symbol to either multiply, divide or raised to
if( source[locInSource] == '+' || source[locInSource] == '*' || source[locInSource] == '^')
break;

//quit if at end of string
if( source[locInSource]=='\0') break;

//convert character and concatenate to string
CharToString( source[locInSource], temp );
strcat_s(target_int, temp );

locInSource++;
}

};

//Extract the operator from the string
void ExtractOp( const String& source, String &op)
{

NullString(op);

String temp;
int locInSource = 0;

// Starting at locInSource, skip Leading blanks up
// to first character

while( isspace(source[locInSource]) && ( locInSource < MAX_STRING_LENGTH))
locInSource++;

while(true){
// quit if at symbol to either multiply, divide or raised to
if( source[locInSource] == '+' || source[locInSource] == '*' || source[locInSource] == '^')
{//convert character and concatenate to string
CharToString( source[locInSource], temp );
strcat_s(op, temp );
break;
}

//quit if at end of strings
if(source[locInSource]=='\0') break;

locInSource++;

}

};

void CharToString( char c, String& s )
{ s[0] = c;
s[1] = '\0'; // or just 0
}

// Copy the string ( character array into an integer array
void PopulateIntArray(const String source, int target[])
{
int val,j=0;

for(int i=0;i<MAX_STRING_LENGTH;i++)
target[i]=0;

for(int i=strlen(source)-1;i>=0;i--)
{
val=(int)source[i]-48;
target[j++]=val;
}

};

//Add the two integers in the string
void AddInteger(const String l, const String r )
{
int arr1[MAX_STRING_LENGTH], arr2[MAX_STRING_LENGTH];
PopulateIntArray(l, arr1);
PopulateIntArray(r, arr2);

int temp[MAX_STRING_LENGTH] = {0};
int carry=0,sum=0, flag = 0;
int i = 0, j = 0;

for( i=0;i<MAX_STRING_LENGTH;i++)
{
sum=(arr1[i]+arr2[i]);
temp[i]=(sum+carry)%10;
carry=(sum+carry)/10;
}

for(i=MAX_STRING_LENGTH, j = 0;i>=0;i--, j++)
{
while(flag==0&&arr1[i]==0)
i--;
if(flag==0)
flag=1;
printf("%d",temp[i]);

}

};

If you can see I am typecasting the character array into integers which is what I am supposed to do.

How do I store the resultant addition into an array ?

The AddArray is correctly outputting the addition of integers, but I am just outputting it character by character.

However, I am supposed to write multiplication and exponentiation functions.

I am not sure how to go about writing a multiplication function i.e. I give two parameters - string 1 and string 2 to the multiplication function and then resultant is string 1*string 2.

I would be really grateful if someone could help me out on this one.

Thanks,
Amol

oracleguy
10-05-2009, 08:06 AM
On first glance of your program, there are a couple functions that can make your program simpler:

strtok (http://www.cplusplus.com/reference/clibrary/cstring/strtok/)
atoi (http://www.cplusplus.com/reference/clibrary/cstdlib/atoi/)

I'm guessing the atoi function is the one that you are really missing, which should help you a lot. Because once you have the left and right strings, you can just use atoi on them to convert them to integers and then just do straight math on them and print out the result.

Take a look at that and then if you have more questions, post back and I can help you further.

amol0010
10-05-2009, 04:37 PM

However, I am not allowed to use atoi in this. The only allowed methods are using the character or integer typecasted +/- 48 to convert them back and forth.

I guess I dont really need to use the strtok function anymore since I am already able to split the strings into three - left , right and the operator.

I am scratching my head on how to perform the multiplication or exponentiation.

Also should I store the result of AddArray into an integer array or a character array ?

oesxyl
10-05-2009, 07:00 PM

However, I am not allowed to use atoi in this. The only allowed methods are using the character or integer typecasted +/- 48 to convert them back and forth.

I guess I dont really need to use the strtok function anymore since I am already able to split the strings into three - left , right and the operator.

I am scratching my head on how to perform the multiplication or exponentiation.

Also should I store the result of AddArray into an integer array or a character array ?
distributive property, :)

x * y = (x1 * 10^n + x2) * y = x1 * y * 10^n + x2 * y

you can write as r1 * 10^n + r2 the result of x2 * y and then add r1 to x1 * y

10^n help you to split and concatenate the parts of the result, :)

same for exponentiation

x ^ y = x ^ (y1 * 10^n + y2) = x ^( y1 * 10^n) * x ^ y2 = (x ^ y1) ^ (10^n) * x ^ y2

if you make n = 1 you work with chars, so a conversion number = char - '0' and
back char = number + '0' will work.

best regards

amol0010
10-06-2009, 03:46 AM
^ I have no clue on what you just saidd lol.

And no clue on how to implement it as a function either :)

oracleguy
10-06-2009, 03:53 AM
I don't believe it is called the distributive property. oesxyl you might want to give more iterative example.

And as far as exponents, that's pretty easy once you have multiplication working:
80^4
is
80 * 80 * 80 * 80, you can do it with a loop.

oesxyl
10-06-2009, 04:58 AM
a * (b + c) = a * b + a *c
this is not called distributive property of * for +?
whatever is the name that is what I'm talking about.

example for *:

123456 * 65438 will be (12345 * 10 + 6) * 65438 = 12345 * 65438 * 10 + 6 * 65438
now we must multiply 12345 with 65438 and 6 with 65438 and add the results.
recursivly we can do this until we have to multiply only number with one digit.

for ^:

1234^106 = 1234^ (100 + 6) -> 1234 ^ 100 * 1234 ^ 6

I hope is more clear, :)

Anyway it's more easy for me to write the code then to explain, :)

best regards

amol0010
10-06-2009, 05:09 AM
Thanks oracle guy.

To get the multiplication working, I need to get the addition working.

for e.g. 2*3 = (3+3), 4*2 = (2+2+2+2) so I need to be able to call the add function the number of times I want to get it multiplied to.

I am currently just printing out integer by integer from the resultant array, trimming all the zeros.

How should I change my existing AddArray function ? should I store the result of l + r strings into an integer array or a character array ? Should the AddArray return a value ?

e.g. since the result of AddArray of l and r is an integer array in my case, if I want the function to return a value, it needs to return an integer array. But then to use the multiplication function I need AddArray to return an integer and not an integer array...

oracleguy
10-06-2009, 07:17 AM
a * (b + c) = a * b + a *c
this is not called distributive property of * for +?

Yes you're right, I misunderstood what you were going for.

How should I change my existing AddArray function ? should I store the result of l + r strings into an integer array or a character array ? Should the AddArray return a value ?

Yes, have it return an integer and then whatever function called it can do what it wants with the output. So in the case where the user entered 4+4, you would just print the result. And when you need to use it for your multiplication function, you can store the result.

amol0010
10-07-2009, 04:19 AM
^ the problem is that it isnt going to work with very long integers since

if you want to raise a number like 2123123 ^ 123123 it cant be stored in an integer value....

oesxyl
10-07-2009, 11:24 AM
^ the problem is that it isnt going to work with very long integers since

if you want to raise a number like 2123123 ^ 123123 it cant be stored in an integer value....
you can take n = 1 and then use multiplication.
2123123 ^ 123123 = 2123123 ^ (12312 * 10 + 3) = 2123123^(12312 * 10) * 12312^3

the problem from my point of view is that you must implement a lot of operators and function like <, =, +, -, *, ^, /, %, gcd, lcm,..., :)

best regards

oracleguy
10-07-2009, 05:03 PM
Are you sure you aren't allowed to implement your own version of atoi? Otherwise with multiplication in there this assignment seems unnecessarily hard.

amol0010
10-08-2009, 08:24 AM
I can use atoi only once in the program
"You can use atoi to convert the smaller operand of a multiply to an integer. In each case, even those required by exponentiation, choices have been made that make the smaller operand fit into an int."

I wrote the add and multiplication function using the string class.

Here's the code.#define MAX_STRING_LENGTH 45;
#define MIN_STRING_LENGTH 3;

#include <string>

using namespace std;

// create s to contain [c][\0] in first two cells

void CharToString( char c, string& s )
{ s[0] = c;
s[1] = '\0'; // or just 0
};

//Initialize the string to ""s
void NullString( string& s )
{ s[0] = '\0';
};

//Extract the integers from the input string
void Extract( const string source, int &locInSource, string &target_int)
{

string temp(source.length(), ' ' );

// Starting at locInSource, skip Leading blanks up
// to first character

if( source[locInSource] == '+' || source[locInSource] == '*' || source[locInSource] == '^')
locInSource++;

while( true )
{ // quit if at symbol to either multiply, divide or raised to
if( source[locInSource] == '+' || source[locInSource] == '*' || source[locInSource] == '^')
break;

//quit if at end of string
if( source[locInSource]=='\0') break;

//convert character and concatenate to string
CharToString( source[locInSource], temp );
target_int.insert(target_int.end(),source[locInSource]);

locInSource++;
}

};

//Extract the operator from the string
void ExtractOp( const string source, string &op)
{

string temp(source.length(), ' ');
int locInSource = 0;

// Starting at locInSource, skip Leading blanks up
// to first character

while(true){
// quit if at symbol to either multiply, divide or raised to
if( source[locInSource] == '+' || source[locInSource] == '*' || source[locInSource] == '^')
{//convert character and concatenate to string
CharToString( source[locInSource], temp );
op.insert(op.begin(),source[locInSource]);
break;
}

//quit if at end of strings
if(source[locInSource]=='\0') break;

locInSource++;

}

};

string add(string a, string b, int base = 10)
{
int la = a.length(), lb = b.length();
if (la > lb)
b.insert(b.begin(), la - lb, '0');
else
a.insert(a.begin(), lb - la, '0');

int carry = 0;
string result(a.length(), ' ');
for (int i = a.length() - 1; i >= 0; i--)
{
int sum = a[i] + b[i] - '0' + carry;
if (sum - '0' >= base)
result[i] = sum - base, carry = 1;
else
result[i] = sum, carry = 0;
}
if (carry ==1)
result.insert(result.begin(), '1');

return result;
}

//Multiply two long integers as strings, return a string
string multiply(string a, string b, int base = 10)
{
if(a=="0" || b=="0")
return "0";

string result(a.length() + b.length() - 1, '0');
for (int i = b.length() - 1; i >= 0; i--)
{
int carry=0;
for(int j = a.length() - 1; j >= 0; j--)
{
int t = (a[j] - '0') * (b[i] - '0') + result[i + j] - '0' + carry;
result[i + j] = t % base + '0', carry = t / base;
}
if (i ==1)
result[i - 1] = carry + '0';
else
result.insert(result.begin(), carry + '0');
}
if (result[0] == '0')
{
return result.substr(1);
}
else
{

return result;
}
}

#include <iostream>
#include "stringarithmetic.h"

using namespace std;

int main()
{
string source, left, right, op;

char ch ;

NullString(left);
NullString(right);
NullString(op);
NullString(source);

int locInSource =0;

cout<<"Enter the string with the operator in between the intergers, for e.g.\n\nTo add 2 and 3 type in 2+3\n\nTo multiply 2 and 3 type 2*3\n\nTo raise 2 to 3 enter 2^3"<<endl;
cout<<"\n\nRemember the maximum length of the entire string (including the left and right integers and the operand has to be less than 45 \n\n"<<endl;

getline(cin,source);

if( !(source.find("*",0) || source.find("+",0) || source.find("^",0)) )
{
cout<< "No valid operators were found in the input string \nExiting"<<endl;
system("PAUSE");
exit(1);
}

//Check if string entered is too long or too short
if(source.length() > 45)
{
cout<<"Sorry you entered too long a string to be operated upon (MAX YOU CAN INPUT IS 45), hence the program shall exit\n\n"<<endl;
system("PAUSE");
exit(1);
}
if(source.length() < 3)
{
cout<<"The operation needs at least 2 digits - left and right and one operand: +, *, ^ to operate the left and right upon \n\n"<<endl;
system("PAUSE");
exit(1);
}

//Extract the left operand
Extract(source,locInSource,left);

//Extract the operator
ExtractOp(source,op);
ch = op[0];

//Extract the right operand
Extract(source,locInSource,right);

switch(ch)
{
case '+':
{
break;
}

case '*':
{
result_multiply = multiply(left,right);
cout<<endl<<"The multiplication of "<<left<<" " <<"and "<<right<<" is "<<endl<<result_multiply<<endl<<endl;
break;

}

default:
{
cout<<"Wrong operator used, check input again"<<endl;
break;
}
}

system("PAUSE");
return 0;
}

It works perfectly.

Now how do I implement the exponentiation function ?

The exponentiation is limited to a single digit. e.g. 123123213 ^ 2

Thanks

oesxyl
10-08-2009, 05:39 PM
Now how do I implement the exponentiation function ?

The exponentiation is limited to a single digit. e.g. 123123213 ^ 2

Thanks
a^1 = a
a^2 = a * a
a^3 = a * a * a

use a loop as he said, :)

best regards

amol0010
10-09-2009, 03:45 AM
Well, the loop isnt working here, since they are character arrays.

A loop would only work in integer/floating point multiplication.

e.g. int a,b;

b =3 ;

a^b = a*b*b

//Multiply two long integers as strings, return a string
string multiply(string a, string b, int base = 10)
{
if(a=="0" || b=="0")
return "0";

int b_temp = atoi(b.c_str());

string result(a.length() + b.length() - 1, '0');
for (int i = b.length() - 1; i >= 0; i--)
{
int carry=0;
for(int j = a.length() - 1; j >= 0; j--)
{
int t = (a[j] - '0') * (b[i] - '0') + result[i + j] - '0' + carry;
result[i + j] = t % base + '0', carry = t / base;
}
if (i ==1)
result[i - 1] = carry + '0';
else
result.insert(result.begin(), carry + '0');
}
if (result[0] == '0')
{
return result.substr(1);
}
else
{

return result;
}
}

here a would be multiplied since a is an integer.

Not in case of a character array...

Anyways, I am allowed to convert only one string to integer using atoi.

e.g. i input 2 strings in exponent(a,b);

a^b . B is a single digit integer.

i am only allowed to convert b into an integer using atoi.

a remains a string.

oesxyl
10-09-2009, 08:09 AM
Well, the loop isnt working here, since they are character arrays.

A loop would only work in integer/floating point multiplication.

e.g. int a,b;

b =3 ;

a^b = a*b*b

char i, b = '3';
for(i = '0'; i < b; i++){
....
}

best regards

amol0010
10-09-2009, 07:01 PM
Sorry I was just being really stupid. I am not normally this stupid. I wonder why it didnt occur to me how to do it earlier.

here's the code I wrote.

//Raise one number to another using strings
string exponent(string a, string b, int base = 10)
{
int counter = atoi(b.c_str());

string multiplicant("1");

for(int i = 0; i<counter; i++)
{
multiplicant = multiply(a,multiplicant);
}

return multiplicant;

}

Works fine.

Thank you everyone for the help.