Допустим мы ввели такой набор каких-то абстрактных правил (форма записи "если A и B то C"

A&B -> C
D -> E
C&E->G

потом на основе входной строки программа должна составить вывод на основе этих правил.
К примеру если входная строка была

"A&B". Программа должна выдать - "C"
а если ввели например
"A&B&E" программа должна выдать - "G" (потому как A&B это C, а C&E- это G)

расскажите алгоритм хотя бы на словах, в виде схемы/кода вообще было бы замечательно
Спасибо!

Ну в чём проблема??? Вроде сам алгоритм рассказал???

Ты считываешь строку, потом разбиваешь её на отдельные символы, символы которые стоят между знаками, ты записываешь куда-то в какую-то переменную(сам придумай) а знак ты записываешь в другую переменную(лучше какую-то структуру со множеством полей) и там же указываешь ссылку между какими переменными

Потом ты пишешь алгоритм обработки слево направо по паре знаков, делая соответствующие замены

Вообщем начни хоть что-то пытаться делать, а там станет понятнее что тебе уже конкретно нужно будет(мне начинание хоть с чего-нить помогает).

Это сообщение отредактировал(а) DarkProg - 25.1.2010, 20:01

Как понимаю, это вариант стандартной задачи парсинга математического (булева арифметика) выражения, записанного в виде текстовой строки. Задача эта много раз обсуждалась и даже здесь. Я даже где-то встречал библиотеки ее рашающие и красивые описания алгоритмов - но где - не помню.

Сам я ее решал лет 15 назад (парсинг булевой строки любой сложности со скобками и т.п.). Если нужно, могу найти старый код на VB. Но в обьектном языке такую задачу решать приятнее.

Заводим ассоциативный массив, в котором ключом является первый символ левой части правила, а значением - массив ссылок на правила, начинающиеся с этого символа. Затем просматриваем строку слева направо по одному символу и ищем, есть ли такой ключ в массиве. Если есть, то перебираем все правила, начинающиеся с этого символа и проверяем, совпадают ли следующие символы строки с левой частью правила. Если совпадения найдены, то выбираем самое длинное из подходящих правил, заменяем кусок строки на правую часть правила, возвращаемся в начало строки. Если же совпадения не найдены, то переходим к следующему символу строки. Повторяем до тех пор, пока не просмотрим всю строку.

Этот алгоритм далеко не оптимален, но зато прост в реализации. Для ускорения работы на длинных строках можно запомнить максимальную длину (L) левой части правила и после замены переходить не к началу строки, а на (L-1) символов назад.

Вопросы

 однозначна ли грамматика?
Существуют ли правила укорачивающие длину строки?