By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,234 Members | 1,941 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,234 IT Pros & Developers. It's quick & easy.

help with a stack problem in c++

P: 94
I am by no means an ultra slick programmer and my problem solving skills.. well they leave much to be desired. That being said I have been working on the following problem for the past few days and have yet to find a solution.

My program is supposed to read in a txt file which contains 2 lines of numbers. Program reads the file and stores each line as a string, then converts each character to an integer. Once char is converted to an int the program pushes each integer onto the stack (note: each new node on the stack is a digit from 0 - 9). My program is fine up till this point.

Here is the problem. I have to add the two stacks together (simple enough at first thought). First the program takes the top of each stack and adds them together. However, if the result is > 9 I run into a problem. The carry value. I will paste a sample output my program gives after my code so you can see exactly what is happening. Also the linkedStack.h is just a simple class that pushes and pops (pretty textbook stuff there).

Expand|Select|Wrap|Line Numbers
  1. #include "stdafx.h"
  2. #include "linkedStack.h"
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <iostream>
  6. #include <cstring>
  7. #include <fstream>
  8. using namespace std;
  9.  
  10. int _tmain(int argc, _TCHAR* argv[])
  11. {
  12.     linkedStackType<int> stack1;    //Creating first stack object 
  13.     linkedStackType<int> stack2;    //Creating second stack Object
  14.     linkedStackType<int> stackSum;  //Creating Stack object for sum
  15.  
  16.     char recordIn[999];                //Variable to gather a string that is at most 999 characters long
  17.     int num;                        //Variable to store num (see lines 41 and 51)
  18.     int stack1Length = 0;            //Variable for checking size of the string read into program (stack1)
  19.     int stack2Length = 0;            //Variable for checking size of the string read into program (stack2)
  20.     int sumOne = 0;                    //Variable for ones digit
  21.     int sumCarry = 0;                //Variable for tens digit
  22.     int sumX;
  23.     int sumTwo;
  24.  
  25.     ifstream infile;
  26.     stack1.initializeStack();
  27.     stack2.initializeStack();
  28.     stackSum.initializeStack();
  29.  
  30.     infile.open("largeIntegers.txt");
  31.     if(!infile)
  32.     {
  33.         cout<<"Cannot open file."<<endl;
  34.     }
  35.     else
  36.     {
  37.         infile.getline(recordIn, 100);        //Get first line of text file
  38.         stack1Length = strlen(recordIn);    //Check to see the size of the stack (see for loop below)
  39.         while(!infile.eof())                
  40.         {
  41.             for(int i = 0; i < stack1Length; i++)
  42.             {    
  43.                 num = recordIn[i] - '0';    //Convert char to integer
  44.                 stack1.push(num);            //Push converted integer onto the stack
  45.                 cout<<recordIn[i];            //Displaying entire stack
  46.             }
  47.             cout<<"\n";
  48.  
  49.             infile.getline(recordIn, 100);
  50.             stack2Length = strlen(recordIn);
  51.             for(int i = 0; i < stack2Length; i++)
  52.             {    
  53.                 num = recordIn[i] - '0';    //Convert char to integer
  54.                 stack2.push(num);            //Push converted integer onto the stack
  55.                 cout<<recordIn[i];            //Displaying entire stack
  56.             }
  57.             cout<<"\n";
  58.             break;
  59.         }
  60.     }
  61. //*********************** Adding the stacks ***********************//
  62.     while(stack2.stackTop != NULL)
  63.     {
  64.         int sum = stack1.top() + stack2.top();
  65.         if(sum >= 10)
  66.         {
  67.             sumOne = sum % 10;
  68.             sumCarry = sum / 10;
  69.             stackSum.push(sumOne);
  70.         }
  71.         else
  72.         {
  73.             if(sumCarry == 0)
  74.             stackSum.push(sum);
  75.             else
  76.             {
  77.                 sumTwo = sum + sumCarry;
  78.                 stackSum.push(sumTwo);
  79.             }
  80.         }
  81.         stack1.pop();
  82.         stack2.pop();
  83.     }
  84.  
  85.     while(stack1.stackTop != NULL)
  86.     {
  87.         sumX = stack1.top() + 0 + sumCarry;    //adding sumCarry incase of any carry
  88.         stackSum.push(sumX);
  89.         stack1.pop();
  90.     }
  91.  
  92.     while(stackSum.stackTop != NULL)
  93.     {
  94.         cout<<stackSum.top();
  95.         stackSum.pop();
  96.     }
  97.     cout<<"\n"<<"\n"<<endl;
  98.     return 0;
  99. }
  100.  
