271. Простой синтаксис

Синтаксис языка Хедониан невероятно прост. Вот его правила:

0. Символами языка являются только буквы от ‘p’ до ‘z’, а также N, C, D, E, I.

1. Каждый символ от ‘p’ до ‘z’ является правильной фразой.

2. Если фраза s корректна, то таковой является и фраза Ns.

3. Если фразы s и t корректны, то корректными являются и фразы Cst, Dst, Est, Ist.

4. Только правила 0 - 3 определяют корректно построенную фразу.

Вход. Каждая входная строка содержит фразу – последовательность из не менее 1 и не более чем 256 символов.

Выход. Для каждой фразы вывести “YES” или “NO” в зависимости от того, удовлетворяет ли она синтаксису языка Хедониан.

Пример входа

Cp

Isz

NIsz

Cqpq

Пример выхода

NO

YES

YES

NO

РЕШЕНИЕ

синтаксический анализ

Анализ алгоритма

Следует провести синтаксический анализ входной строки по описанным в условии задачи правилам. Если строка удовлетворяет всем правилам, то выводим “YES”, иначе “NO”.

Реализация алгоритма

Входную фразу читаем в массив m.

char m[257];

Функция eval производит синтаксический анализ строки, хранящейся в символьном массиве m. Переменная ptr хранит номер текущей разбираемой позиции. Если входная строка не принадлежит языку Хедониан, то устанавливаем flag = 0, после чего выходим из рекурсии.

void eval(void)

{

if (flag) return;

if ((m[ptr] >= 'p') && (m[ptr] <= 'z')) {ptr++; return;}

if (m[ptr] == 'N') {ptr++; eval(); return;}

if ((m[ptr] == 'C') || (m[ptr] == 'D') ||

(m[ptr] == 'E') || (m[ptr] == 'I'))

{

ptr++; eval(); eval();

return;

}

flag = 1;

}

Основной цикл программы. Читаем входную фразу в массив m, устанавливаем значения переменных flag и ptr в 0, вызываем процедуру eval. Если обработаны все буквы (ptr равно длине строки m) и переменная осталась равной 0, то фраза является словом языка Хедониан, выводим “YES”. Иначе выводим “NO”.

while(gets(m))

{

flag = ptr = 0; eval();

if (ptr < (int)strlen(m)) flag = 1;

if (flag) printf("NO\n"); else printf("YES\n");

}