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

[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 20:50

[volvo]

Во-первых, как ты думаешь, что будет в строке ST после окончания вот этого цикла:

while not eof(f) do
  read(f,ST);

?

А во-вторых: в файле *.IN (если он текстовый) последняя строка должна быть пустая, т.е. если после введенной тобой строки не был нажат Enter, то Паскаль будет делать проблемы...

Тегами, кстати, тоже пользуйся...

[Гость]

Во-первых, как ты думаешь, что будет в строке ST после окончания вот этого цикла:

while not eof(f) do
  read(f,ST);

?

А во-вторых: в файле *.IN (если он текстовый) последняя строка должна быть пустая, т.е. если после введенной тобой строки не был нажат Enter, то Паскаль будет делать проблемы...

Тегами, кстати, тоже пользуйся...

По окончанию цикла в строке будет содержимое файла, если нет то в чем ошибка????? ok можно изменить на writeln(f1,length(ST)) ???????

[Michael_Rybak]

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

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

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

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

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

[volvo]

По окончанию цикла в строке будет содержимое файла, если нет то в чем ошибка?

ВСЕГО файла? Ошибаешься... Последняя строка (группа символов, после последнего пробела/табуляции)... А если в файле будет БОЛЬШЕ одной строки?

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

Кстати, Metrax, у нас когда-то даже конкурс был на программу, проверяющую правильность расстановки скобок... Так что в Поиск (ссылка - у меня в подписи)...