UC Davis, Winter 2018
1 Changelog
2 General information
3 Programming exercises
1 Changelog
v1: First publication
2 General information
Due before 11:59 PM, Friday March 9th, 2018
You are to work with a partner for this homework
The reference work environment is the CSIF
3 Programming exercises
3.1 Problems
Working executables for all the following problems are available on my CSIF account, in directory/home/jporquet/ecs30/hw5.
All the following problems are meant to exercise your problem solving skills. It is highly recommended to start writing the functions in the suggested order. If you know what the functions are expected to receive and are expected to return, you can usually write them independently from the rest. Once you have all of the functions, it is easier to write the main function and assemble the whole program.
3.1.1 Redact
The legal department of a big company is looking for a way to redact certain sensitive documents before they can be released publicly. A redacted document has certain words deleted or blacked out.
For this problem, censored words will be hidden with asterisks, leaving only their first letter intact. Censored words should be matched regardless of their case.
Write programredact.cthat reads entire lines from the user, and hides certain words according to a list of words received as program arguments, as illustrated in the following example.
$ cat udhr_art26.txt(1) Everyone has the right to education. Education shall befree, at least in the elementary and fundamental stages.Elementary education shall be compulsory. Technical andprofessional education shall be made generally available andhigher education shall be equally accessible to all on thebasis of merit.(2) Education shall be directed to the full development ofthe human personality and to the strengthening of respectfor human rights and fundamental freedoms. It shall promoteunderstanding, tolerance and friendship among all nations,racial or religious groups, and shall further the activitiesof the United Nations for the maintenance of peace.(3) Parents have a prior right to choose the kind ofeducation that shall be given to their children.$ ./redact education right t < udhr_art26.txt(1) Everyone has the r**** to e********. E******** shall befree, at least in the elementary and fundamental stages.Elementary e******** shall be compulsory. Technical andprofessional e******** shall be made generally available andhigher e******** shall be equally accessible to all on thebasis of merit.(2) E******** shall be directed to the full development ofthe human personality and to the strengthening of respectfor human r****s and fundamental freedoms. It shall promoteunderstanding, tolerance and friendship among all nations,racial or religious groups, and shall further the activitiesof the United Nations for the maintenance of peace.(3) Parents have a prior r**** to choose the kind ofe******** that shall be given to their children.$
Here are a list of requirements, assumptions and hints:
This program shall contain no global variables.
We assume that the maximum number of characters a line can contain is 80.
Censored words less than 2 characters should be ignored.
You will probably need to split the problem into a hierarchy of functions. A possible set of functions could include:
A function that hides a certain number of characters in a line, starting from a given position.
A function that hides a certain word in a line (e.g. by iterating through the string and locating the word).
A function that hides a collection of words in a line.
The main function should be the brain, reading the line from the user and calling the censor function before displaying the censored line.
In order to match strings while ignoring their case, you can usestrncasecmp()function provided by the libc.
List of some important libc functions that are used in the reference program:strlen(),strncasecmp(),fgets().
3.1.2 Spanish verb conjugator
Two years ago, right before arriving in Davis, I traveled for a couple of months in South-American and learned some Spanish there. Now, without much practice, I am slowly losing my Spanish skills and might need some help remembering.
I basically would like to start a program that shows the verb conjugations, first starting with the easiest group of verbs: the verbs ending in -ar.
For amar, which means to love in its infinitive form, is conjugated as follows:
Yo amo (I love)
Tu amas (You love)
Usted ama (He/She loves)
Nosotros amamos (We love)
Ustedes aman (They love)
As you can observe, the suffix -ar is first removed from the infinitive form and then a specific ending is added to the verb’s root according to the given pronoun.
Write programconjugador.cthat receives an -ar Spanish verb from the user and conjugates it accordingly, as illustrated in the following example.
$ ./conjugadorEnter a spanish verb (-ar):amaryo amotu amasusted amanosotros amamosustedes amanConjugate another verb? [Yy]yEnter a spanish verb (-ar):hablaryo hablotu hablasusted hablanosotros hablamosustedes hablanConjugate another verb? [Yy]q$ ./conjugadorEnter a spanish verb (-ar):saberNot a correct -ar verbConjugate another verb? [Yy]n$
Here are a list of requirements, assumptions and hints:
This program shall contain no global variables.
We assume that the maximum number of characters a verb (in its infinitive form or conjugated form) can contain is 30.
You will probably need to split the problem into a hierarchy of functions. A possible set of functions could include:
For this function, it might be a good idea to have the pronouns and endings in arrays of strings.
A function that conjugates a verb.
A function that test if the verb ends in -ar.
The main function should be the brain, reading the verb from the user and calling the conjugation function if the verb is valid, before asking if another verb should be inputted.
Since the user is only requested to enter a verb, you can safely usescanf()to read the verb (instead of usingfgets()which would be more difficult to handle as it keeps the newline character as part of the input buffer).
List of some important libc functions that are used in the reference program:strlen(),strncpy(),strcat(),scanf().
3.1.3 Line editor
One of the first parts of the Unix operating system, developed in August 1969, waseda line editor. Some have described it as “the most user-hostile editor ever created” asedis really difficult to use!
Here, we would like to develop a very simple line editor that only acts on one initial line of text. The user can then either delete a substring from that line, or insert a string into it.
Write programline_editor.cthat implements a line editor supporting deletion and insertion, as illustrated in the following example:
$ ./line_editorEnter the source string:Hello worldSource string is: 'Hello world'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):iEnter string to insert: of wonders!Enter position to insert:11Source string is: 'Hello world of wonders!'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):dEnter string to delete:HelloSource string is: ' world of wonders!'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):iEnter string to insert:DearEnter position to insert:0Source string is: 'Dear world of wonders!'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):eInvalid commandSource string is: 'Dear world of wonders!'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):dEnter string to delete:totoError, 'toto' not foundSource string is: 'Dear world of wonders!'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):12Invalid commandSource string is: 'Dear world of wonders!'Enter [Dd] (delete), [Ii] (insert) or [Qq] (quit):qFinal string: 'Dear world of wonders!'$
Here are a list of requirements, assumptions and hints:
This program shall contain no global variables.
We assume that the maximum number of characters a line can contain is 80.
You will probably need to split the problem into a hierarchy of many functions. A possible set of functions could include (but is not limited to):
Or return an error in case the substring could not be located;
If you usescanf()for this function, don’t forget to empty the input buffer afterwards.
Whenscanf()reads a character or a number, it leaves the newline character in the input buffer. If the program was to callfgets()right afterwards,fgets()would return immediately an empty string only containing the newline.
In order to prevent that, we need a function that discards all the characters left in the input buffer up until a newline character is found.
For this function, you probably need to use the functiongetchar()which returns the next character in the input buffer.
Callgetchar()in a loop until the character is a newline.
Whenfgets()reads from the user, it also takes in the newline and for this problem the newline has to be removed.
Hint: removing characters at the end of a string is easy if you just move the end-of-line character where you need it to be!
Such function should only trim the newline character if there is one in the first place.
A function that trims the newline out of a string.
A function that empties the input buffer.
A function that prompts the user for a command and returns it.
A function that can locate a substring in a string and return its position.
A function that can delete a portion of a string, given a starting position and a number of characters to remove.
A function that can insert a substring in a string at a given position.
The main function should be the brain, first getting the initial string, then getting commands from the user performing them, using sub-functions, until the user wishes to quit.
List of some important libc functions that are used in the reference program:strlen(),getchar(),strncmp(),strcpy(),fgets(),strcat(),scanf().
3.1.4 Common string suffix
A famous editor of English dictionaries are in the process of digitalizing their dictionary collection. Their goal is run some language processing algorithms in order to help academics researching the English language.
One particular algorithm they would like to run is finding the number of words that share the same suffix. As a start, they would like to determine the longest suffix two words share.
Write programsuffix.cthat displays the longest suffix two words share, as illustrated in the following example:
$ ./suffixprocrastination destinationCommon suffix between 'procrastination' and 'destination' is 'stination'$ ./suffixgloballyinternallyCommon suffix between 'globally' and 'internally' is 'ally'$ ./suffixgloves doveCommon suffix between 'gloves' and 'dove' is ''$
Here are a list of requirements, assumptions and hints:
This program shall contain no global variables.
We assume that the maximum number of characters a word can contain is 30.
While the two strings that are being filled out by the user are local arrays in the main function, any additional strings created during the execution should be dynamically allocated in the heap.
Do not forget that dynamically allocated memory should be freed appropriately.
You must implement functionchar *find_suffix(char *s1, char *s2)that returns a dynamically allocated string containing the longest suffix shared by stringss1ands2.
Hint: you should start iterating from the end of the words.
Hint:forloops allows multiple initializations and updates within their construct, if they are separated with commas.
For example, you can iterate on both someiandjvariables until one of them (or both) fails a condition:
for (i = 0, j = 0; i < len1 && j < len2; i++, j++) { ...}
You should probably a similar construct for iterating through the two strings at the same time.
The main function should get the user input, then run the suffix function, and finally display the suffix.
List of some important libc functions that are used in the reference program:strlen(),malloc(),free(),scanf().
3.1.5 Word reverse
The common writing form of some languages, such as Arabic or Hebrew, is right to left (abbreviated RTL). It means that RTL writing starts from the right of the page and continues to the left.
As an experiment, we would like to convert English from LTR to RTL. But to make it not to complicated, instead of reversing all the letters, we would like to only reserve the words of a line.
There are multiple ways of reversing a string but here you have to follow a specific algorithm. First, you have to count the number of words in the string; we assume that words are separate by one space and that no other punctuation exists. Then you have to create a array of strings, each item being one of the words. The last item is NULL to mark the end of the array. If item are ordered from the last word to the first word, recomposing the reserved string only consists in concatenating these words in sequence.
Word reverse
Write programword_reverse.cthat reverse all the words of a line, as illustrated in the following example:
$ echo "Let There Be Light" | ./word_reverseInput: Let There Be LightOutput: Light Be There Let$
Here are a list of requirements, assumptions and hints:
This program shall contain no global variables.
We assume that the maximum number of characters a line can contain is 80.
While the input string that is being filled out by the user is a local array in the main function, any additional strings created during the execution should be dynamically allocated in the heap.
Do not forget that dynamically allocated memory should be freed appropriately.
You must implement functionchar **tokenize_words(char *line)that returns a dynamically allocated array of strings containing all the words in reverse order.
Hint: you should start iterating from the end of the array when filling it out.
The last item of the array should be initialized to NULL so that you can recognize the end of the array when iterating.
You will probably need to split a few helper functions for this problem. A possible set of functions could include (but is not limited to):
A function that counts the number of words in the line. Words are separated by spaces and the line probably ends with a newline character (look into the functions fromctype.h).
You will need this function to allocate the first dimension of your array of strings.
A function that counts the number of character in a word.
You will need this function to allocate each string in your array of strings.
A function that skips leading spaces from a certain string and returns a pointer to the first non-space character.
When scanning the input string and split it into separate words, you will need this function to go to the next word.
The main function should get and echo the user input, then get the reversed string as per described by the project and display it.
List of some important libc functions that are used in the reference program:malloc(),free(),strncpy(),strcat(),fgets().
3.1.6 Complex numbers
A high-school in Davis wants to have a program for their students that can do basic operations on complex numbers.
A complex number is expressed by the form , where and are real values and is the imaginary number (). The common operations between complex numbers are:
Addition:
Subtraction:
Multiplication:
Division:
Write programcomplex.cthat reads an operation between two complex numbers and print the resulting complex number, as illustrated in the following example:
$ ./complex(3.5+5.2i)+(2.5-1.2i)=(6.00+4.00i)(3.5-5.2i)-(2.5+1.2i)=(1.00-6.40i)(3.5+5.2i)*(2.5-1.2i)=(14.99+8.80i)(3.5+5.2i)^(2.5-1.2i)Operation '^' invalid(3.5+5.2i)/(2.5-1.2i)=(0.33+2.24i)totoInvalid input$
Here are a list of requirements, assumptions and hints:
This program shall contain no global variables.
You should define a structure to represent complex numbers:struct complex_s.
You must implement the following functions:
int scan_complex_op(struct complex_s *c1, struct complex_s *c2, char *operator)
This function gets the operation from the user and fill out the output parameters accordingly. In case of an invalid input, it should display an error message and loop.
It should return 0 if the program has receivedEOF(i.e. no more operations to process), or 1 if an operation is being returned in the output parameters.
void print_complex(struct complex_s c)
Prints a complex number.
struct complex_s add_complex(struct complex_s c1, struct complex_s c2)
Returns a complex number resulting from addingc1andc2.
struct complex_s sub_complex(struct complex_s c1, struct complex_s c2)
Returns a complex number resulting from subtractingc2fromc1.
struct complex_s mult_complex(struct complex_s c1, struct complex_s c2)
Returns a complex number resulting from multiplyingc1withc2.
struct complex_s div_complex(struct complex_s c1, struct complex_s c2)
Returns a complex number resulting from dividingc1byc2.
The main function should be the brain and contain the processing loop: first getting the requested operation, then performing it by calling the appropriate function and printing the result.
以上发布均为题目，为保证客户隐私，源代码绝不外泄！！）
