Help With Stacks

penance · #1 09-Oct-2005, 14:33

Hello, I am creating a program to add and multiply large numbers using stacks. I have been working on the program all day and I believe I am on the verge of completing it, but right now the addition and multiplication functions are not doing their job correctly. I'm not entirely sure why, and I was hoping someone here could assist me in finding out the source of this problem. Thank you for your time and any help is appreciated, no matter how small.

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Define the limit of the stacks.*/
#define MAXSTACK 100

/*Defines the structure of a stack.*/
typedef struct {
	int digits[MAXSTACK];
	int top;
}arraystack;

/*Pushes new item onto the stack.*/
void push(arraystack *x, int y);
/*Pops new item from the stack.*/
void pop(arraystack *x, int y);
/*Pops items from stack and prints them.*/
void popprint(arraystack *x, int y);
/*Checks to see if the stack is empty.*/
int isEmpty(arraystack *x);
/*Addition function.*/
void addition(arraystack *x, arraystack *y);
/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y);
/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y);

/*Structs will be global.*/
arraystack value1;
arraystack value2;
arraystack dummy;
arraystack temp1;
arraystack result;

int main(void)
{
	/*Variables for file input.*/
	FILE *ifp;
	char filename[30];
	/*Variables for loops.*/
	int counter, i, j;
	/*Variables for strings.*/
	char num1[100];
	char num2[100];
	/*Variables for conversion.*/
	char c1;
	int digit = 0;

	/*Initialize top of stacks.*/
	value1.top = -1;
	value2.top = -1;
	dummy.top = -1;
	temp1.top = -1;
	result.top = -1;

	/*Ask for input file.*/
	printf("Please enter the filename of the file you wish to open: ");
	scanf("%s", &filename);

	/*Open input file.*/
	ifp = fopen(filename, "r");

	/*Get number of digit sets from file.*/
	fscanf(ifp, "%d", &counter);

	/*For the number of digits in the file:*/
	for (i = 0; i < counter; i++) {
		/*Read in the first number.*/
		fscanf(ifp, "%s", &num1);
		/*Read in the next number.*/
		fscanf(ifp, "%s", &num2);
		/*Convert first number into a digit and push it into the first array.*/
		j = 0;
		while(num1[j] != '\0') {
			c1 = num1[i];
			digit = c1 - '0';
			push(&value1, digit);
			j++;
		}
		/*Convert second number into a digit and push it into the second array.*/
		j = 0;
		while(num2[j] != '\0') {
			c1 = num2[i];
			digit = c1 - '0';
			push(&value2, digit);
			j++;
		}
		/*Add the two arrays.*/
		addition(&value1, &value2);
		/*Multiply the two arrays.*/
		multiplication(&value1, &value2);
	}

	/*Close input file.*/
	fclose(ifp);

	/*End program.*/
	return 0;
}

/*Pushes items onto a stack.*/
void push(arraystack *x, int y) {
	/*If the stack is full:*/
	if (x->top >= MAXSTACK - 1) {
		/*Error.*/
		printf("Stack is full.\n");
	}
	/*Otherwise:*/
	else {
		/*Stack top raises by 1 and new digit is added.*/
		x->top = x->top + 1;
		x->digits[x->top] = y;
	}
}

/*Pops items from a stack.*/
void pop(arraystack *x, int y) {
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and stack top lowers by 1.*/
		y = x->digits[x->top];
		x->top = x->top - 1;
	}
}

/*Checks to see if the stack is empty.*/
int isEmpty(arraystack *x) {
	return (x->top < 0);
}

/*Pops items from stack and prints them.*/
void popprint(arraystack *x, int y) {
	/*Variable for loop.*/
	int i;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and printed and stack top lowers by 1.*/
		y = x->digits[x->top];
		for (i = 0; i <= x->top; i++) {
			printf("%d", y);
		}
		printf("\n");
		x->top = x->top - 1;
	}
}

/*Addition function.*/
void addition(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			pop(x, num1);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			pop (y, num2);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry = 1) {
		/*Push carry onto stack.*/
		push(&result, carry);
	}
	/*Call popprint and send result.*/
	popprint(&result, digit);
}

/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variable for deciding factor.*/
	int decide = 0;
	/*Variable for loop.*/
	int i;
	/*Variables for product.*/
	int num1 = 0;
	int num2 = 0; 
	int product;
	/*Variable for printing.*/
	int digit = 0;
	/*While second stack is not empty:*/
	while (y->top >= 0) {
		/*Add the necessary zeros to first temp stack.*/
		for (i = 0; i < decide; i++) {
			push(&temp1, 0);
		}
		/*Dummy stack is equivalent to first value stack.*/
		for (i = 0; i <= value1.top; i++) {
			dummy.digits[i] = value1.digits [i];
		}
		/*Pop value from second value stack.*/
		pop(y, num2);
		/*For the duration of dummy stack:*/
		while (dummy.top >= 0) {
			/*Pop value from dummy stack.*/
			pop(&dummy, num1);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(&temp1, product);
			}
			/*If product is 10 or greater:*/
			else {
				/*Value of product % 10 is pushed onto stack.*/
				product = product % 10;
				push(&temp1, product);
				/*Value of (product-(product%10))/10 becomes carry.*/
				carry = (product-(product%10))/10;
			}
		}
		/*If second temp stack is empty:*/
		if (result.top < 0) {
			/*Second temp stack is first temp stack.*/
			result = temp1;
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Otherwise:*/
		else {
			/*Add two temp stacks together.*/
			addformult(&temp1, &result);
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Add 1 to deciding factor.*/
		decide = decide + 1;
	}
	/*Call popprint and print result.*/
	popprint(&result, digit);
}

/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			pop(x, num1);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			pop (y, num2);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push (&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry = 1) {
		/*Push carry onto stack.*/
		push (&result, carry);
	}
	/*Send result to multiplication.*/
	return &result;
}