*** Sample output ***
6788
145
7923


Press any key to continue . . .
*** /end sample ***

6788 is the first line of the txt file
145 is the second line of the txt file
the third line there should be 6933 but because of my carrying problem its rather messed up. Any help on this issue would be greatly appreciated.


Cheers;
Dav3
Nov 5 '06 #1
Share this Question
Share on Google+
5 Replies


Expert 100+
P: 1,510
the problem appears to be in adding the stacks
(1) if sum>=10 you don't add the carry from a previous addition
(2) if sum < 10 you don't zero the carry after adding it

updated code (to test it I changed it to use the STL <stack>)
Expand|Select|Wrap|Line Numbers
  1. #include <stack>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <iostream>
  5. #include <cstring>
  6. #include <fstream>
  7. using namespace std;
  8.  
  9. int main()
  10. {
  11.     stack<int> stack1;    //Creating first stack object 
  12.     stack<int> stack2;    //Creating second stack Object
  13.     stack<int> stackSum;  //Creating Stack object for sum
  14.  
  15.     char recordIn[999];                //Variable to gather a string that is at most 999 characters long
  16.     int num;                        //Variable to store num (see lines 41 and 51)
  17.     int stack1Length = 0;            //Variable for checking size of the string read into program (stack1)
  18.     int stack2Length = 0;            //Variable for checking size of the string read into program (stack2)
  19.     int sumOne = 0;                    //Variable for ones digit
  20.     int sumCarry = 0;                //Variable for tens digit
  21.     int sumX;
  22.     int sumTwo;
  23.  
  24.     ifstream infile;
  25.     //stack1.initializeStack();
  26.     //.initializeStack();
  27.     //.initializeStack();
  28.  
  29.     infile.open("largeIntegers.txt");
  30.     if(!infile)
  31.     {
  32.         cout<<"Cannot open file."<<endl;
  33.     }
  34.     else
  35.     {
  36.         infile.getline(recordIn, 100);        //Get first line of text file
  37.         stack1Length = strlen(recordIn);    //Check to see the size of the stack (see for loop below)
  38.         while(!infile.eof())                
  39.         {
  40.             for(int i = 0; i < stack1Length; i++)
  41.             {    
  42.                 num = recordIn[i] - '0';    //Convert char to integer
  43.                 stack1.push(num);            //Push converted integer onto the stack
  44.                 cout<<recordIn[i];            //Displaying entire stack
  45.             }
  46.             cout<<"\n";
  47.  
  48.             infile.getline(recordIn, 100);
  49.             stack2Length = strlen(recordIn);
  50.             for(int i = 0; i < stack2Length; i++)
  51.             {    
  52.                 num = recordIn[i] - '0';    //Convert char to integer
  53.                 stack2.push(num);            //Push converted integer onto the stack
  54.                 cout<<recordIn[i];            //Displaying entire stack
  55.             }
  56.             cout<<"\n";
  57.             break;
  58.         }
  59.     }
  60. //*********************** Adding the stacks ***********************//
  61.     while(!stack2.empty() )
  62.     {
  63.         int sum = stack1.top() + stack2.top();
  64.         if(sum >= 10)
  65.         {
  66.             sumOne = sum % 10;
  67.             if(sumCarry != 0)  sumOne =sumOne+ sumCarry; //**added
  68.             sumCarry = sum / 10;
  69.             stackSum.push(sumOne);
  70.         }
  71.         else
  72.         {
  73.             if(sumCarry == 0)
  74.             stackSum.push(sum);
  75.             else
  76.             {
  77.                 sumTwo = sum + sumCarry;
  78.                 stackSum.push(sumTwo);
  79.                 sumCarry=0;         //**** added
  80.             }
  81.         }
  82.         stack1.pop();
  83.         stack2.pop();
  84.     }
  85.  
  86.     while(!stack1.empty() )
  87.     {
  88.         sumX = stack1.top() + 0 + sumCarry;    //adding sumCarry incase of any carry
  89.         stackSum.push(sumX);
  90.         stack1.pop();
  91.     }
  92.  
  93.     while(!stackSum.empty() )
  94.     {
  95.         cout<<stackSum.top();
  96.         stackSum.pop();
  97.     }
  98.     cout<<"\n"<<"\n"<<endl;
  99.     return 0;
  100. }
  101.  
