Justificação de textos

Um espaço (=Whitespace character) é um caractere de codigo 9 (tabulaçao), 10 (quebra-de-linha), 13 (carriage return), ou 32 (espaço em branco). Uma palavra é uma sequência maximal de não-espaços. Neste exercício você deve escrever um programa em MACAL que lê um texto da entrada padrão e o escreve justificado na saída padrão. Seu programa deve receber um inteiro c > 0 como primeiro argumento da linha de comando e justificar o texto usando c colunas.

Os parágrafos do texto são separados por pelo menos uma linha em branco. Cada parágrafo deve ser quebrado em linhas da seguinte forma. Primeiro quebramos o parágrafo em palavras, depois colocamos na primeira linha o maior número possível de palavras de modo a não ultrapassar c colunas (se uma palavra tem comprimento maior do que c, então deve aparecer sozinha numa linha). Daí inserimos mais espacos em branco entre as palavras de modo que a linha ocupe exatamente c colunas, a não ser que a linha tenha apenas uma palavra. Em seguida, colocamos na segunda linha o maior número possível de palavras, e assim por diante. Entre palavras consecutivas da última linha de um parágrafo colocamos apenas um espaço. Vejamos mais precisamente como distribuir espaços entre as palavras de uma linha que não a ultima. Suponha que a linha seja composta das palavras w₁, ..., w_n, com n > 1.

Então

|w₁|+ · · · +|w_n|−|n|−1 ≤ c

sendo |x| o comprimento da palavra x. Escreva

N = c − |w₁|− · · · −|w_n|−n + 1

Entre duas palavras consecutivas devemos colocar 1 + ⌊N/(n − 1)⌋ espaços. Desta forma, sobram N × mod(n − 1)<n − 1 espaços a ser distribuídos; estes devem ser adicionados, um a um, entre palavras consecutivas da direita para a esquerda, ou seja, devemos adicionar um espaço a mais entre as palavras w_n e w_(n − 1), outro entre as palavras w_n − 1, e assim por diante até ter distribuído todos os espaços restantes. Considere por exemplo o texto abaixo, composto de cinco parágrafos:

38:1 Then the LORD answered Job out of the whirlwind, and
said, 38:2 Who is this that darkeneth counsel by words
without knowledge?  38:3 Gird up now thy loins like a man;
for I will demand of thee, and answer thou me.

38:4 Where wast thou when I laid the foundations of the
earth?  declare, if thou hast understanding.

38:5 Who hath laid the measures thereof, if thou knowest? or
who hath stretched the line upon it?  38:6 Whereupon are the
foundations thereof fastened? or who laid the corner stone
thereof; 38:7 When the morning stars sang together, and all
the sons of God shouted for joy?  38:8 Or who shut up the
sea with doors, when it brake forth, as if it had issued out
of the womb?  38:9 When I made the cloud the garment
thereof, and thick darkness a swaddlingband for it, 38:10
And brake up for it my decreed place, and set bars and
doors, 38:11 And said, Hitherto shalt thou come, but no
further: and here shall thy proud waves be stayed?  38:12
Hast thou commanded the morning since thy days; and caused
the dayspring to know his place; 38:13 That it might take
hold of the ends of the earth, that the wicked might be
shaken out of it?  38:14 It is turned as clay to the seal;
and they stand as a garment.

38:15 And from the wicked their light is withholden, and the
high arm shall be broken.

38:16 Hast thou entered into the springs of the sea? or hast
thou walked in the search of the depth?  38:17 Have the
gates of death been opened unto thee? or hast thou seen the
doors of the shadow of death?  38:18 Hast thou perceived the
breadth of the earth? declare if thou knowest it all.

Suponha que o texto acima esteja contido no arquivo ‘job.txt’. Se seu programa se chama ‘just.mac’, então a invocação

prompt > macsim just.mac 65 < job.txt

deve produzir o seguinte texto justificado como saída (com underscores em vez de espaços por clareza):

38:1\_Then\_the\_LORD\_answered\_Job\_out\_of\_the\_whirlwind,\_\_and\_\_said,
38:2\_\_Who\_\_is\_\_this\_\_that\_\_darkeneth\_\_counsel\_\_by\_\_words\_\_without
knowledge?\_38:3\_Gird\_up\_now\_thy\_loins\_like\_\_a\_\_man;\_\_for\_\_I\_\_will
demand\_of\_thee,\_and\_answer\_thou\_me.

38:4\_Where\_wast\_thou\_when\_I\_laid\_the\_foundations\_\_of\_\_the\_\_earth?
declare,\_if\_thou\_hast\_understanding.

38:5\_Who\_hath\_laid\_the\_measures\_thereof,\_if\_thou\_knowest?\_or\_\_who
hath\_\_stretched\_\_the\_\_line\_\_upon\_\_it?\_\_38:6\_\_Whereupon\_\_are\_\_\_the
foundations\_thereof\_\_fastened?\_\_or\_\_who\_\_laid\_\_the\_\_corner\_\_stone
thereof;\_38:7\_When\_the\_morning\_stars\_sang\_together,\_and\_\_all\_\_the
sons\_of\_God\_shouted\_for\_joy?\_38:8\_Or\_who\_shut\_\_up\_\_the\_\_sea\_\_with
doors,\_when\_it\_brake\_forth,\_as\_if\_it\_had\_issued\_out\_of\_the\_\_womb?
38:9\_When\_I\_\_made\_\_the\_\_cloud\_\_the\_\_garment\_\_thereof,\_\_and\_\_thick
darkness\_a\_swaddlingband\_for\_it,\_38:10\_And\_brake\_\_up\_\_for\_\_it\_\_my
decreed\_place,\_and\_set\_bars\_and\_doors,\_38:11\_And\_\_said,\_\_Hitherto
shalt\_thou\_come,\_but\_no\_further:\_and\_here\_shall\_thy\_\_proud\_\_waves
be\_stayed?\_38:12\_Hast\_thou\_commanded\_the\_morning\_since\_thy\_\_days;
and\_caused\_the\_dayspring\_to\_know\_his\_place;\_38:13\_That\_\_it\_\_might
take\_hold\_of\_the\_ends\_of\_the\_earth,\_\_that\_\_the\_\_wicked\_\_might\_\_be
shaken\_out\_of\_it?\_38:14\_It\_is\_turned\_as\_clay\_\_to\_\_the\_\_seal;\_\_and
they\_stand\_as\_a\_garment.

38:15\_And\_from\_the\_wicked\_their\_light\_is\_withholden,\_and\_the\_high
arm\_shall\_be\_broken.

38:16\_Hast\_thou\_entered\_into\_the\_springs\_of\_the\_sea?\_or\_hast\_thou
walked\_in\_the\_search\_of\_the\_depth?\_38:17\_Have\_the\_gates\_of\_\_death
been\_opened\_unto\_thee?\_or\_hast\_thou\_seen\_the\_doors\_of\_the\_\_shadow
of\_death?\_38:18\_Hast\_thou\_perceived\_the\_\_breadth\_\_of\_\_the\_\_earth?
declare\_if\_thou\_knowest\_it\_all.