Thread: stack and recursion help needed!

  1. #1
    Registered User
    Join Date
    May 2002

    stack and recursion help needed!

    Tonights problem is this:

    Main function MUST look like this:

    void main()
    { int input;

    I'm trying to implement a class of STACK, and have three different outputs : stack, recursion, and no stack nor recursion.

    Here is example of running program:

    Please insert a number for binary representation:
    The binary representation of 10 is (using stack): 1010
    The binary representation of 10 is (using recursion): 1010
    The binary representation of 10 is (no stack nor recursion): 1010

    This is what I have so far:

    using std::cout;
    using std::cin;
    using std::endl;
    using std::istream;
    using std:stream;

    class STACK{
    int data[100];
    int top;
    int n;
    void getinput();
    void push(int target) {data[top++] = target;};
    int isEmpty(){return !top;};
    int pop() {return data[--top];};

    int print_stack(int n)
    if (n == 0)
    return n;

    cout << "The binary representation of 10 is (using stack): " << n.pop() << endl;

    STACK getinput(int input)
    { int n;
    cout << "Please enter a number for binary representation: \n";
    cin >> n;

    Ok, I'll admit, I'm out of my league here. I'm not sure where to go. I know I have big problems with the above. Please help!!

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    for starters, in your print_stack function it assumes a value of 10 every time (which isn't right...).

    using stack: push and pop values. figure out a way find one bit, then push that bit. then pop the bits out and print them.

    using recursion: give a number to your function, and decrease it as you check for bits. then re-enter with the new number. you might want a separate counter to count down accurately. either way, once the number reaches 0, stop reentering and return the result.

    using neither: this means iteration. simply create a for loop, check for bits each time, and print out the result.

  3. #3
    You first have to decide whether all functions called from main() need to be members of STACK or not-----probably not from what I can tell.

    Then you need a way to convert user input into binary form. I suspect the method you use to convert can be done in conjunction with a stack, a recursive function, and neither of those--maybe an array or a list.

    Then you need to develop a STACK class. You have a good start on that. You need a default constructor however. Within the default constructor you need to initialize top to a value. Otherwise, the ++ and -- operators have no meaningful data to work with.

  4. #4
    I assume that n is an integer, and presumably has the value of input.

    input can be passed by reference to getinput() so that it's value in main() changes with the user input obtained in getinput(). input can then be passed by value to the other functions (in the form of n) so it's value in main() is not changed.

    One algorhythm to derive the binary equivalent of a decimal number is to use the modulo operator with the value 2 and then divide n by 2 unti n == 0. This will yield the binary placeholders in reverse order:

    n = 10;
    n % 2 = 0; <-----this is least significant binary placeholder
    n = n/2;<----n now equals 5 using integer math
    n % 2 = 1;<------next least significant binary placeholder
    n /= 2;<-----n now equals 2 using integer math
    n % 2 = 0;<------next binary placeholder
    n /= 2;<----n now equals 1 using integer math
    n % 2 = 1<------most significant placeholder
    n /= 0;<-----stop indicator

    Using that algorhythm you can use a loop to do the calculations, pushing each value returned by the % onto the stack until n == 0. Then pop each value from the stack in sequence and display it to the screen

    Using that algorhythm you can devise a recursive function that is passed n and gets re-called with each new value of n returned by the /= operation until n == 0.

    Using that algorhythm you can use a loop to do the calculations assigning the value returned by the % operation to successive elements of an array until n == 0. Then start at the end of array and read each value out of the array from back to front so to speak displaying each value to the screen.

    Now, you need to finish up your stack class so you use an instance of that class as a local variable in the first scenario above. Develop the above functions outside the class.

    It's all up to you now.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Recursive function crashes.
    By samus250 in forum C Programming
    Replies: 9
    Last Post: 01-16-2008, 02:58 PM
  2. Confused about Memory
    By gL_nEwB in forum C++ Programming
    Replies: 22
    Last Post: 06-20-2006, 07:32 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. FloodFill stack overflow
    By VirtualAce in forum A Brief History of
    Replies: 22
    Last Post: 04-09-2002, 04:21 PM