a run now gives
6788
145
6933


better test it more thoroughly though!
Nov 5 '06 #2

P: 94
Thank you so much. I knew it was something minor I was missing.
Nov 5 '06 #3

P: 94
ah this solution only appears to work if the second number is only 1 digit smaller than the first.

9999
11
101010 <<<-- not 10010

*sigh*
Nov 5 '06 #4

Expert 100+
P: 1,510
ah this solution only appears to work if the second number is only 1 digit smaller than the first.

9999
11
101010 <<<-- not 10010

*sigh*
try this code
Expand|Select|Wrap|Line Numbers
  1. //#include "stdafx.h"
  2. #include <stack>
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <iostream>
  6. #include <cstring>
  7. #include <fstream>
  8. using namespace std;
  9.  
  10. int main()
  11. {
  12.     stack<int> stack1;    //Creating first stack object 
  13.     stack<int> stack2;    //Creating second stack Object
  14.     stack<int> stackSum;  //Creating Stack object for sum
  15.  
  16.     char recordIn[999];                //Variable to gather a string that is at most 999 characters long
  17.     int num;                        //Variable to store num (see lines 41 and 51)
  18.     int stack1Length = 0;            //Variable for checking size of the string read into program (stack1)
  19.     int stack2Length = 0;            //Variable for checking size of the string read into program (stack2)
  20.     int sumOne = 0;                    //Variable for ones digit
  21.     int sumCarry = 0;                //Variable for tens digit
  22.     int sumX;
  23.     int sumTwo;
  24.  
  25.     ifstream infile;
  26.     //stack1.initializeStack();
  27.     //.initializeStack();
  28.     //.initializeStack();
  29.  
  30.     infile.open("largeIntegers.txt");
  31.     if(!infile)
  32.     {
  33.         cout<<"Cannot open file."<<endl;
  34.     }
  35.     else
  36.     {
  37.         infile.getline(recordIn, 100);        //Get first line of text file
  38.         stack1Length = strlen(recordIn);    //Check to see the size of the stack (see for loop below)
  39.         while(!infile.eof())                
  40.         {
  41.             for(int i = 0; i < stack1Length; i++)
  42.             {    
  43.                 num = recordIn[i] - '0';    //Convert char to integer
  44.                 stack1.push(num);            //Push converted integer onto the stack
  45.                 cout<<recordIn[i];            //Displaying entire stack
  46.             }
  47.             cout<<"\n";
  48.  
  49.             infile.getline(recordIn, 100);
  50.             stack2Length = strlen(recordIn);
  51.             for(int i = 0; i < stack2Length; i++)
  52.             {    
  53.                 num = recordIn[i] - '0';    //Convert char to integer
  54.                 stack2.push(num);            //Push converted integer onto the stack
  55.                 cout<<recordIn[i];            //Displaying entire stack
  56.             }
  57.             cout<<"\n";
  58.             break;
  59.         }
  60.     }
  61. //*********************** Adding the stacks ***********************//
  62.     while(!stack2.empty() )
  63.     {
  64.         int sum = stack1.top() + stack2.top() + sumCarry;;  // ****
  65.         sumCarry=0;  //****
  66.         if(sum >= 10)
  67.         {
  68.             sumOne = sum % 10;
  69.             sumCarry = sum / 10;
  70.             stackSum.push(sumOne);
  71.         }
  72.         else
  73.             stackSum.push(sum);
  74.         stack1.pop();
  75.         stack2.pop();
  76.     }
  77.  
  78.     while(!stack1.empty() )
  79.     {
  80.         sumX = stack1.top() + 0 + sumCarry;    //adding sumCarry incase of any carry
  81.         stackSum.push(sumX);
  82.         stack1.pop();
  83.     }
  84.  
  85.     while(!stackSum.empty() )
  86.     {
  87.         cout<<stackSum.top();
  88.         stackSum.pop();
  89.     }
  90.     cout<<"\n"<<"\n"<<endl;
  91.     return 0;
  92. }
  93.  
keep testing!
Nov 6 '06 #5

P: 94
Ha got it.

Thanks so much for your help:)
Nov 6 '06 #6

Post your reply

Sign in to post your reply or Sign up for a free account.