logo Use SA10RAM to get 10%* Discount.
Order Now logo

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Alex WardComputer science
(5/5)

940 Answers

Hire Me
expert
Woodrow BinionAccounting
(5/5)

735 Answers

Hire Me
expert
Claire BattershillData mining
(4/5)

870 Answers

Hire Me
expert
Martin BlumbergFinance
(5/5)

693 Answers

Hire Me
C++ Programming

For this project you will implement a codeword generator. A codeword in this context is any permutation of characters from an alphabet. For this project, our alphabet is all uppercase letters { A, B, C, … ,Z}

INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS

CodewordGenerator 

For this project you will implement a codeword generator.

A codeword in this context is any permutation of characters from an alphabet. For this project, our alphabet is all uppercase letters { A, B, C, … ,Z}

Our generator will create only codewords that match a given pattern.

 Background - Regular Expressions:

A regular expression (or regex for short) is a special text string for describing a search pattern. You are probably familiar with  the  concept  of  wildcard  and  wildcard notations such as *.txt to find all text files in a file manager. This is a pattern: “all strings that end in .txt”.

With regular expressions you can specify complex patterns. For example “[a-z0-9._%

+-]+@[a-z0-9.- ]+\.[a-z]{2,4}” would match any email address. Lets break it down:

  • The square brackets indicate a character class, and match (can be substituted by) any of the characters between the brackets

  • [a-z0-9._%+-] matches any lowercase letter a-z or any digit 0-9 or period, underscore, percent, plus or minus So it would match any of the following: “a”, “a9b”, “-a9z1%azz54_”. But it would not match “a&b9"

  • + after a character class means “1 or more”, so [a-z0-9._%+-]+ means “any permutation of lowercase letters, digits and . _ % + _ of length 1 or more”

  • [a-z0-9._%+-]+@ matches the above followed by @

  • … and so on, so [a-z0-9._%+-]+@[a-z0-9.- ]+\.[a-z]{2,4} means

“any permutation of lowercase letters, digits and . _ % + _ of length 1 or more followed by @ followed by one or more lowercase letters and/or digits and/or dot and/or dash followed by a dot followed by two to four lowercase letters”

  • A * instead of a + after a character class means “0 or more of the characters in the character class”

 In C++ you can use the <regex> library to look for patterns in strings.

  • To create a regular expression object given a string patters such as the one described above

std::regex re(“[a-z]+aba[a-z]*");

  • To check if a string s matches the pattern

std::regex_match(s, re)

For example

std::string s = "caba"; std::regex_match(s, re) //true

will return true, while

std::string s = "aba"; std::regex_match(s, re) //false

will return false.

For this project this is enough knowledge of regular expressions, however I do encourage you to explore further, regex can be a very useful and powerful tool for future projects.

Implementation:

 You will implement a class named CodewordGenerator.

You may design this class as you wish, but it MUST have the following two public

methods:

  • std::string generateShortestWord(std::string pattern);

takes a string pattern and returns the shortest string that matches the pattern exploring the space of possible alphabet permutations in Breadth First Search order.

The input string pattern is guaranteed to represent a valid regular expression pattern.

  • std::string generateLengthWord(std::string pattern, int length); takes a string pattern and an integer n and returns a string of length n  that  matches the pattern exploring the space of possible alphabet permutations  in  Depth First Search

Here too, the input string pattern is guaranteed to represent a valid regular expression pattern.

We discussed BFS and DFS algorithms using queue and stack in the Queue ADT Lecture19 slides (you may refer to the lecture slides for pseudocode)

 Order of exploration of the permutation space is important for correctness!

If you return a string that matches the pattern but is not the one expected when exploring the space in BFS or DFS you will get partial credit.

The alphabet is all uppercase letters { A, B, C, … ,Z}

 You may add as many private functions and data members as necessary.

Testing:

Beware of the complexity of these algorithms when testing. BFS will not handle very long strings. DFS will do better, but still may require excessive computation with certain patters. Test with simple patterns but make sure to cover different possibilities.

Related Questions

. The fundamental operations of create, read, update, and delete (CRUD) in either Python or Java

CS 340 Milestone One Guidelines and Rubric  Overview: For this assignment, you will implement the fundamental operations of create, read, update,

. Develop a program to emulate a purchase transaction at a retail store. This  program will have two classes, a LineItem class and a Transaction class

Retail Transaction Programming Project  Project Requirements:  Develop a program to emulate a purchase transaction at a retail store. This

. The following program contains five errors. Identify the errors and fix them

7COM1028   Secure Systems Programming   Referral Coursework: Secure

. Accepts the following from a user: Item Name Item Quantity Item Price Allows the user to create a file to store the sales receipt contents

Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip

. The final project will encompass developing a web service using a software stack and implementing an industry-standard interface. Regardless of whether you choose to pursue application development goals as a pure developer or as a software engineer

CS 340 Final Project Guidelines and Rubric  Overview The final project will encompass developing a web service using a software stack and impleme

Get Free Quote!

326 Experts Online