davekw7x · #2 09-Oct-2005, 15:25

Quote:

Originally Posted by penance

Hello, I am creating a program to add and multiply large numbers using stacks.

My first question is rhetorical: Why would you use stacks to hold digits for multi-digit arithmetic?

Here's the way I think you are doing addition:

You get digits for one operand (the addend?) and push them onto a stack (most significant digit first).
You get digits for the other operand (the augend?) and push them onto another stack (most significant digit first).

That's pretty good: the least significant digits are sitting on top of the stack, easy to get to, and that's where the arithmetic will begin.

You get the top digit (least significant of the remaining digits) for each number, calculate sum and carry for the decimal addition. So far, so good. But now, you push the sum digit onto the result stack. When you get through, the result has least significant on bottom, most significant on top (assuming the logic and arithmetic are correct). Maybe that's convenient for printing out the value, but in order to use that result as the operand for another addition, it has to be reversed so that the most significant digit is on bottom, right?

See my problem? You are representing numbers on a stack, but sometimes they have least significant digits on top and sometimes they have most significant digits on top. I think the data base should match the application, and I can't think of any reason to make the representation context-sensitive (the program ---i.e. the programmer--- has to know whether a given number is ready for operating or ready for printing).

Oh, well, without actually looking really, really close at the logic and arithmetic, here are a couple of observations:

Line 59 (or thereabouts)

CPP / C++ / C Code:

	scanf("%s", &filename);

Filename is an array of char, and when you use an array name by itself (no brackets) it is treated as a pointer, so the correct syntax would be

CPP / C++ / C Code:

	scanf("%s", filename);

You do this a couple of other places, too (for num1 and num2).

Now, there are lots of reasons not to use scanf, and there are also safer ways to use scanf (most experienced programmers recommend fgets() for what you are doing here), but at any rate, whatever you decide to use for input, I really, really, strongly recommend that you put in statements to print out what the user entered at each step.

This is also (and in this case, especially) true for getting the input data from the files. If you get the "wrong" output answer, how do you know whether the problem is with input routines or arithmetic routines?

line 207 (or thereabouts):

CPP / C++ / C Code:

	if (carry = 1) {

line 333 or thereabouts

CPP / C++ / C Code:

	if (carry = 1) {

Easy to do; I've done it more times than you have seen summers (probably more times than you have seen sunsets).

Your function pop() doesn't do anything except decrease the stack by one. If you want to pop a value, maybe it should return the value. (The second argument isn't used in the function, but places where you call the function seem to expect that the top of the stack be returned in the second argument. If you want to do it that way, you can pass a pointer, but why not just have the function return the value?)

Maybe you could write a simple main() program that does a few pushes and pops to test the fundamentals before you get into the arithmetic.

I think your multiplication() function is supposed to multiply x by y, but the parameter x is not used. You use y but not x Why????

You are using global variables for a lot of your stacks. Why? It's really bad programming practice in the opinion of many of my more knowledegable colleagues. You could at least be consistent. Either make everything global (a bad idea, in my opinion) or use function arguments to pass information around the program.

One final comment about style (about comments, actually):
I know that everyone says to use lots of comments, but really!

compare your code

CPP / C++ / C Code:

		for (i = 0; i <= value1.top; i++) {
			dummy.digits[i] = value1.digits [i];
		}
		/*Pop value from second value stack.*/
		pop(y, num2);
		/*For the duration of dummy stack:*/
		while (dummy.top >= 0) {
			/*Pop value from dummy stack.*/
			pop(&dummy, num1);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(&temp1, product);
			}
			/*If product is 10 or greater:*/

with this:

CPP / C++ / C Code:

		for (i = 0; i <= value1.top; i++) {
			dummy.digits[i] = value1.digits [i];
		}
		pop(y, num2);
		while (dummy.top >= 0) {
			pop(&dummy, num1);
			product = (num1 * num2) + carry;
			if (product < 10) {
				carry = 0;
				push(&temp1, product);
			}

Do you really need a comment "pop value from second value stack" for the instruction "pop(y, num2)" (even if your pop() worked)? And look at the statement "product = (num1 * num2) + carry;" That's beautiful! What could be more clear! I really like the use of meaningful variable names. But --- what useful information is added by the comment "multiply the numbers and add the carry to get the product"? Just more clutter, in my opinion.

By putting comments every single line (or almost every line) you obscure the really relevant comments and make the program, overall, less pleasant to read (and eyeball fatigue is one main reason people overlook things like "if (carry = 1)").

Regards,

Dave

penance · #3 09-Oct-2005, 15:41

Thanks for your assistance, I tried changing a lot of what you said although the problems don't seem to be clearing up. There's probably some big issue at the root of all this.

Here is the new code.

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Define the limit of the stacks.*/
#define MAXSTACK 100

/*Defines the structure of a stack.*/
typedef struct {
	int digits[MAXSTACK];
	int top;
}arraystack;

/*Pushes new item onto the stack.*/
void push(arraystack *x, int y);
/*Pops new item from the stack.*/
int pop(arraystack *x, int *y);
/*Pops items from stack and prints them.*/
void popprint(arraystack *x, int *y);
/*Checks to see if the stack is empty.*/
int isEmpty(arraystack *x);
/*Addition function.*/
void addition(arraystack *x, arraystack *y);
/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y);
/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y);

/*Structs will be global.*/
arraystack value1;
arraystack value2;
arraystack dummy;
arraystack temp1;
arraystack result;

