Количество скобок Опции

[Metrax]

И так , условие: в файле iekavas.in хранится последовательность скобок, например )()())( записать в файл iekavas.out сколько скобок лишних (например 3(смотрите выше)) мой код:

program iekavas;
var
 i,j:integer;
 f,f1:text;
 ST:string;
begin
assign(f,'iekavas.in');
assign(f1,'iekavas.out');
reset(f);
while not eof(f) do
 read(f,ST);
i:=1;
while i<>length(ST) do
 if (ST[i]='(') and (ST[i+1]=')') then
    begin
     delete(ST,i,2);
     dec(i);
    end
 else inc(i);
rewrite(f1);
write(f1,length(ST));
close(f1);
end.

ето самое последнее мое решение, вродь лучше и ниможет быть, почему непроходит по времени????? напишите свои решегия... заранее благодарен

Сообщение отредактировано: volvo - 2.11.2006 16:50

[Michael_Rybak]

ето самое последнее мое решение, вродь лучше и ниможет быть, почему непроходит по времени????? напишите свои решегия... заранее благодарен

Твое решение имеет квадратичную сложность. Ты все делаешь одним линейным циклом, но процедура delete работает тоже за линейное время; меняя строку (потенциально на каждой итерации), ты замедляешься до квадрата.

На самом деле тебе строку менять не надо. Суть твоего алгоритма: идем слева направо, как только нашли "()" - удаляем из строки, откатываем на 1 позицию влево, и продолжаем поиск.

То же самое можно сделать несколько по-другому. Идем слева направо. Храним счетчик количества открытых скобок, и счетчик "лишних" скобок. В начале оба равны 0. Встретив открытую скобку, увеличиваем счетчик открытых. Встретив закрытую, проверяем счетчик открытых. Если он больше нуля, уменьшаем его на 1 (нашли "()"). Если же он равен нулю, это значит, что встреченная закрывающая скобка - лишняя. Увеличиваем счетчик "лишних". Дойдя до конца строки, добавляем значение счетчика открытых скобок к счетчику "лишних" (потому что эти открытые так и не закрылись).

Т.е. я не менял идеи твоего алгоритма, но перешел от изменения строки к запоминанию промежуточных результатов. Пробуй, должно пройти.