Program 3 will be worth 100 points and will
be assigned points according to the following scheme:
Program
compiles 25
Points
Documentation
Header documentation (personal) 10
Points
Internal documentation (what your program
is doing) 10 Points
Style
Indentation 5
Points
White space 5
Points
Output
Correctly calculated 20
Points
Correct use of Functions 15
Points
Correctly printed output (on monitor) 10
Points
Total
100 Points
Assignment:
Part 1:
Write
a program to do the following:
Write a program to implement pattern
matching and sorting techniques. Give user a menu choice to either implement
pattern matching or sorting technique. Keep running this code until this user
decides to exit.
Pattern
Matching Part:
Accept some text from the user. Accept the
string that needs to be searched. Your program is supposed to print the number
of occurrences of the string found within the text, and the position at which
the pattern was found. Look at the following sample output:
Sample Output:
Enter
text: “Call me Ishmael. Some years ago - never mind
how long precisely - having little or no money in my purse, and nothing
particular to interest me on shore, I thought I would sail about a little and
see the watery part of the world. It is a way I have of driving off the spleen,
and regulating the circulation”
String to search – “Some years ago”
Number of occurrences – 1
Position Found – 18
Sorting Techniques/Methods:
Generate 10 random numbers from 1 - 100 and
sort those using the following sorting method. Each sorting method should be an
individual function:
Bubble Sort – Look at the
pseudo code explanation and pseudo code is in text book
Input Validation: Make sure only unique
random numbers are generated
Sample Output:
Initial
Set of numbers: 9 34 12 1 45 67 55 100 11 91
Bubble
Sort – 1 9 11 12 34 45 55 67 91 100
Part
2 (optional):
Create a new program. Copy the contents of
your PART A code. Modify the above
code to add another sorting technique to the program.
Selection Sort – Look at
the pseudo code explanation and pseudo code is in text book
Modify the menu choice, so when user
chooses sorting, you give them 2 more menu choices to choose from: Bubble Sort,
Selection Sort. Keep doing this user decided to exit. (If user chooses exit,
then exit back to the Main Menu choice)
Sample Output:
Initial
Set of numbers: 9 34 12 1 45 67 55 100 11 91
Bubble
Sort – 1 9 11 12 34 45 55 67 91 100
Initial
Set of numbers: 19 44 22 11 55 77 25 100 3 81
Selection
Sort – 3 11 19 22 25 44 55 77 81 100
Before
you start writing code, take some time to think about design of this program.
Decompose into a set of functions, and create a main() function that reads like
an outline for your solution to the problem. Make sure each function does one
task.
* * Be sure to print the header documentation as you
did in the fist programming assignment.
* *
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#include "sortalg.h"
//All the main menu options.
enum MAIN_MENU_OPTIONS {PATTERN_MATCHING, SORTING_TECHNIQUES, MAIN_MENU_EXIT, UNKNOWN};
//Search for occurences of searchText into text. Output in foundPositions the positions in the text where the searchtext is found.
//Returns number of occurences.
int seachForText(std::string text, std::string searchText, std::vector<int> &foundPositions)
{
int numberOfOccurences = 0;
std::size_t pos = text.find(searchText, 0);
while(pos != std::string::npos)
{
foundPositions.push_back(pos+1);
pos = text.find(searchText, pos+1);
numberOfOccurences++; //if text is found, increase by 1 the counter of texts found
}
return numberOfOccurences;
}
//Display a vector of numbers(integer) separated by space.
void displayVector(std::vector<int> vect)
{
std::vector<int>::const_iterator i;
for(i=vect.begin(); i!=vect.end(); ++i)
{
std::cout<<(*i)<<" ";
}
}
//Display search menu.
void GetSearchTextAndFullText(std::string &fullText, std::string &searchString)
{
//display to the screen to inform the user to enter some text
std::cout<<"Please enter some text:";
//read from the user the text into 'fullText' variable(some text).
std::getline (std::cin,fullText);
//display to the screen to inform the user to enter search text
std::cout<<"The string that needs to be searched:";
//read from the user the text to be searched into 'searchText' variable
std::getline (std::cin, searchString);
}
//display found positions
void displayFoundPositions(std::vector<int> foundPos)
{
std::cout<<"Position found - ";
displayVector(foundPos);
}
//display number of occurences
void displayNumberOfOccurences(int number)
{
std::cout<<"Number of occurences - "<<number<<std::endl;
}
//Menu for search - read input and search search, and output to the screen number of occurences and found positions
void patternMatchingMenu()
{
//search the input string into text
std::string fullText, searchText;
GetSearchTextAndFullText(fullText, searchText);//input by user full text and text to be seached
std::vector<int> foundPos;
int numberOfOccurences = seachForText(fullText, searchText, foundPos); //search the positions of searched text and full text and return number of occurences
//display number of occurences
displayNumberOfOccurences(numberOfOccurences);
displayFoundPositions(foundPos);
}
//Generate numbers = numberOfItems, values between minValue and maxValue.
//Returns the numbers generated in a vector.
std::vector<int> generateUniqueNumbers(int numberOfItems, int minValue, int maxValue)
{
std::vector<int> generatedValues;
for (int p = 0; p < numberOfItems; p++)
{
int num = minValue;
bool found = false;
do
{
found = false;
num = rand() % maxValue + minValue; //generate the number
std::vector<int>::const_iterator i;
for(i=generatedValues.begin(); i!=generatedValues.end(); ++i) //if the number is already in the list, generate another number (numbers are unique)
//the list items are compared with generated number
{
if ((*i) == num)
{
found = true;
}
}
}
while (found == true);
generatedValues.push_back(num); //if not already in list, add it
}
return generatedValues;
}
void displaySortingTechniquesMenu();
void displaySortingTechniquesMenuLoop();
//read the option selected from main menu
MAIN_MENU_OPTIONS readMainMenuOption()
{
//read line from keyboard
std::string read;
std::getline (std::cin,read);
if (read[0] == '1')
return PATTERN_MATCHING;
if (read[0] == '2')
return SORTING_TECHNIQUES;
if (read[0] == '3')
return MAIN_MENU_EXIT;
return UNKNOWN;//if none of these, uknown menu
}
//Display menu according to option selected in main menu
void mainMenuSelection(MAIN_MENU_OPTIONS option)
{
switch(option)
{
case PATTERN_MATCHING:
patternMatchingMenu();
break;
case SORTING_TECHNIQUES:
displaySortingTechniquesMenuLoop();
break;
case MAIN_MENU_EXIT:
break;
}
}
//displays the main menu texts
void displayMainMenu()
{
std::cout<<std::endl<<"Main Menu"<<std::endl;
std::cout<<"1.Pattern Matching"<<std::endl;
std::cout<<"2.Sorting techniques"<<std::endl;
std::cout<<"3.Exit"<<std::endl;
}
//Displays the main menu while '3'= Exit is selected
void displayMainMenuLoop()
{
MAIN_MENU_OPTIONS option = UNKNOWN;
do
{
//displays on screen the menu
displayMainMenu();
option = readMainMenuOption();
mainMenuSelection(option);
}
while(option != MAIN_MENU_EXIT); //exit the loop on selecting 3 option
}
//Display sorting techniques menu
void displaySortingTechniquesMenu()
{
std::cout<<std::endl<<"Please select an option."<<std::endl;
std::cout<<std::endl<<"1.Bubble sort"<<std::endl;
std::cout<<"2.Selection sort"<<std::endl;
std::cout<<"3.Exit"<<std::endl;
}
//Displays menu for selecting sort algorithm, select algorithm sort 1 = Bubble Sort, 2 = Selection Sort, 3 = Exit
void displaySortingTechniquesMenuLoop()
{
std::string read;
do
{
displaySortingTechniquesMenu();
//read from keyboard user input - menu selection
std::getline (std::cin,read);
if (read[0] == '1') //select bubble sort algorithm
{
std::vector<int> vectorUniqueNumbers = generateUniqueNumbers(10, 1, 100); //generate 10 numbers, from 1 to 100
cout<<"Initial set of numbers: "; //display text
displayVector(vectorUniqueNumbers); //display generated vector
bubble_sort(vectorUniqueNumbers); //sort the vector
std::cout<<std::endl<<"Bubble sort - "; //display text
displayVector(vectorUniqueNumbers); //display sorted vector
}
if (read[0] == '2')//select selection sort algorithm
{
std::vector<int> vectorUniqueNumbers = generateUniqueNumbers(10, 1, 100);//generate 10 numbers, from 1 to 100
cout<<"Initial set of numbers: "; //display text
displayVector(vectorUniqueNumbers); //display generated vector
selectionSort(vectorUniqueNumbers); // sort the vector
std::cout<<std::endl<<"Selection sort - ";//display text
displayVector(vectorUniqueNumbers); //display sorted vector
}
if (read[0] == '3') //select display main menu
{
}
}while(read[0] != '3'); //exit the loop on selecting 3 option
}
//main function - entry point
int main()
{
displayMainMenuLoop();
}
#include <iostream>
#include <string>
#include <vector>
//Bubble sort algorithm on a vector
void bubble_sort(std::vector<int>& a)
{
for (int i = a.size(); i > 0;i--)
{
for (int j = 0, k = 1; k < i;j++, k++)
{
if (a[j] > a[k])
{
int swap = a[j];
a[j] = a[k];
a[k] = swap;
}
}
}
}
//swap items on position i with item in position j in vector
void swap(std::vector<int> & data, int i, int j)
{
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
//selection sort algorithm on a vector
void selectionSort(std::vector<int> & data)
{
int length = data.size();
for (int i = 0; i < length; ++i)
{
int min = i;
for (int j = i+1; j < length; ++j)
{
if (data[j] < data[min])
{
min = j;
}
}
if (min != i)
{
swap(data, i, min);
}
}
}
