INFOMAN брой 18
{
ФОРМАТИРАНЕ НА ТАБЛИЦИ
----------------------
Даден е текстов файл, който съдържа няколко таблици, описани на език, по-
добен на HTML. Всяка таблица започва със служебната дума <TABLE> и завършва
със служебната дума </TABLE>.Между тези две думи се слагат описанията на от-
делните редове на таблицата, изброени последователно отгоре надолу.За всеки
ред се дефинира по една двойка служебни думи <TR> ... </TR>, като между тях
се разполагат описанията на отделните клетки на реда. Броят клетки в първия
ред определя броя клетки във всички редове на таблицата - броя колони. Този
брой трябва да е число между 1 и 10.Ако някой ред има повече клетки от броя
колони, излишните се игнорират, а ако има по-малко от броя колони, липсващи-
те се считат за празни. Описанието на клетка е конструкция <TD> текст </TD>,
където между двете служебни думи <TD> и </TD> има някакъв текст,съставен от
букви и цифри или нищо, ако е празна клетката. Между всеки две думи, незави-
симо дали са служебни или са стойности на клетки, може да няма нищо или да
има произволен брой разделители.За разделители се считат символите интервал,
табулация и нов ред. Ето и една примерна таблица с 3 реда и 2 колони:
<TABLE>
<TR> <TD> 0123476789 </TD> <TD> 10 </TD> </TR>
<TR> <TD> row2col1 </TD> <TD> kletka22 </TD> </TR>
<TR> <TD> 202202.05pbppp </TD> <TD> row3col2 </TD> </TR>
</TABLE>
Задачата е по дадения входен файл с описанията на няколко таблици да се съз-
даде текстов файл, който съдържа форматирани таблиците. Една таблица е фор-
матирана, ако: Клетките са подредени в редове и колони, като в една колона
всички клетки са една под друга и имат еднаква ширина и във всеки ред всич-
ки клетки са с еднаква височина и са разположени една след друга.Всяка клет-
ка е оградена със символа '*'. Всеки ред съдържа еднакъв брой клетки и дъл-
жината му в символи заедно с разделителните символи '*' не надвишава 30. Съ-
държанието на всяка клетка се изписва отляво надясно и отгоре надолу, като
текста на всяка клетка трябва да се събира в определените за нея размери ка-
то може да се разполага на няколко реда и да се прекъсва на произволно мяс-
то. Програматa трябва да форматира така всяка зададена таблица, че тя да съ-
държа общо минимален брой редове и когато този минимум е достигнат дължина-
та на редовете да се минимизира.
РЕШЕНИЕ
-------
Алгоритъма в най-основни линии е следният:
Докато има още таблици във входния файл, изпълнявай:
(1) Прочети следващата таблица
(2) Намери оптималните широчини на колоните й и височини на редовете й
(3) Отпечатай форматирана таблицата в изходния файл
Край
Част (1) - прочитане на входния файл не е нищо сложно.Тя е реализиране чрез
няколко процедури - за прочитане на таблица, за прочитане на ред и за прочи-
тане на клетка, като всичките използват функция за четене на следващата ду-
ма от входния файл. Таблицата се съхранява в правоъгълна матрица,като всеки
елемент от нея съдържа една клетка. Всяка клетка е запис, който съдържа дъл-
жината в символи на съдържанието на клетка и това съдържание. Таблицата се
разполага динамично и се чете последователно по редове и по колони, като къ-
дето има излишни клетки, те се игнорират, а където не достигат, се допълват
с празни. Допуска се по-свободен синтаксис на описанието на таблицата. Про-
цедурата игнорира излишен текст, вмъкнат "не на място". Това позволява във
входния файл да слагаме коментари между редовете например. Служебните думи
се разпознават и с главни и с малки букви. Процедурата за вход не се влияе
от броя и вида на разделителите между думите. Ако един ред е празен (ако ня-
ма дефиниране клетки в него), той се попълва целия с празни клетки. За нача-
ло на дума се счита всеки символ, който не е разделител,а за край на дума -
всеки разделител и символа '>'. Програмата подържа думи в клетките дълги до
32KB.
Съществената част (2) от алгоритъма намира ширината на всяка колона и висо-
чината на всеки ред от таблицата. Ясно е,че всички Greedy алгоритми за тази
задача не гарантират оптимални резултати по простата причина,че задачата не
е матроид. Всички опити за прилагане на алгоритми, основаващи се на методът
динамично оптимиране също пропадат, защото за дадената задача не може да се
намери рекурентна функция, по която да се оптимира и за която да е изпълнен
принципа за оптималност на Белман. Както и да дефинираме целева функция, тя
не може да сведе до 1, 2 или 3 параметъра,за които да се направи табличка и
да се приложи алгоритъм за динамично оптимиране, защото оптималната ширина
на всяка следваща колона зависи не само от ширината на предходната, но и от
височината на всеки един от редовете в предната колона,поради което не може
да се направи таблица за динамично оптимиране. Ето защо най-подходящият ал-
горитъм в случая е оптимизираният Backtracking. Той дава добри резултати за
кратко време, понеже таблицата може да има най-много 10 колони и най-голяма
широчина 30, а броя на редовете указва несъществено значение. Ще генерираме
последователно всички възможни ширини за всяка на колоните и ще изчисляваме
сумарния брой редове, който би се получил в най-добрия случай. Ако той е по-
малък от оптималния за момента, ще продължаваме да търсим широчина за след-
ващата колона от таблицата. Когато се стигне до момент,в който сме намерили
широчина за всички колони, подобряваме текущото най-добро решение. Сумарния
брой редове се получава като за всеки ред от таблицата се смята максималния
му размер като максимум от размерите, получени във всяка от генерираните ко-
лони. Разбира се това не се изчислява всеки път, а се помни максималната ви-
сочина на всеки ред за всички генерирани до момента колони и се изчислява в
момента само за текущата колона. Разбира се, се взема предвид,че ако текуща-
та височина на таблицата е точно колкото оптималната, все пак по-добро реше-
ние може да се получи и то точно в случаите, когато текущата ширина на таб-
лицата не е достигнала текущата оптимална ширина при текущата най-добра ви-
сочина. Предвижда се естествено и че, преди и след всяка колона има по един
разделител '*'. За повече яснота може да се погледне сорса.
Част (3) от алгоритъма е лесна за реализация. След като имаме вече оптимал-
ните размери на всяка колона и всеки ред, можем само да вървим ред по ред и
колона по колона и да печатаме поредната част от текста в поредната клетка
като ако клетката е празна или текстът е свършил, да допълваме с интервали.
След всеки ред печатаме по един ред само с '*'. След всяка таблица оставяме
по един празен ред, за да се разграничават таблиците една от друга в изход-
ния файл.
Програмата работи правилно за време под 10 sec. за всеки тестов пример, кой-
то има не повече от 500 реда, независимо колко колони има. Най-тежки са слу-
чаите, в които някоя таблица има 7, 8 или 9 колони, защото тогава възможни-
те конфигурации за широчина на колоните са най-много.
Автор на алгоритъма и програмата
--------------------------------
Светлин Наков
гр. Велико Търново
tel. (062) 3-14-36
e-mail: nakov@hotmail.com
}
{$R-} {$S-} {$Q-}
CONST InFileName = 'tables.txt';
OutFileName = '';
MaxLines = 1000;
MaxCols = 10;
MaxTextLen = 32768;
TableSize = 30;
TYPE TKletka = record
Len: integer;
Text: array[1..MaxTextLen] of char;
end;
PKletka = ^TKletka;
THeights = array[1..MaxLines] of integer;
PHeights = ^THeights;
VAR F: Text;
T: array[1..MaxLines,1..MaxCols] of PKletka;
Rows,Cols: integer;
Width,BestWidth: array[1..MaxCols] of byte;
Height,BestHeight: THeights;
Procedure DisposeKletka(K:PKletka); {Free allocated for K memory}
Begin with K^ do Freemem(K,Len*SizeOf(char)+SizeOf(Len)); End;
Procedure ReadTable; {Read a table from current position of input file}
Var KletkaBuf: PKletka;
Function MyUpCase(const S: string): string;
Var Rez: string;
I: integer;
Begin
Rez:='';
for I:= 1 to length(S) do
Rez:= Rez + UpCase(S[I]);
MyUpCase:=Rez;
End;
Function GetWord: string; {Skip separators before the word at current}
Var Ch: char; {position in input file and return this word or ''. We}
S: string; { consider every word ends with '>', separator or EOF}
Begin
repeat
Read(F,Ch);
until (not (Ch in [#10,#13,' ',#9])) or EOF(F);
if EOF(F) then
begin GetWord:=''; Exit; end;
S:='';
repeat
S:= S + Ch;
Read(F,Ch);
until (Ch in [#10,#13,' ',#9,'>']) or EOF(F);
if Ch = '>' then GetWord:= S + Ch
else GetWord:=Ch;
End;
Procedure ProcessRow; {Process the text between <TR> and </TR> and fill T}
Function GetKletkaText: PKletka; {Return the text at current file pos.}
Var NewKletka: PKletka; {Allocate memory for it. It can be at most 32KB}
Ch: char;
Begin
Ch:=#10;
while (not EOF(F)) and (Ch in [#10,#13,' ',#9]) do
Read(F,Ch);
with KletkaBuf^ do
begin
Len:=0;
while (not EOF(F)) and (Ch in ['0'..'9','a'..'z','A'..'Z']) do
begin
Inc(Len); Text[Len]:=Ch;
Read(F,Ch);
end;
GetMem(NewKletka, Len*SizeOf(char)+SizeOf(Len) );
Move(KletkaBuf^,NewKletka^, Len*SizeOf(char)+SizeOf(Len) );
GetKletkaText:= NewKletka;
end;
End;
Function MaximalColumnCount: integer; {Return number of columns in T}
Begin
if Rows = 1 then MaximalColumnCount:= MaxCols
else MaximalColumnCount:= Cols;
End;
Var ColCount: integer;
KletkaText: PKletka;
S: string;
Begin
ColCount:=0; Inc(Rows);
repeat
S:=GetWord;
if Pos('TD',MyUpCase(S)) <> 0 then
begin { '<TD>' found. We must get kletka contents and save it in T }
KletkaText:= GetKletkaText;
if ColCount < MaximalColumnCount then
begin { We get kletka contents only if we need more kletki }
Inc(ColCount); if Rows = 1 then Inc(Cols);
T[Rows,ColCount]:= KletkaText;
end
else DisposeKletka(KletkaText);
GetWord; { skip '</TD>' after kletka's contents}
end;
if Pos('TR',MyUpCase(S)) <> 0 then
Exit; { '</TR>' found. Row completed. Exit }
until EOF(F);
End;
Procedure ProcessTableBody; {Process the text between <TABLE> and </TABLE>}
Var S: string;
Begin
repeat
S:=GetWord;
if Pos('TR',MyUpCase(S)) <> 0 then
ProcessRow; { '<TR>' found. }
if Pos('TABLE',MyUpCase(S)) <> 0 then
Exit; { '</TABLE>' found. Table sucessufully loaded from file. Exit }
until EOF(F);
End;
Begin
New(KletkaBuf);
Rows:=0; Cols:=0;
FillChar(T,SizeOf(T),0);
if Pos('TABLE',MyUpCase(GetWord)) <> 0 then { '<TABLE>' found }
ProcessTableBody;
Dispose(KletkaBuf);
End;
Procedure CalculateOptimalWidthAndHeight;
Var SumRows,MinRows: longint;
SumCols,MinCols: integer;
Procedure FindWidths(Col,Len:integer); {Calculate optimal Widths[1..Col]}
Var W: integer; {and Heights[1..Rows] and MinRows}
H: PHeights;
Function Max(a,b:integer): integer;
Begin if a>b then Max:=a else Max:=b; End;
Procedure CalculateHeights; {Using given width W of current column}
Var R: integer; {calculate Heights[1..Rows] and SumRows}
Begin
SumRows:=0;
for R:= 1 to Rows do
if T[R,Col] <> nil then
begin
Height[R]:= Max( Height[R],
(T[R,Col]^.Len+W-1) div W );
Inc(SumRows,Height[R]);
end;
End;
Begin
if (SumRows > MinRows) or
((SumRows = MinRows) and (SumCols>=MinCols)) then
Exit; {Exit if there isn't perspective to find better solution}
if Col = 0 then
begin {Better solution found. Update solution and Exit}
BestWidth:=Width; BestHeight:=Height;
MinRows:=SumRows; MinCols:=SumCols;
Exit;
end;
for W:= 1 to Len-Col+1 do
begin {Try all possible widths for column Col}
GetMem(H,Rows*SizeOf(integer));
Move(Height,H^,Rows*SizeOf(integer));
Width[Col]:=W; CalculateHeights;
Inc(SumCols,W);
FindWidths(Col-1,Len-W);
Dec(SumCols,W);
Move(H^,Height,Rows*SizeOf(integer));
FreeMem(H,Rows*SizeOf(integer));
end;
End;
Begin
SumCols:=0; MinRows:=MaxLongInt;
FillChar(Height,SizeOf(Height),0);
FindWidths(Cols,TableSize-Cols-1);
End;
Procedure PrintTable;
Var Row,TotalWidth: integer;
F: Text;
Procedure PrintLine;
Var I: integer;
Begin
for I:= 1 to TotalWidth+Cols+1 do
Write(F,'*');
WriteLn(F);
End;
Procedure PrintRow;
Var I,R,C: integer;
Begin
for R:= 1 to BestHeight[Row] do
begin {Write the row Row of the table at Heights[Row] sequential rows}
for C:= 1 to Cols do
begin {Write the next part of T[R,C]}
Write(F,'*');
with T[Row,C]^ do
for I:= (R-1)*BestWidth[C]+1 to R*BestWidth[C] do
if ((T[Row,C])=nil) or (I > Len) then Write(F,' ')
else Write(F, Text[I]);
end;
WriteLn(F,'*');
end;
End;
Begin
TotalWidth:=0;
for Cols:= 1 to Cols do
Inc(TotalWidth,BestWidth[Cols]);
for Rows:= 1 to Rows do
if BestHeight[Rows] = 0 then Inc(BestHeight[Rows]);
Assign(F,OutFileName); Append(F);
for Row:= 1 to Rows do
begin
PrintLine;
PrintRow;
end;
PrintLine;
WriteLn(F);
Close(F);
End;
Procedure FreeAllocatedMemory;
Begin
for Rows:= 1 to Rows do
for Cols:= 1 to Cols do
if T[Rows,Cols] <> nil then
DisposeKletka(T[Rows,Cols]);
End;
BEGIN
Assign(F,OutFileName); Rewrite(F); Close(F);
Assign(F,InFileName); Reset(F);
repeat
ReadTable;
CalculateOptimalWidthAndHeight;
PrintTable;
FreeAllocatedMemory;
until SeekEOF(F);
Close(F);
END.