int main(void)
{
	/*Variables for file input.*/
	FILE *ifp;
	char filename[30];
	/*Variables for loops.*/
	int counter, i, j;
	/*Variables for strings.*/
	char num1[100];
	char num2[100];
	/*Variables for conversion.*/
	char c1;
	int digit = 0;

	/*Initialize top of stacks.*/
	value1.top = -1;
	value2.top = -1;
	dummy.top = -1;
	temp1.top = -1;
	result.top = -1;

	/*Ask for input file.*/
	printf("Please enter the filename of the file you wish to open: ");
	scanf("%s", filename);

	/*Open input file.*/
	ifp = fopen(filename, "r");

	/*Get number of digit sets from file.*/
	fscanf(ifp, "%d", &counter);

	/*For the number of digits in the file:*/
	for (i = 0; i < counter; i++) {
		/*Read in the first number.*/
		fscanf(ifp, "%s", num1);
		/*Read in the next number.*/
		fscanf(ifp, "%s", num2);
		/*Convert first number into a digit and push it into the first array.*/
		j = 0;
		while(num1[j] != '\0') {
			c1 = num1[i];
			digit = c1 - '0';
			push(&value1, digit);
			j++;
		}
		/*Convert second number into a digit and push it into the second array.*/
		j = 0;
		while(num2[j] != '\0') {
			c1 = num2[i];
			digit = c1 - '0';
			push(&value2, digit);
			j++;
		}
		/*Reset stacks.*/
		dummy.top = -1;
		temp1.top = -1;
		result.top = -1;
		/*Add the two arrays.*/
		addition(&value1, &value2);
		/*Multiply the two arrays.*/
		multiplication(&value1, &value2);
	}

	/*Close input file.*/
	fclose(ifp);

	/*End program.*/
	return 0;
}

/*Pushes items onto a stack.*/
void push(arraystack *x, int y) {
	/*If the stack is full:*/
	if (x->top >= MAXSTACK - 1) {
		/*Error.*/
		printf("Stack is full.\n");
	}
	/*Otherwise:*/
	else {
		/*Stack top raises by 1 and new digit is added.*/
		x->top = x->top + 1;
		x->digits[x->top] = y;
	}
}

/*Pops items from a stack.*/
int pop(arraystack *x, int *y) {
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and stack top lowers by 1.*/
		*y = x->digits[x->top];
		x->top = x->top - 1;
	}
	return *y;
}

/*Checks to see if the stack is empty.*/
int isEmpty(arraystack *x) {
	return (x->top < 0);
}

/*Pops items from stack and prints them.*/
void popprint(arraystack *x, int *y) {
	/*Variable for loop.*/
	int i;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and printed and stack top lowers by 1.*/
		*y = x->digits[x->top];
		for (i = 0; i <= x->top; i++) {
			printf("%d", y);
		}
		printf("\n");
		x->top = x->top - 1;
	}
}

/*Addition function.*/
void addition(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x, &num1);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop(y, &num2);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry == 1) {
		/*Push carry onto stack.*/
		push(&result, carry);
	}
	/*Call popprint and send result.*/
	popprint(&result, &digit);
}

/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variable for deciding factor.*/
	int decide = 0;
	/*Variable for loop.*/
	int i;
	/*Variables for product.*/
	int num1 = 0;
	int num2 = 0; 
	int product;
	/*Variable for printing.*/
	int digit = 0;
	/*While second stack is not empty:*/
	while (y->top >= 0) {
		/*Add the necessary zeros to first temp stack.*/
		for (i = 0; i < decide; i++) {
			push(&temp1, 0);
		}
		/*Dummy stack is equivalent to first value stack.*/
		for (i = 0; i <= x->top; i++) {
			dummy.digits[i] = x->digits [i];
		}
		/*Pop value from second value stack.*/
		num2 = pop(y, &num2);
		/*For the duration of dummy stack:*/
		while (dummy.top >= 0) {
			/*Pop value from dummy stack.*/
			num1 = pop(&dummy, &num1);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(&temp1, product);
			}
			/*If product is 10 or greater:*/
			else {
				/*Value of product % 10 is pushed onto stack.*/
				product = product % 10;
				push(&temp1, product);
				/*Value of (product-(product%10))/10 becomes carry.*/
				carry = (product-(product%10))/10;
			}
		}
		/*If second temp stack is empty:*/
		if (result.top < 0) {
			/*Result stack is first temp stack.*/
			for (i = 0; i <= temp1.top; i++) {
				result.digits[i] = temp1.digits [i];
			}
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Otherwise:*/
		else {
			/*Add two temp stacks together.*/
			addformult(&temp1, &result);
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Add 1 to deciding factor.*/
		decide = decide + 1;
	}
	/*Call popprint and print result.*/
	popprint(&result, &digit);
}

/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num2 = pop(x, &num1);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop (y, &num2);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry ==  1) {
		/*Push carry onto stack.*/
		push (&result, carry);
	}
	/*Send result to multiplication.*/
	return &result;
}

penance · #4 09-Oct-2005, 15:46

Changed the code again. Problem still exists but it's starting to clear away.

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Define the limit of the stacks.*/
#define MAXSTACK 100

/*Defines the structure of a stack.*/
typedef struct {
	int digits[MAXSTACK];
	int top;
}arraystack;

/*Pushes new item onto the stack.*/
void push(arraystack *x, int y);
/*Pops new item from the stack.*/
int pop(arraystack *x);
/*Pops items from stack and prints them.*/
void popprint(arraystack *x);
/*Checks to see if the stack is empty.*/
int isEmpty(arraystack *x);
/*Addition function.*/
void addition(arraystack *x, arraystack *y);
/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y);
/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y);

/*Structs will be global.*/
arraystack value1;
arraystack value2;
arraystack dummy;
arraystack temp1;
arraystack result;

/*Name: Matthew Barak
PID: ma241840
Course: COP 3502
Assignment Number: 2
Title: Large Numbers
Program Description: Reads in numbers from an outside file, stores them in stacks,
and adds and multiplies them.
Date: 10/09/05
Bonus Part Attempted: No
Created In: Visual C++
*/

