Goal: Get familiar with the stack data structure. Through this programming exerc

Question

Goal: Get familiar with the stack data structure. Through this programming exercise, students can further understand and implement stack. Description of requirements: About Fibonacci numbers: In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the following integer sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, By definition, the first two numbers in the Fibonacci sequence are 1 and 1, and each subsequent number is the sum of the previous two. In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation: F Fn-1 Fn-2, with seed values 1, F In this programming exercise, you are required to realize a Fibonacci number generator. Assume the position number in the Fibonacci sequence starts from 1, and once the user enter a certain position number, the generator program should output the value of Fibonacci number at that position. For example, when user input 20, the program should be able to print out "The Fibonacci number at position 20 is 6765".

Explanation / Answer

#include <iostream>
#include <stack>
#include <string>
#include <algorithm>

using namespace std;

bool is_number(const std::string& s)
{
return !s.empty() && std::find_if(s.begin(),
s.end(), [](char c) { return !std::isdigit(c); }) == s.end();
}

int main(int argc, const char * argv[])
{
stack<int> s1, s2,s3, rs;
string input;
int num;
cout << "Enter number: ";
cin >> num;
// push 0 onto stack s1
s1.push(0);
  
input = "1";
       // push 1 onto stack s2
s2.push(1);
  
       //iterate till the given numver
for (int i = 2; i <= num; i++)
{
   int carry=0, op1=0, op2=0;
int op = 0;
       // while s1 or s2 is non empty pop and add numbers and push back onto stack rs(resultStack)
while (!s1.empty() && !s2.empty()) {
op1=0,op2=0;
if (s1.empty() && s2.empty()) break;
if (!s1.empty()) { op1 = s1.top(); s1.pop(); }
if (!s2.empty()) { op2 = s2.top(); s3.push(s2.top()); s2.pop(); }
int sum = 0;
sum = op1 + op2 + carry;
rs.push(sum%10);
op = sum%10;
if (sum >= 10) carry = 1; else carry = 0;
}
           //If carry is 1 then push that onto resultStack
if(carry){
rs.push(1);
}

// if both the numbers are not of same lenth the push 0's on to the other stack
if(rs.size()>s3.size()){
int n = rs.size() - s3.size();
while(n>0)
{
s3.push(0);
n--;
}
}

if(s3.size()>rs.size()){
int n = s3.size() - rs.size();
while(n>0)
{
s2.push(0);
n--;
}
}
             
           // copy resultStack values onto s2 because in fibonacci c = a+b and a = b and b =c
if(i < num){
while (!rs.empty()) {
// cout << rs.top();
              
input = rs.top();
// s2.push(rs.top());
for (auto &c : input) {
    s2.push(c);
}
rs.pop();
               }
}
  
           // copy s2 onto s1 i.e a = b here we use s3 as temporary stack to store s2
while (!s3.empty()) {
s1.push(s3.top());
s3.pop();
}

}
      
       cout << " Result is: ";
       while (!rs.empty()) {
cout << rs.top();
rs.pop();
}

cout <<" ";return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.