Задача 7: Скобки.
Проверить корректность расстановки скобок в арифметическом
выражении.
Выражение задается из файла "input.txt" и может содержать
произвольное количество круглых скобок.
Программа должна выдать одну строчку: "правильно" или "неправильно".
Решение:
Сначала разберемся, что считать правильной расстановкой скобок:
1) количество открытых скобок всегда больше либо равно количеству
закрытых.
2) в конце выражения количество закрытых скобок равно количеству
открытых.
В этой задаче возможно употребление, так называемого "конечного
автомата", который изменяет свое состояние в зависимости от входных
данных. Этот автомат должен иметь счетчик скобок, первоначально
инициализированный нулем. Тогда:
1) при появлении символа "(" - увеличить счетчик на 1;
2) при появлении символа ")" - уменьшить счетчик на 1;
3) при появлении символа EOF - прекратить работу;
4) игнорировать появление любого другого символа.
Автомат мы создали, теперь надо правильно воспользоваться им для
решения предложенной задачи.
Посмотрим на счетчик: он содержит количество открытых, но еще не
закрытых скобок. Если счетчик стал меньше нуля, значит появилась
лишняя закрывающая скобка, т.е. выражение неверно (нарушение пункта
1).
Если после завершения работы конечного автомата счетчик не равен
нулю (т.е. не все скобки закрыты) то выражение неверно (нарушение
пункта 2).
Полученная программа будет короткой и красивой :) Ура, ура, ура!!!
Далее
ð
