Stack conversion

[Kellaw]

How do you implement a binary number to convert into an equivalent decimal number using stack in C++.I am having a headache here.I have been thinking the past 2 days but without much knowledge in C++ i am partially dead. Tried reading books but still can't figure it out and time is running short on me.Please advice and help.Thanks in advance

[Kellaw]

I saw a previous thread of code but i think it is not using stacks
#include <string.h> int btoi(char *buf) { // Create local variables int count, tmp; int retValue = 0; // Get length of string count = strlen(buf); // Go through string one byte at a time (backwards) for (i = 0; i <= count; i++) { // If a number '1' was found if (buf[count-i] == '1') { tmp = 1; for (j = 1; j < i; j++) tmp *= 2; retValue += tmp; } } // Return our decimal value return retValue; }

[Salem]

There are essentially two steps to the problem, given
void foo ( int num );

1. do something with num % 2
2. call foo ( num / 2 );

Changing the order of those two steps changes what happens - feel free to experiment.

Oh, and you also need something to decide when to stop recursing otherwise you'll just go on until you run out of stack.

[iamthwee]

There are essentially two steps to the problem, given
void foo ( int num );

1. do something with num % 2
2. call foo ( num / 2 );

Changing the order of those two steps changes what happens - feel free to experiment.

Oh, and you also need something to decide when to stop recursing otherwise you'll just go on until you run out of stack.

Yes essentially you are using the stack instead of recursion. So if you understand recursion than that shouldn't be a problem.

You would use while

