List Processing and String Analysis

The assignment consists of three tasks: (1) List processing, where programs are written to analyze a list of integer numbers entered by the user; (2) String processing, where programs are written to count and check if a string containing left and right brackets is math-like or not.

Coursework 1.
1 List processing
In this section you will be asked to write programs that ask from the user to enter a list of
integer numbers (let us give the list name A) and then analyse the list as specified in the
following three subsections.
In order to obtain the list A, the program first asks the user to enter the number of
elements of the list and then asks to enter these individual n elements in a loop lasting n
iterations (standard procedure of entering lists to be considered in the class of week 4).
Let me stress again that this way of obtaining lists applies to all the three tasks below.
Please feel free to assume that the input is entered correctly. No marks will be added for
correctness checking of the input and, accordingly, no marks will be reduced for not doing
such a check.
1.1 List containing the given set of elements (25 marks)
Write a program that prints ”YES” if A contains numbers 1,2,3 (all of them) in an arbitrary
order and ”NO” otherwise. For instance, the program should print ”YES” if A =
[10,2,4,15,3,6,1] and ”NO” if A = [1,17,2,45] (because number 3 is missing).
1.2 List containing the given set of elements in the given order (25 marks)
Write a program that prints ”YES” if A contains all the numbers 1,2,3 occurring in the order
they are listed (but not necessarily consecutive) and ”NO” otherwise. For instance the
program prints ”YES” if A = [45,1,5,2,77,3] and ”NO” if A = [45,1,3,77,2] (incorrect order).
Clearly, the program should also print ”NO” if one of 1,2,3 is missing in A.
The tricky part of this task are cases of multiple occurrences of 1,2,3. For instance the
program should print ”YES” if A = [3,2,1,2,3] because there are occurrences of 1,2,3
appearing in the correct order while ”NO” should be printed for A = [3,3,2,2,1,2] because
there are no such occurrences.
The marking scheme for this exercise is the following.
• The solutions working for all cases (including repeated occurrences) will receive full
mark (25 marks).
1
• The solution working only for cases without repeated occurrences of 1,2,3 will receive
15 marks provided that the ‘NO REPEATED OCCURRENCES’ statement is explicitly
provided as a comment to the program.
• The solutions working only for cases without repeated occurrences of 1,2,3 and not
warning the user about this in the comments will receive 5 marks.

1.3 Lists containing the given set of elements consecutively and in the given order
(25 marks)
Write a program that prints ”YES” if A contains all the numbers 1,2,3 occurring in the order
they are listed and consecutively and ”NO” otherwise. In other words, you need to check
whether there are indices i,i + 1,i + 2 such that A[i] = 1, A[i + 1] = 2, and A[i + 2] = 3.
2 String processing
In this exercise the program request from the user a string S consisting of left and right
brackets, for instance ‘(()))(()(’.
Please feel free to assume that the input is entered correctly. No marks will be added for
correctness checking of the input and, accordingly, no marks will be reduced for not doing
such a check.
2.1 Counting left and right brackets (18 marks)
Write a program that counts the number of left and the number of right brackets of the input
string. For example, the string ‘(()))(()’ contains four right brackets and four left brackets.
Hint: introduce two counters initialized to zero in the beginning. Then explore the symbols
of the string in a loop. For the current symbol increment the ‘left’ counter by 1 f the symbol
is ‘(’, otherwise, increment by 1 the ‘right’ counter.
2.2 Testing whether the string is math-like (7 marks)
Let us call a string math-like if the brackets occur like in a mathematical formula. For
instance, the strings ‘()’, ‘(())()’, ‘(()())’ are math-like, while the strings ‘))(())((’ and ‘())(()’
are not.
Write a program that prints ”YES” if the input string is math-like and ”NO” otherwise.
Hint: only a minor modification of the solution for Exercise 2.1. is required. In particular,
for each iteration of the loop, you need to check that the values of the ‘left’ and ‘right’
counters satisfy a particular condition. The non-triviality of the exercise is that you need to
find this condition. In order to do this, I recommend to consider several math-like strings of
small size and to observe the behaviour of the ‘left’ and ‘right’ counters as the string is
being explored from the left to the right.
2