Войти
или
Зарегистрироваться
Курсы
Учебник
Учебник 2.0
ОГЭ/ЕГЭ
Олимпиады
Рубрикатор
Компилятор
Курсы
Строки
Правильная скобочная последовательность (ПСП)
Модуль:
Правильная скобочная последовательность (ПСП)
Задача
2
/6
Омега-лямбда-исчисление
Теория
Нажмите, чтобы прочитать/скрыть
Правильные скобочные последовательности состоят из открывающих и закрывающих скобок одного или нескольких типов, причём для каждой открывающей скобки есть закрывающая, и (в случае нескольких типов) их типы не перекрываются.
Правильные СП:
( ( ) ) ( ) ( )
{ } [ ( ) ] ( )
{ [ ( { } ) ] }
Неправильные СП:
) ) ( ( ) ) ( (
{ [ ( ] ) }
( ( ] }
Чтобы проверить, является ли скобочная последовательность из скобок одного типа, достаточно проверять баланс.
То есть мы заводим переменную, равную нулю (balance). Затем мы пробегаем по строке (если вы не умеете это делать - БЕГИТЕ, ГЛУПЦЫ!), увеличивая balance при встрече открывающей скобки и уменьшая - при закрывающей. Если на любом этапе баланс становится отрицательным или в конце он не равен нулю, значит, последовательность неправильная.
Задача
Омега-лямбда-исчисление - инновационная разработка "British Scientists, Inc" в сфере формальной логики. Любое выражение омега-лямбда-исчисления состоит из круглых скобок и термов (термом может быть любая последовательность из букв латинского алфавита).
Иззи-редукция - одна из операций над такими выражениями. При её выполнении проверяется, является ли скобочная последовательность в выражении правильной. Термы при этом игнорируются. Если последовательность правильная - она превращается в терм
gg
, если нет - в терм
wp
.
На вход подаётся омега-лямбда-выражение длиной не более 10
7
символов. Нужно вывести результат его иззи-редукции.
Примеры
№
Входные данные
Выходные данные
1
a(b(xx)f(g(x))m(y))
gg
2000
ms
256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач
Статистика успешных решений по компиляторам
Кол-во
С++ Mingw-w64
25
C#
2
Python
26
Комментарий учителя