((! Stack.empty())

to test if your stack is empty.
There is plenty of information on the web documenting the use of the stack from the STL.

[Kellaw]

Yes essentially you are using the stack instead of recursion. So if you understand recursion than that shouldn't be a problem.

You would use while

((! Stack.empty())

to test if your stack is empty.
There is plenty of information on the web documenting the use of the stack from the STL.

you mean my program is already using stack?actually i know nothing about stack and i just started c++ a week ago. i am still learning now.

[iamthwee]

you mean my program is already using stack?actually i know nothing about stack and i just started c++ a week ago. i am still learning now.

huh?

You started programming a week ago and you're already learning data structures? Hmm, you must have an incompetent teacher like myself. LOL.

Anyhow, let's try and make sense of this.

>you mean my program is already using stack

By this are you asking, 'is there already a facility in c++ such that I don't have to write my own stack, templated procedure?' If that's the case then yes. Using 'stack' from the STL will provide you will all the rudimentary things you need to do. Like push and pop stuff from the stack.

>i am still learning now

me too welcome to the club.

[Kellaw]

huh?

You started programming a week ago and you're already learning data structures? Hmm, you must have an incompetent teacher like myself. LOL.

Anyhow, let's try and make sense of this.

>you mean my program is already using stack

By this are you asking, 'is there already a facility in c++ such that I don't have to write my own stack, templated procedure?' If that's the case then yes. Using 'stack' from the STL will provide you will all the rudimentary things you need to do. Like push and pop stuff from the stack.

>i am still learning now

me too welcome to the club.

well i am learning on my own.i need to come up with this project and the F***ing lecturer only know how to ask me to refer to books. he says i should learn how to write up a stack and use the stack as binary to be converted to decimal.he say he learn that in a day when he started learning.it means i basicallt have to do the same lol.is there a specific function to push and pop.i only know the basic function and a little on recursion.

[Lerner]

>>is there a specific function to push and pop

No. It depends on the implementation. If you are going to implement your own stack then you get to decide how do set things up. If you are using a third party implementation then you use the functions provided without worrying about the implementation as long as they meet your needs.

[Kellaw]

>>is there a specific function to push and pop

No. It depends on the implementation. If you are going to implement your own stack then you get to decide how do set things up. If you are using a third party implementation then you use the functions provided without worrying about the implementation as long as they meet your needs.

i am supposed to come up with the stack too.i just called my lecturer.he sounds sarcastic.he says "do i look like an idiot to you?if you are not gona do the stack you expect me to do it?"
just felt like slapping him lol

[Lerner]

The easiest answer is that you will probably find any number of stack implementations by searching the web. However, you will learn more by doing it yourself.

The two versions of implementing a stack that I'm most familiar with use either an array or a list as the underlying container, and build the stack as a wrapper around the underlying container. I am only familiar with implementing stacks using C++, so if you want to do it in C then I'll be of less help.

With an array based stack class you declare an array of a given size, you can use either static or dynamic memory, and then have a second member variable keep track of the last index actually used. Popping then amounts to decrementing the last index and pushing should be straightforward from what I've said already.

With a list, I find it easiest to always push/pop from the head of the list.

This information plus what Salem gave you should put you well on the way to at least roughing out your project. Post code and specific questions if necessary and someone will probably help from there.

[Kellaw]

The easiest answer is that you will probably find any number of stack implementations by searching the web. However, you will learn more by doing it yourself.

The two versions of implementing a stack that I'm most familiar with use either an array or a list as the underlying container, and build the stack as a wrapper around the underlying container. I am only familiar with implementing stacks using C++, so if you want to do it in C then I'll be of less help.

With an array based stack class you declare an array of a given size, you can use either static or dynamic memory, and then have a second member variable keep track of the last index actually used. Popping then amounts to decrementing the last index and pushing should be straightforward from what I've said already.

With a list, I find it easiest to always push/pop from the head of the list.

This information plus what Salem gave you should put you well on the way to at least roughing out your project. Post code and specific questions if necessary and someone will probably help from there.

i am doing it in C++ and i dont have the faintest idea how to create a stack.i only know how to enter variables but not stacks :sad:
code such as
int x;
cin>> x;
cout<< x; :sad: :cry:

[iamthwee]

i am doing it in C++ and i dont have the faintest idea how to create a stack.i only know how to enter variables but not stacks :sad:
code such as
int x;
cin>> x;
cout<< x; :sad: :cry:

Ha ha, you need to go back to school and study sum more kiddo.

Does your stack need to be built using templates?

[dreamreaver]

I believe its too hard to use templates lol..why not just use the notes given by the lecturer and use the stack example and build your own template..since he/she taught you that..

[iamthwee]

>I believe its too hard to use templates

Maybe, although they afford a great deal of advantages, such as allowing one to create a stack of a generic type; char, int, string etc.

We'll wait until he gets back. I hope he knows what object-orientated design is at the very least. Most creations of stacks rely on this principle, or so I've read. Tee he he.

[Kellaw]

nope not involving template.somehow i got a book which gives me the own declaration.i ask my friend and he say the templete is too complex

const int MAX_STACK = 15 ;
Typedef int stackItemType ;

class stackClass
    {
        public :
            stackClass () ;
            bool StackIsEmpty () const ;
            void Push ( stackItemType NewItem , bool& Success ) ;
            void Pop ( stackItemType& StackTop , bool& Success ) ;
            void GetStackTop ( stackItemType& StackTop , bool& success ) const ;

        Private :
            stackItemType items [ MAX_STACK ] ;
            int Top ;
    }

[Lerner]

As a start the code you posted looks okay. I might change a few things here and there to simplify it a bit so you don't have so much stuff in the way of understanding about the basic protocols, but it should work. Basically, it's creating a stack class using an array called items as the underlying container and using the variable Top to indicate the last index used (top could also be the first index available if you prefer, but I prefer the last index used).

Now it's time to start implementing each of the functions.

I'll start with the assumption you know that array indexes are zero based. Given that, you will need to use some integer value for top that could never be used as an index of items to indicate when there are no items in the array. Assign that value to top in the constructor and evaluate for that value when determining whether the stack is empty or not. Then when you push a add a new item to items increment top and when you remove an item from items decrease the value of top. You will probably want to do some bounds checking to be sure you don't try to pop from an empty stack or try push an item on a stack that's already full, but that is a level of sophistication above and beyond the actual mechanism to push and pop.

Write just one function at a time, not all at once.

[Kellaw]

i have all the function here
the probs is that as i know stacks fills in like a tube and what is on the top need to go out first which means when i save a stack its in a reverse form.how do i continue from there?

const int MAX_STACK = 15 ;
Typedef int stackItemType ;

class stackClass
    {
        public :
            stackClass () ;
            bool StackIsEmpty () const ;
            void Push ( stackItemType NewItem , bool& Success ) ;
            void Pop ( stackItemType& StackTop , bool& Success ) ;
            void GetStackTop ( stackItemType& StackTop , bool& success ) const ;

        Private :
            stackItemType items [ MAX_STACK ] ;
            int Top ;
    }

stackClass :: stackClass () : Top ( -1 )
    {
    }

bool stackClass :: StackIsEmpty () const
    {   
        return bool ( Top < 0 ) ;
    }

void stackClass :: Push ( stackItemType NewItem , bool& Success )
    {   
        Success = bool ( Top < MAX_STACK - 1 ) ;

        if ( Success )
            {
                ++ Top ;
                Items [ Top ] = NewItem ;
            }
    }

void stackClass :: Pop ( stackItemType& StackTop , bool& Success )
    {
        Success = bool ( ! StackIsEmpty () ) ;

        if ( Success )
            {
                StackTop = Items [ Top ] ;
                -- Top ;
            }
    }

void stackClass :: GetStackTop ( stackItemType& StackTop , bool& Success ) const
    {
        Success = bool ( ! StackIsEmpty () ) ;

        if ( Success )
            {
                StackTop = Items [ Top ] ;
            }
    }

[iamthwee]

You might want to wack that in a header file or something.

Next step would be to test your stack implentation using a main().

Try simple stuff like pushing a bunch of numbers onto the stack then systematically popping them out, whilst at the same time displaying them on the screen.

[Kellaw]

How do i put them into a header file?Please advice.i learn arrays and i know it start with 0 then it goes on using a loop eg
for (i=0;1<10;i++)
cin>> array;

[iamthwee]

Well I can only assume your stack was built using notes you obtained from class.

With those notes you should also have a little snippnet detailing how you might actually use your stack inside int main().

You don't necessarily need to put your stack inside another header file but it's convenient to do so.

Look here's an example, using stack from the STL, it's content should be similar to your own.

#include <iostream>
#include <stack> //this is basically the utility you have been
                 //asked to design

using namespace std;

int main()
{
    stack <char> thwees_stack;//initialise stack
    thwees_stack.push('i'); //push chars onto the stack
    thwees_stack.push('a'); //push chars onto the stack
    thwees_stack.push('m'); //push chars onto the stack
    thwees_stack.push('t'); //push chars onto the stack
    thwees_stack.push('h'); //push chars onto the stack
    thwees_stack.push('w'); //push chars onto the stack
    thwees_stack.push('e'); //push chars onto the stack
    thwees_stack.push('e'); //push chars onto the stack
    
    while (! thwees_stack.empty()) //test if stack is empty
    {
        cout<<thwees_stack.top(); //print wat's at the top of da stack
        thwees_stack.pop(); //delete from da stack
    }
    
        cin.get();
}

[Kellaw]

Actually i got it from friend who gave me the photo copy of lecture notes.i dont have snippets on how to use them. I am not in a computer class but i am actually an engineering student.i need the binary converter because i am making a bar code using binary where a 1 = a line 0 = a a space.
my lecturer only tell me the howabout in doing my project.put it in a header file being convenient?what do you mean?

[Kellaw]

ok assuming the binary code is 10100 = 20
when i put it as cin >> stack
10100 does the digits separates itself or it goes all into one array cell?
lets say i key in 10100 the stack would pop out 0 followed by 0 then 1,0,1
which means the stack is in reverse?how do you convert when the stack is in reverse form?

Well I can only assume your stack was built using notes you obtained from class.

With those notes you should also have a little snippnet detailing how you might actually use your stack inside int main().

You don't necessarily need to put your stack inside another header file but it's convenient to do so.

Look here's an example, using stack from the STL, it's content should be similar to your own.

#include <iostream>
#include <stack> //this is basically the utility you have been
                 //asked to design

using namespace std;

int main()
{
    stack <char> thwees_stack;//initialise stack
    thwees_stack.push('i'); //push chars onto the stack
    thwees_stack.push('a'); //push chars onto the stack
    thwees_stack.push('m'); //push chars onto the stack
    thwees_stack.push('t'); //push chars onto the stack
    thwees_stack.push('h'); //push chars onto the stack
    thwees_stack.push('w'); //push chars onto the stack
    thwees_stack.push('e'); //push chars onto the stack
    thwees_stack.push('e'); //push chars onto the stack
    
    while (! thwees_stack.empty()) //test if stack is empty
    {
        cout<<thwees_stack.top(); //print wat's at the top of da stack
        thwees_stack.pop(); //delete from da stack
    }
    
        cin.get();
}

[iamthwee]

>but i am actually an engineering student

Hey dats kewl I wanna do that in two years time :sad:

>because i am making a bar code using binary where a 1 = a line 0 = a a space.

That's odd, I would assume that most real time applications, such as bar scanners would be written with C, or more precisely embedded C. Then of course you would use an analogue to digital converter etc etc. Or so me thinks. Tee he he.

Look kiddo, even if you don't have the notes to see how you might incorporate that into a main it should be fairly simple to do so. :rolleyes:

[iamthwee]

Sorry kiddo, I got school now, ask someone else to help. They probably no more than me. Tee he he.

[Kellaw]

when your times comes you can ask me ques lol.
its a project and the darn lecturer wants me to do it in C++.wonders why.of course there is always the easy way of getting a bar scanner and install the application software. i am learning here lol.

[Lerner]

For future reference, to keep the indentation formatting I hope you use when writing code in your text editor you will need to use code tags. You can read the FAQ about how to use them. It makes it much easier to read code when it is indented, and some folks here won't even try to read non-indented code.

Now that you have the code for a working stack class using C++ you need to use it in a working program to test it out, just like you were told before. Put some actual data in a stack and print it out again to see what happens. For example try putting the numbers 1, 2, and 3 on a stack and print it out. Then try putting the numbers 3, 2, and 1 on a stack and print it out. Which would be the correct way to enter the digits if you wanted to store single digits on a stack of ints and print out the value of 123? When you are convinced you can do that and understand what is going on, then you are ready for the next step.

The next step I would do is forget about writing code and write an algorhithm to convert decimal into binary using pencil and paper. Salem's advise about using the modulo and division operators should be all you need to do that.

If you store the result of each modulo as an item in a stack of ints and the print out the stack you should be impressed. Be sure you have all the steps written down before you try to write out the actual code though. It really will save you time in the long run.

[Lerner]

To convert a binary number to decimal is a little more complicated. If you are given the binary number as a string--like 10110 where the lower powers of 2 are on the right and the higher powers of 2 are on the left, then I would use a loop to convert each char in the string (from left to right) to an int by subracting the value of '0' from the current char, and pop the resulting int onto a stack of int. Then I would use a loop to pop each int off the stack one by one until it was empty. Each time I popped an int off the stack I would multiply it by one higher power of 2 and add that value to a running total of all prior numbers generated so far.

[Kellaw]

since i am using a loop to pop the binary digits one by one i think i will use the same loop to actually increase the power using predefined functions lets say

for(i=0 ; i<15 ; i++)
 {
  while (!StackIsEmpty())
   {
    if (stack.top=1)
     {
      total+=pow(2,i);
      stack.pop();
     }
   }
 }

To convert a binary number to decimal is a little more complicated. If you are given the binary number as a string--like 10110 where the lower powers of 2 are on the right and the higher powers of 2 are on the left, then I would use a loop to convert each char in the string (from left to right) to an int by subracting the value of '0' from the current char, and pop the resulting int onto a stack of int. Then I would use a loop to pop each int off the stack one by one until it was empty. Each time I popped an int off the stack I would multiply it by one higher power of 2 and add that value to a running total of all prior numbers generated so far.

[Kellaw]

i am thinking of lets say i input a binary of 1010
and in the stack the digits are pushed into single cells.i would then pop and push it into a temp stack because the earlier stack would be in reverse order.so the temp stack would be popped in order.or i could just reverse the way that i pop the single binary digits into the stack so the temp stack is not used.i just wonder how can i set it into single digits when the reverse would generate in a stack of 15 cells 101000000000000.thats my problem here
i already know how to separate 1010 into single digits.

x=1010;
stack.push((x/(power(10,i))%10);

[iamthwee]

You're definitely on the right track.

i already know how to separate 1010 into single digits.

Code:
x=1010;
stack.push((x/(power(10,i))%10);

Wouldn't it be easier to represent the binary number as characters, then you could just access each cell with a pointer.

and in the stack the digits are pushed into single cells.i would then pop and push it into a temp stack because the earlier stack would be in reverse order.so the temp stack would be popped in order

Why are you trying to correct the order of the stack. Ok so you know the stack stores your data backwards, but this is actually an advantage here, because binary numbers are normally worked out backwards - from right to left. Or did you already know this?

I don't consider this doing your work because I've just literally copy and pasted your original algorithm into my program with a few changes. This is what it should look like. :)

/**************************************************
 A program to convert binary to decimal
 using the stack.
 
 Algorithm implemented as proposed by Kellaw
 
 Released into the public domain on 09/03/06 
 All rights reserved
 *************************************************/
#include <iostream>
#include <stack> 
#include <cmath> //for the pow function

int main()
{
    std::stack <char> thwees_stack;//initialise a stack of chars
    char test[20] = "000000000001010"; //test case change here
    
    for(int i=0; i<15; i++)
    {
        thwees_stack.push(test[i]);//push 1's and 0's onto the stack
    }     
    
    double total = 0; //initialise total
   
      for(int i=0; i<15; i++)
      { 
        if (!thwees_stack.empty()) //test if stack is empty
        {
           if (thwees_stack.top()=='1')//chars are enclosed by single quotes
           {
              total += pow(2.0,i);
              thwees_stack.pop(); //discard from the stack
           }
           else if(thwees_stack.top()=='0')
           {
              thwees_stack.pop(); //discard from the stack 
           }
        }    
      }        
      
    std::cout<<total; //show final result
    std::cin.get();
    
}

Your next task will be to use YOUR stack prototype instead of the one provided in the STL. I have managed to correct a few typos but there is still an error there.

If you ask someone really nicely, they might be able to help you finish it.

const int MAX_STACK = 15 ;
typedef int stackItemType ;

class stackClass
{
    public:
    stackClass () ;
    bool StackIsEmpty () const;
    void Push ( stackItemType NewItem , bool& Success );
    void Pop ( stackItemType& StackTop , bool& Success );
    void GetStackTop ( stackItemType& StackTop , bool& success ) const;

    private:
    stackItemType items [ MAX_STACK ];
    int Top;
}

stackClass :: stackClass () : Top ( -1 )
{
    
}

bool stackClass :: StackIsEmpty () const
{ 
    return bool ( Top < 0 );
}

void stackClass :: Push ( stackItemType NewItem , bool& Success )
{ 
   Success = bool ( Top < MAX_STACK - 1 );

   if ( Success )
   {
     ++ Top;
     items [ Top ] = NewItem;
   }
}

void stackClass :: Pop ( stackItemType& StackTop , bool& Success )
{
   Success = bool ( ! StackIsEmpty () ) ;

   if (Success)
   {
    StackTop = items [Top];
     -- Top ;
   }
}

void stackClass :: GetStackTop ( stackItemType& StackTop , bool& Success )const
{
    Success = bool ( ! StackIsEmpty () ) ;

    if (Success)
    {
      StackTop = items [Top] ;
    }
}