int main(void)
{
	/*Variables for file input.*/
	FILE *ifp;
	char filename[30];
	/*Variables for loops.*/
	int counter, i, j;
	/*Variables for strings.*/
	char num1[100];
	char num2[100];
	/*Variables for conversion.*/
	char c1;
	int digit = 0;

	/*Initialize top of stacks.*/
	value1.top = -1;
	value2.top = -1;
	dummy.top = -1;
	temp1.top = -1;
	result.top = -1;

	/*Ask for input file.*/
	printf("Please enter the filename of the file you wish to open: ");
	scanf("%s", filename);

	/*Open input file.*/
	ifp = fopen(filename, "r");

	/*Get number of digit sets from file.*/
	fscanf(ifp, "%d", &counter);

	/*For the number of digits in the file:*/
	for (i = 0; i < counter; i++) {
		/*Read in the first number.*/
		fscanf(ifp, "%s", num1);
		/*Read in the next number.*/
		fscanf(ifp, "%s", num2);
		/*Convert first number into a digit and push it into the first array.*/
		j = 0;
		while(num1[j] != '\0') {
			c1 = num1[i];
			digit = c1 - '0';
			push(&value1, digit);
			j++;
		}
		/*Convert second number into a digit and push it into the second array.*/
		j = 0;
		while(num2[j] != '\0') {
			c1 = num2[i];
			digit = c1 - '0';
			push(&value2, digit);
			j++;
		}
		/*Reset stacks.*/
		dummy.top = -1;
		temp1.top = -1;
		result.top = -1;
		/*Add the two arrays.*/
		addition(&value1, &value2);
		/*Multiply the two arrays.*/
		multiplication(&value1, &value2);
	}

	/*Close input file.*/
	fclose(ifp);

	/*End program.*/
	return 0;
}

/*Pushes items onto a stack.*/
void push(arraystack *x, int y) {
	/*If the stack is full:*/
	if (x->top >= MAXSTACK - 1) {
		/*Error.*/
		printf("Stack is full.\n");
	}
	/*Otherwise:*/
	else {
		/*Stack top raises by 1 and new digit is added.*/
		x->top = x->top + 1;
		x->digits[x->top] = y;
	}
}

/*Pops items from a stack.*/
int pop(arraystack *x) {
	int y;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and stack top lowers by 1.*/
		y = x->digits[x->top];
		x->top = x->top - 1;
	}
	return y;
}

/*Checks to see if the stack is empty.*/
int isEmpty(arraystack *x) {
	return (x->top < 0);
}

/*Pops items from stack and prints them.*/
void popprint(arraystack *x) {
	int y;
	/*Variable for loop.*/
	int i;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and printed and stack top lowers by 1.*/
		y = x->digits[x->top];
		for (i = 0; i <= x->top; i++) {
			printf("%d", y);
		}
		printf("\n");
		x->top = x->top - 1;
	}
}

/*Addition function.*/
void addition(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop(y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry == 1) {
		/*Push carry onto stack.*/
		push(&result, carry);
	}
	/*Call popprint and send result.*/
	popprint(&result);
}

/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variable for deciding factor.*/
	int decide = 0;
	/*Variable for loop.*/
	int i;
	/*Variables for product.*/
	int num1 = 0;
	int num2 = 0; 
	int product;
	/*Variable for printing.*/
	int digit = 0;
	/*While second stack is not empty:*/
	while (y->top >= 0) {
		/*Add the necessary zeros to first temp stack.*/
		for (i = 0; i < decide; i++) {
			push(&temp1, 0);
		}
		/*Dummy stack is equivalent to first value stack.*/
		for (i = 0; i <= x->top; i++) {
			dummy.digits[i] = x->digits [i];
		}
		/*Pop value from second value stack.*/
		num2 = pop(y);
		/*For the duration of dummy stack:*/
		while (dummy.top >= 0) {
			/*Pop value from dummy stack.*/
			num1 = pop(&dummy);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(&temp1, product);
			}
			/*If product is 10 or greater:*/
			else {
				/*Value of product % 10 is pushed onto stack.*/
				product = product % 10;
				push(&temp1, product);
				/*Value of (product-(product%10))/10 becomes carry.*/
				carry = (product-(product%10))/10;
			}
		}
		/*If second temp stack is empty:*/
		if (result.top < 0) {
			/*Result stack is first temp stack.*/
			for (i = 0; i <= temp1.top; i++) {
				result.digits[i] = temp1.digits [i];
			}
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Otherwise:*/
		else {
			/*Add two temp stacks together.*/
			addformult(&temp1, &result);
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Add 1 to deciding factor.*/
		decide = decide + 1;
	}
	/*Call popprint and print result.*/
	popprint(&result);
}

/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop (y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry ==  1) {
		/*Push carry onto stack.*/
		push (&result, carry);
	}
	/*Send result to multiplication.*/
	return &result;
}

davekw7x · #5 09-Oct-2005, 15:59

Quote:

Originally Posted by penance

Thanks for your assistance, I tried changing a lot of what you said although the problems don't seem to be clearing up.

I gave some general observations and a couple of specific hints about glaring errors. I hope you didn't think that my post had all the information you need to get satisfaction.

By the way, this is wrong:

CPP / C++ / C Code:

			printf("%d", y);

The variable y is a pointer, so the print statement should be

CPP / C++ / C Code:

			printf("%d", *y);

This brings me to the point: It's not enough for you to say, "the problems don't seem to be clearing up." In order for you to have some hope of getting meaningful help, I recommend that you run a simple test case. Maybe you could give the program a couple of two-digit numbers to add so that it will be easy to test the results, and in worst case, you could print out every single step of the operations. Make a new file that has the main program, the addition routine and whatever input and output stuff that you think you need. You could even hard-code values for the input variables so as not to get hung up in file input routines.

