<ПРЕД Задача:
СЛЕД>
Задачу решили 186 пользователей: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Регулярное выражение II

Time limit = 3 секунд(ы)

Дано регулярное выражение, состоящее из последовательности обязательных лексем и возможных элементов. Возможный элемент, в свою очередь, также является регулярным выражением ( состоит из обязательных лексем и возможных элементов ). Регулярное выражение имеет следующий рекуррентно-определенный синтаксис:

regexp ::= ( lexem | '[' regexp ']' ) +

Пример:

abc[de[f]g][h]i[j]

Соответвенно, lexem — любой ascii-символ, за исключением квадратных скобок.

Дать ответ, удовлетворяет ли данная строка S данному регулярному выражению R. Максимальная длина строки и регулярного выражения — 1000 символов. Регулярное выражение всегда задано корректно.

Вход Две строчки. В первой — регулярное выражение R, во второй — строка S.

Выход Выведите YES в случае, когда строка удовлетворяет регулярному выражению и NO — в другом случае.

Вход#1
[er[r]we]
erwe

Выход#1
YES

Вход#2
a[we[r[t[y[u]]]]]
awe

Выход#2
YES

Вход#3
a[we[r[t[y[u]]]]]
au

Выход#3
NO


Автор:
Известная
19 декабря 2003

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


© acm.mipt DevGroup
The page was generated in 170ms

SW soft NIX
ID = 3.228.220.31