Quiz 7

Problem Statement:

Today, Raphael was asked by his coworker (a math teacher) to help him write a program that converts an integer from decimal to binary. This (kinda annoying) guy recently learned about the usefulness of stacks, and wants Raphael to write a program that does this using stacks. He will not accept any algorithm that doesn't use stacks.

As an illustrative example of the algorithm that Raphael was asked to implement, say you want to convert 14 into binary. Then you do the following:

1. 14/2 = 7, remainder is 0.
2. 7/2 = 3, remainder is 1.
3. 3/2 = 1, remainder is 1.
4. 1/2 = 0, remainder is 1.
Then the binary value of 14 is 1110.

Using stacks, write a program for Raphael that takes as input a positive integer n (in decimal), and outputs a string of 0's and 1's which represents n in binary.

Solution

You're asked here to implement a basic stack algorithm. The algorithm description is already clear in the problem statement, we just need to sit down and write the code that actually does it!

#include <iostream>
#include <stack>

string decimal2Binary(int n)
{
	string s;
	stack<int> A;
	while(n>0)  // Populate the stack A with the successive remainders.
	{
		A.push(n%2);
		n /= 2;
	}
	while(!A.empty())  // Pop out of the stack and append to string s successively.
	{
		s += to_string(A.top());
		A.pop();
	}
	if(s.empty())  // If n was 0, then we never appended anything to s, but the binary rep of 0 is "0".
		s = "0";
	return s;
}

int main()
{
	int n;
	std::cout<<"Enter the number in decimal: ";
	std::cin>>n;
	std::cout<<"The number in binary is: "<<decimal2Binary(n)<<endl;
	return 0;
}