Then:

1. Tell us what the input was. (Also, for your information and ours, have the program print out the input values that is using.)

2. Tell us what the output was. (Copy/paste from your screen to the post whatever the program printed; you might explain what the printout actually represents.)

3. Tell us what you expected the output to be. How did you arrive at the values of your expected outputs? Did you step through the program manually with the given input values or what?

4. Tell us what you don't understand about the difference between expected and actual program output.

Additional debugging hints:
Put in some print statements in the internal routines for pushing, popping, adding digits, showing sum and carry at each step, or whatever would give you (and us) a clue as to what is going on.

In other words: simplify the program and give a simple test case.

Regards,

Dave

"Simplify, simplify!"
---Henry David Thoreau

penance · #6 09-Oct-2005, 16:24

I revised the code again to this.

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Define the limit of the stacks.*/
#define MAXSTACK 100

/*Defines the structure of a stack.*/
typedef struct {
	int digits[MAXSTACK];
	int top;
}arraystack;

/*Pushes new item onto the stack.*/
void push(arraystack *x, int y);
/*Pops new item from the stack.*/
int pop(arraystack *x);
/*Pops items from stack and prints them.*/
void popprint(arraystack *x);
/*Addition function.*/
void addition(arraystack *x, arraystack *y);
/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y);
/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y);

/*Structs will be global.*/
arraystack value1;
arraystack value2;
arraystack dummy;
arraystack temp1;
arraystack result;

/*Name: Matthew Barak
PID: ma241840
Course: COP 3502
Assignment Number: 2
Title: Large Numbers
Program Description: Reads in numbers from an outside file, stores them in stacks,
and adds and multiplies them.
Date: 10/09/05
Bonus Part Attempted: No
Created In: Visual C++
*/

int main(void)
{
	/*Variables for file input.*/
	FILE *ifp;
	char filename[30];
	/*Variables for loops.*/
	int counter, i, j;
	/*Variables for strings.*/
	char num1[100];
	char num2[100];
	/*Variables for conversion.*/
	char c1;
	int digit = 0;

	/*Initialize top of stacks.*/
	value1.top = -1;
	value2.top = -1;
	dummy.top = -1;
	temp1.top = -1;
	result.top = -1;

	/*Ask for input file.*/
	printf("Please enter the filename of the file you wish to open: ");
	scanf("%s", filename);

	/*Open input file.*/
	ifp = fopen(filename, "r");

	/*Get number of digit sets from file.*/
	fscanf(ifp, "%d", &counter);

	/*For the number of digits in the file:*/
	for (i = 0; i < counter; i++) {
		/*Read in the first number.*/
		fscanf(ifp, "%s", num1);
		/*Read in the next number.*/
		fscanf(ifp, "%s", num2);
		/*Convert first number into a digit and push it into the first array.*/
		j = 0;
		while(num1[j] != '\0') {
			c1 = num1[j];
			digit = c1 - '0';
			push(&value1, digit);
			j++;
		}
		/*Convert second number into a digit and push it into the second array.*/
		j = 0;
		while(num2[j] != '\0') {
			c1 = num2[j];
			digit = c1 - '0';
			push(&value2, digit);
			j++;
		}
		/*Reset stacks.*/
		dummy.top = -1;
		temp1.top = -1;
		result.top = -1;
		/*Add the two arrays.*/
		addition(&value1, &value2);
		/*Multiply the two arrays.*/
		multiplication(&value1, &value2);
	}

	/*Close input file.*/
	fclose(ifp);

	/*End program.*/
	return 0;
}

/*Pushes items onto a stack.*/
void push(arraystack *x, int y) {
	/*If the stack is full:*/
	if (x->top >= MAXSTACK - 1) {
		/*Error.*/
		printf("Stack is full.\n");
	}
	/*Otherwise:*/
	else {
		/*Stack top raises by 1 and new digit is added.*/
		x->top = x->top + 1;
		x->digits[x->top] = y;
	}
}

/*Pops items from a stack.*/
int pop(arraystack *x) {
	int y;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and stack top lowers by 1.*/
		y = x->digits[x->top];
		x->top = x->top - 1;
	}
	return y;
}

/*Pops items from stack and prints them.*/
void popprint(arraystack *x) {
	/*Variable for loop.*/
	int i;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*Digits are popped and printed.*/
		for (i = 0; i <= x->top; i++) {
			printf("%d", x->digits[x->top]);
			x->top = x->top - 1;
		}
	}
	printf("\n");
}

/*Addition function.*/
void addition(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop(y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry == 1) {
		/*Push carry onto stack.*/
		push(&result, carry);
	}
	/*Call popprint and send result.*/
	popprint(&result);
}

/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variable for deciding factor.*/
	int decide = 0;
	/*Variable for loop.*/
	int i;
	/*Variables for product.*/
	int num1 = 0;
	int num2 = 0; 
	int product;
	/*Variable for printing.*/
	int digit = 0;
	/*While second stack is not empty:*/
	while (y->top >= 0) {
		/*Add the necessary zeros to first temp stack.*/
		for (i = 0; i < decide; i++) {
			push(&temp1, 0);
		}
		/*Dummy stack is equivalent to first value stack.*/
		for (i = 0; i <= x->top; i++) {
			dummy.digits[i] = x->digits [i];
		}
		/*Pop value from second value stack.*/
		num2 = pop(y);
		/*For the duration of dummy stack:*/
		while (dummy.top >= 0) {
			/*Pop value from dummy stack.*/
			num1 = pop(&dummy);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(&temp1, product);
			}
			/*If product is 10 or greater:*/
			else {
				/*Value of product % 10 is pushed onto stack.*/
				product = product % 10;
				push(&temp1, product);
				/*Value of (product-(product%10))/10 becomes carry.*/
				carry = (product-(product%10))/10;
			}
		}
		/*If second temp stack is empty:*/
		if (result.top < 0) {
			/*Result stack is first temp stack.*/
			for (i = 0; i <= temp1.top; i++) {
				result.digits[i] = temp1.digits [i];
			}
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Otherwise:*/
		else {
			/*Add two temp stacks together.*/
			addformult(&temp1, &result);
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Add 1 to deciding factor.*/
		decide = decide + 1;
	}
	/*Call popprint and print result.*/
	popprint(&result);
}

