CS13002 Programming and Data Structures
Section: 4/D, Spring 2005
This exercise is based on string manipulation and handling of two-dimensional arrays. You are given a text file. Your problem is to adjust the spaces in each line in such a way that the resulting text is justified (both at the left and at the right). Here is our proposal of an algorithm that you should use in order to solve the problem.
- First read the input file and store the lines in a two-dimensional character array with each line stored in a single row of the array.
- The text is divided into paragraphs. Two consecutive paragraphs are separated by a blank line.
- The last line in a paragraph is not to be justified. Also a blank line is not to be justified.
- Finally suppose that you have a non-blank line which is not the last line of a paragraph. If the length of this line is already larger than the target width, then do not perform any processing of this line. Otherwise, increase the sizes of the inter-word gaps so that the resulting line has a width equal to the target width.
Assume that len denotes the initial length of the line and that the line initially contains nsp number of inter-word spaces. You have to add a total ofextra = target_width - len
number of additional spaces in the line. In order that the insertion leads to (aesthetically) good-looking paragraphs, it is necessary to distribute the extra new spaces more or less uniformly among the nsp inter-word gaps. Letq = extra / nsp (integer division).
First insert q additional spaces in each of the nsp gaps. If extra is not an integral multiple of nsp, this still leaves us withr = extra - q * nsp
spaces to be inserted. If the line has an odd number in the current paragraph, add another single space in each of the first r gaps. On the other hand, if the line has an even number in the current paragraph, add a single space in each of the last r gaps.
Here is an example. Consider the following line:Deciding the truth of a statement in a formal system was called the
which has a length of 67. Assume that the target width is 75. You have to add 8 extra spaces to the line. The line contains 12 inter-word gaps. If the line has an odd number in the paragraph, then the leftmost 8 inter-word gaps should be increased from one space to two spaces, else the rightmost 8 gaps need be so increased. In the former case, the line would look likeDeciding the truth of a statement in a formal system was called the
and in the latter case it would look likeDeciding the truth of a statement in a formal system was called the
If we started with a smaller line likeDeciding the truth of a statement in a formal system was called
that needs 75-63=12 spaces to be added among 11 gaps, the line after justification would look likeDeciding the truth of a statement in a formal system was called
orDeciding the truth of a statement in a formal system was calleddepending on its position in the paragraph.
- Replace each row of your two-dimensional array by its justified version using the above rules.
- Print the resulting justified text line-by-line.
- Take the target width to be 75. There is a total of 230 lines in this file and each line has a width no bigger than 75.
The following should be the output of your program for the fourth paragraph of the input file.The design of the first commercially available mechanical calculator is attributed to Leibnitz (1671) (the same bloke who invented calculus). It was completed in 1694 and Leibnitz demonstrated, for the first time, that binary arithmetic was superior to decimal arithmetic as it simplifies machine construction. Leibnitz's machine could add, subtract, multiply, divide and even find square root. Leibnitz's machine was a full adder (you'll learn about a full adder in your Digital Hardware Design course), in which the carry was saved in the form of the position of a lever. A working model of this machine was exhibited at the Royal Society of London in 1794, but it was somewhat unreliable. It was commercially available in 1820.