Question

----------------

Overview:

----------------

• This lab will consist of several independent exercises that must all use recursion to solve various problems.
• Some problems will have fairly short solutions, but declaring and using classes/objects is still required.
• Some could benefit from having some kind of data structure being passed between calls. Feel free to use your LinkedList if you think it could help.
• Some solutions will be a mix of iteration and recursion, but all solution need to be recursive in some form.

----------------

Exercise 1: Recursive Parenthesis Checker

----------------

Create a program that takes a sequence of parenthesis from the command line. Your program will indicate whether or not it's a balanced set of parenthesis (matching left and right, not just an equal number).

----------------

Output:

----------------

$>./prog "(())"
The sequence (()) is balanced

$>./prog "))(("
The sequence ))(( is not balanced

$>./prog "((((((()))))))"
The sequence ((((((())))))) is balanced

$>./prog "(()()()()()()()()()())"
The sequence (()()()()()()()()()()) is balanced

----------------

Exercise 2: String Permutations

----------------

Create a program that takes a string from the command line and prints every permutation of that string. You may assume the string will contain all unique characters. You may print the permutations in any order, as long as you print them all.

----------------

Output:

----------------

$>./prog dog
d
do
dog
dg
dgo
o
od
odg
og
ogd
g
gd
gdo
go
god

----------------

Exercise 3: Good Old Fibonacci

----------------

The Fibonacci sequence is a famous numerical series in which every number (after the first two) is the sum of the previous two numbers added together. The sequence is defined as...

F₀=0

F₁=1

F_i=F_i-1 + F_i-2

For your reference, here are the first few numbers in the Fibonacci sequence:

0,1,1,2,3,5,8,13,21,34,55,89

Create a program that takes an integer and a flag from the user. The flag will indicate one of two options:

• -i
  • Short for "ith" where the user wants to know the ith Fibonacci number (note the lowest valid would be zero)
• -v
  • Short for "verify" where the user wants to know if the number given is in the Fibonacci sequence

----------------

Output:

----------------

$>./prog -i 2
1
$>./prog -i 8
21
$>./prog -i 36
14930352
$>./prog -v 7
7 is not in the sequence
$>./prog -v 75025
75025 is in the sequence

----------------

I need help on these 3 exercises that require recursion only. I need main.cpp, makefile, Executive.cpp, and Executive.h files for each exercise, and I can't figure out the code for these recursive exercises. So, will someone help me on this lab? If so, then that will be awesome.

Answer 1

Summary: The Exerscise 1 is considered as a primary question and completed as per the requirement. Kindly post Exerscise 2 and 3 seperately to get solution.

The program written in c here below will check if the input string with braces is balanced or not. The .h header files are created with the definitions of the classes and the implementation is in.cpp file. There is a main program which act as a driver. The make file is used to compile the program and create the executable.

Excersice 1:

File : executive.h

#ifndef BRACE_H
#define BRACE_H
/*This class is for checking the brace balancing*/
class BracesChecker
{
private:
    char* ptr; // pointer to store the string pointer
public:
    BracesChecker(char* argv);
        bool paranthesisChecker(char* argv, int count);
    void printResult();
};
#endif

File : executive.cpp

#include <iostream>
#include "executive.h"
using namespace std;

BracesChecker::BracesChecker(char* argv){
        ptr = argv;
}
// This method is recursively called to check the balancing of string
bool BracesChecker::paranthesisChecker(char* argv, int count)
{
    if (count < 0)
        return false; // If the count comes negative then the balancing is failed
    if(argv[0]=='\0') // checking whether we reached end of string.
    {
        if (count==0)
        {
            return true; // when count is zero we have balanced the braces
        }
        else
        {
            return false;
        }
    }
    if(argv[0] == '(')
      {
          count = count + 1;
          return paranthesisChecker(argv +1, count); // call recursively with next character
      }
      else if(argv[0] == ')')
      {
          count = count - 1;
          return paranthesisChecker(argv +1, count); // call recursively with next character
      }
     return false;
        }
void BracesChecker::printResult(){
        char* tmp = ptr;
        if(paranthesisChecker(tmp, 0))
                cout<<"The sequence "<<ptr<<" is balanced.\n";
        else
                cout<<"The sequence "<<ptr<<" is not balanced.\n";
}

File : main.cpp

#include <iostream>
using namespace std;
#include "executive.h"
int main(int argc, char** argv) 
{ 
    // Create a BraceChecker object and print the result
    BracesChecker bracesChecker(argv[1]);
    bracesChecker.printResult();
    return 0; 
} 

File Makefile

g++ -c main.cpp
g++ -c executive.cpp
g++ -o main main.o executive.o

Output