/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop (y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry ==  1) {
		/*Push carry onto stack.*/
		push (&result, carry);
	}
	/*Send result to multiplication.*/
	return &result;
}

I'm sorry I didn't mention this earlier but I have been using a test case to run the program, which is how I know it's not running correctly even though the compiler says there are no errors.

Given the data file

3
26
32
3523011938638144
619232
1
100

Which is supposed to result in

58
832
3523011939257376
2181561728786775185408
101
100

The program puts out
5
8
35230119
3925
10
1

With the current code.

Obviously this isn't correct, but what I've just discovered is quite curious. The first two result numbers, 5 and 8 make 58, which is what the addition function is supposed to display. So it goes with the others. It seems that instead of displaying the result of addition and multiplication, it's displaying the result of addition broken into two values. Quite odd.

penance · #7 09-Oct-2005, 16:28

Changed the code again. Now the addition works correctly. The multiplication on the other hand keeps resulting in an empty stack. Working on it.

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Define the limit of the stacks.*/
#define MAXSTACK 100

/*Defines the structure of a stack.*/
typedef struct {
	int digits[MAXSTACK];
	int top;
}arraystack;

/*Pushes new item onto the stack.*/
void push(arraystack *x, int y);
/*Pops new item from the stack.*/
int pop(arraystack *x);
/*Pops items from stack and prints them.*/
void popprint(arraystack *x);
/*Addition function.*/
void addition(arraystack *x, arraystack *y);
/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y);
/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y);

/*Structs will be global.*/
arraystack value1;
arraystack value2;
arraystack dummy;
arraystack temp1;
arraystack result;

/*Name: Matthew Barak
PID: ma241840
Course: COP 3502
Assignment Number: 2
Title: Large Numbers
Program Description: Reads in numbers from an outside file, stores them in stacks,
and adds and multiplies them.
Date: 10/09/05
Bonus Part Attempted: No
Created In: Visual C++
*/

int main(void)
{
	/*Variables for file input.*/
	FILE *ifp;
	char filename[30];
	/*Variables for loops.*/
	int counter, i, j;
	/*Variables for strings.*/
	char num1[100];
	char num2[100];
	/*Variables for conversion.*/
	char c1;
	int digit = 0;

	/*Initialize top of stacks.*/
	value1.top = -1;
	value2.top = -1;
	dummy.top = -1;
	temp1.top = -1;
	result.top = -1;

	/*Ask for input file.*/
	printf("Please enter the filename of the file you wish to open: ");
	scanf("%s", filename);

	/*Open input file.*/
	ifp = fopen(filename, "r");

	/*Get number of digit sets from file.*/
	fscanf(ifp, "%d", &counter);

	/*For the number of digits in the file:*/
	for (i = 0; i < counter; i++) {
		/*Read in the first number.*/
		fscanf(ifp, "%s", num1);
		/*Read in the next number.*/
		fscanf(ifp, "%s", num2);
		/*Convert first number into a digit and push it into the first array.*/
		j = 0;
		while(num1[j] != '\0') {
			c1 = num1[j];
			digit = c1 - '0';
			push(&value1, digit);
			j++;
		}
		/*Convert second number into a digit and push it into the second array.*/
		j = 0;
		while(num2[j] != '\0') {
			c1 = num2[j];
			digit = c1 - '0';
			push(&value2, digit);
			j++;
		}
		/*Reset stacks.*/
		dummy.top = -1;
		temp1.top = -1;
		result.top = -1;
		/*Add the two arrays.*/
		addition(&value1, &value2);
		/*Multiply the two arrays.*/
		multiplication(&value1, &value2);
	}

	/*Close input file.*/
	fclose(ifp);

	/*End program.*/
	return 0;
}

/*Pushes items onto a stack.*/
void push(arraystack *x, int y) {
	/*If the stack is full:*/
	if (x->top >= MAXSTACK - 1) {
		/*Error.*/
		printf("Stack is full.\n");
	}
	/*Otherwise:*/
	else {
		/*Stack top raises by 1 and new digit is added.*/
		x->top = x->top + 1;
		x->digits[x->top] = y;
	}
}

/*Pops items from a stack.*/
int pop(arraystack *x) {
	int y;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and stack top lowers by 1.*/
		y = x->digits[x->top];
		x->top = x->top - 1;
	}
	return y;
}

/*Pops items from stack and prints them.*/
void popprint(arraystack *x) {
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*Digits are popped and printed.*/
		while (x->top >= 0) {
			printf("%d", x->digits[x->top]);
			x->top = x->top - 1;
		}
	}
	printf("\n");
}

/*Addition function.*/
void addition(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop(y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry == 1) {
		/*Push carry onto stack.*/
		push(&result, carry);
	}
	/*Call popprint and send result.*/
	popprint(&result);
}

