Олимпиадная информатика - 2010

Задача «Вирус»

В файле INPUT.TXT задано арифметическое выражение состоящее из цифр, букв, скобок и знаков арифметических операций. Но вирус удалил из данного файла некоторые скобки, стоящие в начале и в конце выражения. Написать программу, выводящую в файл OUTPUT.TXT исправленное выражение. Максимальная длинна исходной строки не более 100 символов.

INPUT.TXT

(3+(2*6))*3-(((5/4-3)*9-(7-4)

OUTPUT.TXT

((3+(2* 6)) * 3 -(((5/4-3 )* 9-(7-4)));

program zz;
var i,n:integer;c: string;
begin
assign(input,'input.txt');reset(input);
assign(output,'output.txt');rewrite(output);
read(c); {Ввод строки }
n:=0; {Обнуление счетчика}
for i:=1 to length(c) do {Посимвольный просмотр строки}
begin
if c[i]='('then n:=n+1 else {Найдена "(" счетчик увеличиваем}
if c[i]=')' then n:=n-1; {Найдена ")" счетчик уменьшаем}
if n then {счетчик принял отрицательное значение}
begin
write('('); {вывод "("}
n:=0; {Обнуление счетчика}
end;
end;
write(c); {вывод данной строки}
for i:=1 to n do
write(')'); {вывод недостающих ")"}
close(input);
close(output);
end.



close
 

Разбор задачи №1 "Вирус"

Задача на применение стека. Введём счетчик. Посимвольно проверяем строку. Если очередной символ "(", увеличиваем счётчик на единицу, если ")" - уменьшаем на единицу.

Остальные символы игнорируем.Если в какой-то момент счётчик принял отрицательное значение, то это значит, что закрытых скобок больше, чем открытых, т.е. в начале строки нужно добавить "(". Выводим этот символ в выходной файл и обнуляем счётчик. Когда строка просмотрена полностью, выводим её в файл вывода.

Осталось определить нет ли лишних открытых скобок. Это возможно в том случае, если счётчик в конце просмотра имеет положительное значение. Открываем цикл от 1 до значения счетчика и выводим в этом цикле символ ")".