/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variable for deciding factor.*/
	int decide = 0;
	/*Variable for loop.*/
	int i;
	/*Variables for product.*/
	int num1 = 0;
	int num2 = 0; 
	int product;
	/*Variable for printing.*/
	int digit = 0;
	/*While second stack is not empty:*/
	while (y->top >= 0) {
		/*Add the necessary zeros to first temp stack.*/
		for (i = 0; i < decide; i++) {
			push(&temp1, 0);
		}
		/*Dummy stack is equivalent to first value stack.*/
		for (i = 0; i <= x->top; i++) {
			dummy.digits[i] = x->digits [i];
		}
		/*Pop value from second value stack.*/
		num2 = pop(y);
		/*For the duration of dummy stack:*/
		while (dummy.top >= 0) {
			/*Pop value from dummy stack.*/
			num1 = pop(&dummy);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(&temp1, product);
			}
			/*If product is 10 or greater:*/
			else {
				/*Value of product % 10 is pushed onto stack.*/
				product = product % 10;
				push(&temp1, product);
				/*Value of (product-(product%10))/10 becomes carry.*/
				carry = (product-(product%10))/10;
			}
		}
		/*If second temp stack is empty:*/
		if (result.top < 0) {
			/*Result stack is first temp stack.*/
			for (i = 0; i <= temp1.top; i++) {
				result.digits[i] = temp1.digits [i];
			}
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Otherwise:*/
		else {
			/*Add two temp stacks together.*/
			addformult(&temp1, &result);
			/*First temp stack is emptied.*/
			temp1.top = -1;
		}
		/*Add 1 to deciding factor.*/
		decide = decide + 1;
	}
	/*Call popprint and print result.*/
	popprint(&result);
}

/*Revised addition function for use with multiplication.*/
arraystack *addformult(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop (y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry ==  1) {
		/*Push carry onto stack.*/
		push (&result, carry);
	}
	/*Send result to multiplication.*/
	return &result;
}

penance · #8 09-Oct-2005, 18:22

So, I rewrote the program a bit so now nothing is global. The addition still works fine, but the multiplication isn't. I don't know what's wrong with it. I've got it so that now it still spits out "Stack is empty" for the first two responses and a large number for the third, which doesn't really help my problem any. Anyone have any suggestions?

CPP / C++ / C Code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*Define the limit of the stacks.*/
#define MAXSTACK 100

/*Defines the structure of a stack.*/
typedef struct {
	int digits[MAXSTACK];
	int top;
}arraystack;

/*Pushes new item onto the stack.*/
void push(arraystack *x, int y);
/*Pops new item from the stack.*/
int pop(arraystack *x);
/*Pops items from stack and prints them.*/
void popprint(arraystack *x);
/*Addition function.*/
void addition(arraystack *x, arraystack *y, arraystack *z);
/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y, arraystack *z, arraystack *a, arraystack *b);
/*Revised addition function for use with multiplication.*/
arraystack addformult(arraystack *x, arraystack *y);

int main(void)
{
	/*Variables for file input.*/
	FILE *ifp;
	char filename[30];
	/*Variables for loops.*/
	int counter, i, j;
	/*Variables for strings.*/
	char num1[100];
	char num2[100];
	/*Variables for conversion.*/
	char c1;
	int digit = 0;

	/*Stacks.*/
	arraystack add1;
	arraystack add2;
	arraystack mult1;
	arraystack mult2;
	arraystack dummy;
	arraystack temp1;
	arraystack result;
	
	/*Initialize top of stacks.*/
	add1.top = -1;
	add2.top = -1;
	mult1.top = -1;
	mult2.top = -1;
	dummy.top = -1;
	temp1.top = -1;
	result.top = -1;

	/*Ask for input file.*/
	printf("Please enter the filename of the file you wish to open: ");
	scanf("%s", filename);

	/*Open input file.*/
	ifp = fopen(filename, "r");

	/*Get number of digit sets from file.*/
	fscanf(ifp, "%d", &counter);

	/*For the number of digits in the file:*/
	for (i = 0; i < counter; i++) {
		/*Read in the first number.*/
		fscanf(ifp, "%s", num1);
		/*Read in the next number.*/
		fscanf(ifp, "%s", num2);
		/*Convert first number into a digit and push it into the first array.*/
		j = 0;
		while(num1[j] != '\0') {
			c1 = num1[j];
			digit = c1 - '0';
			push(&add1, digit);
			push(&mult1, digit);
			j++;
		}
		/*Convert second number into a digit and push it into the second array.*/
		j = 0;
		while(num2[j] != '\0') {
			c1 = num2[j];
			digit = c1 - '0';
			push(&add2, digit);
			push(&mult2, digit);
			j++;
		}
		/*Add the two arrays.*/
		addition(&add1, &add2, &result);
		/*Clear result.*/
		result.top = -1;
		/*Multiply the two arrays.*/
		multiplication(&mult1, &mult2, &temp1, &dummy, &result);
	}

	/*Close input file.*/
	fclose(ifp);

	/*End program.*/
	return 0;
}

/*Pushes items onto a stack.*/
void push(arraystack *x, int y) {
	/*If the stack is full:*/
	if (x->top >= MAXSTACK - 1) {
		/*Error.*/
		printf("Stack is full.\n");
	}
	/*Otherwise:*/
	else {
		/*Stack top raises by 1 and new digit is added.*/
		x->top = x->top + 1;
		x->digits[x->top] = y;
	}
}

/*Pops items from a stack.*/
int pop(arraystack *x) {
	int y;
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*New digit is popped and stack top lowers by 1.*/
		y = x->digits[x->top];
		x->top = x->top - 1;
	}
	return y;
}

/*Pops items from stack and prints them.*/
void popprint(arraystack *x) {
	/*If the stack is empty:*/
	if (x->top < 0) {
		/*Error.*/
		printf("Stack is empty.\n");
	}
	/*Otherwise:*/
	else {
		/*Digits are popped and printed.*/
		while (x->top >= 0) {
			printf("%d", x->digits[x->top]);
			x->top = x->top - 1;
		}
	}
	printf("\n");
}

/*Addition function.*/
void addition(arraystack *x, arraystack *y, arraystack *z) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop(y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(z, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(z, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry == 1) {
		/*Push carry onto stack.*/
		push(z, carry);
	}
	/*Call popprint and send result.*/
	popprint(z);
}

/*Multiplication function.*/
void multiplication(arraystack *x, arraystack *y, arraystack *z, arraystack *a, arraystack *b) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variable for deciding factor.*/
	int decide = 0;
	/*Variable for loop.*/
	int i;
	/*Variables for product.*/
	int num1 = 0;
	int num2 = 0; 
	int product;
	/*While second stack is not empty:*/
	while (y->top >= 0) {
		/*Add the necessary zeros to first temp stack.*/
		for (i = 0; i < decide; i++) {
			push(z, 0);
		}
		/*Dummy stack is equivalent to first value stack.*/
		for (i = 0; i <= x->top; i++) {
			a->digits[i] = x->digits[i];
			a->top = x->top;
		}
		/*Pop value from second value stack.*/
		num2 = pop(y);
		/*For the duration of dummy stack:*/
		while (a->top >= 0) {
			/*Pop value from dummy stack.*/
			num1 = pop(a);
			/*Multipy numbers and add carry to get product.*/
			product = (num1 * num2) + carry;
			/*If product is less than 10:*/
			if (product < 10) {
				/*Carry equals zero.*/
				carry = 0;
				/*Product is pushed onto first temp stack.*/
				push(z, product);
			}
			/*If product is 10 or greater:*/
			else {
				/*Value of product % 10 is pushed onto stack.*/
				product = product % 10;
				push(z, product);
				/*Value of (product-(product%10))/10 becomes carry.*/
				carry = (product-(product%10))/10;
			}
		}
		/*If second temp stack is empty:*/
		if (b->top < 0) {
			/*Result stack is first temp stack.*/
			for (i = 0; i <= z->top; i++) {
				b->digits[i] = z->digits [i];
				b->top = z->top;
			}
		}
		/*Otherwise:*/
		else {
			/*Add two temp stacks together.*/
			for (i = 0; i <= z->top; i++) {
				b->digits[i] = addformult(z, b).digits [i];
				b->top = addformult(z, b).top;
			}
		}
		/*Add 1 to deciding factor.*/
		decide = decide + 1;
	}
	/*Call popprint and print result.*/
	popprint(b);
}

/*Revised addition function for use with multiplication.*/
arraystack addformult(arraystack *x, arraystack *y) {
	/*Variable for carry.*/
	int carry = 0;
	/*Variables for adding.*/
	int num1, num2, sum;
	/*Variable for printing.*/
	int digit = 0;
	/*Result stack.*/
	arraystack result;
	result.top = -1;
	/*While one stack is not empty:*/
	while (x->top >= 0 || y->top >= 0) {
		/*If first stack is empty:*/
		if (x->top < 0) {
			/*First addend is 0.*/
			num1 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the first addend.*/
			num1 = pop(x);
		}
		/*If second stack is empty:*/
		if (y->top < 0) {
			/*Second addend is 0.*/
			num2 = 0;
		}
		/*Otherwise:*/
		else {
			/*Pop the second addend.*/
			num2 = pop (y);
		}
		/*Add num1, num2, and carry to get the sum.*/
		sum = num1 + num2 + carry;
		/*If sum < 10:*/
		if (sum < 10) {
			/*Carry = 0.*/
			carry = 0;
			/*Sum is pushed on the result stack.*/
			push(&result, sum);
		}
		/*Else:*/
		else {
			/*Unit of result is pushed on result stack.*/
			sum = sum % 10;
			push(&result, sum);
			/*Carry = 1.*/
			carry = 1;
		}
	}
	/*If carry is 1 after loop:*/
	if (carry ==  1) {
		/*Push carry onto stack.*/
		push (&result, carry);
	}
	/*Send result to multiplication.*/
	return result;
}

penance · #9 10-Oct-2005, 07:35

Apologies to the admin. I did not realize there were specific tags for C code. Anyway, as near as I can tell, somewhere in the multiplication function some pop operation is popping an empty stack, but I can't figure out where or how. If someone could please assist me in rectifying this situation I would be most grateful.

davekw7x · #10 10-Oct-2005, 09:25

Quote:

Originally Posted by penance

Apologies to the admin. I did not realize there were specific tags for C code. Anyway, as near as I can tell, somewhere in the multiplication function some pop operation is popping an empty stack, but I can't figure out where or how. If someone could please assist me in rectifying this situation I would be most grateful.

There are thee possibilities that come to mind (I have not gone through your code to try to find which of them apply; that's your job):

1. Your algorithm for multiplication is wrong.

2. Your code doesn't actually implement the algorithm that you had in mind.

3. All of the above.

Since your program is running, but giving the wrong answer (no answer in this case), make the program tell you what it's working with. You might have to put many, many printf statements to get to the bottom of things. Sometimes it's easier to run through the code with pencil-and-paper for a simple example (pretend you are the computer); sometimes it's more time-effective to let the computer do the work. So in your multiplication routine, you could have something like the following:

CPP / C++ / C Code:

  printf("in multiplication: x->top = %d, y=>top = %d\n", x->top, y->top);
  while (y->top >= 0) {
    for (i = 0; i < decide; i++) {
      printf("i = %d, decide = %d, pushing 0 to z\n", i, decide);
      push(z, 0);
    }
    for (i = 0; i <= x->top; i++) {
      printf("i = %d: x->top = %d, x->digits[i] = %d\n", i, x->top);
      a->digits[i] = x->digits[i];
    }
    a->top = x->top;
/* etc */

Regards,

Dave

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
queues, stacks or lists?	zidanefreak01	C++ Forum	22	15-Aug-2005 21:13
stacks or queue	zidanefreak01	MS Visual C++ / MFC Forum	1	08-Aug-2005 13:40
Issue with stacks	CronoX	C++ Forum	10	10-Mar-2004 15:30

Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks

Re: Help With Stacks