Постройте синтаксический анализатор для определяемого выше понятия дизъюнктивная-нормальная-форма (ДНФ)

Здравствуйте! Необходимо реализовать эту задачу на плюсах. Вроде писать умею, но не понимаю саму задачу, что требуется. Если кто-нибудь сможет какие-то тесты скинуть по типу " вот это нужно вводить в программу и она должна показывать вот это".
Нашел пост 10-летней давности, с ссылками https://en.wikipedia.org/wiki/... ent_parser
https://ru.wikipedia.org/wiki/... ьная_форма
Мои предположения: нужно вводить какое-то логическое выражение по типу X or Y и программа должна вычислить, является ли это выражение ДНФ или нет. Но ведь это выражение это строка из символов, придется находить в строке все слова и что они означают и т.д. Например или это || и это &&
Буду благодарен любым комментариям)

0

Садам, вы правы, можно реализовать этот анализатор по принципу ввода строки и дальнейшего её анализа. То есть ввели вы допустим строку: "(A * B) + (A * C)", программа по сути должна посимвольно пройтись по всей строке и, в зависимости от символа, который она встретит - выполнять определённые действия.

Также, если вы хотите, чтобы программа принимала на вход выражение со скобками - вам нужно их также проверять, допустим, если вы введёте в программу: "(A * B ( + (A * C)" - программа по идее должна выдать ошибку, так как количество открывающих скобок не соответствует количеству закрывающих.

Сообщение от Садам придется находить в строке все слова и что они означают

Да, скорее всего так и нужно будет сделать. Как раз на том сайте, что вы указали есть хорошие примеры того, что является ДНФ. Чтобы было проще, можно не использовать во входной строке такие слова как "или", "и", либо "or", "and" - лучше упростить их до "*" и "+", так программно будет легче определить, что означает символ.

0

Egorb17, Спасибо) Я теперь более менее представляю. А здесь можно обойтись без рекурсии, или никак?

0

Сообщение от Egorb17 Также, если вы хотите, чтобы программа принимала на вход выражение со скобками

В ДНФ скобки не имеют смысла, так как здесь последовательность операций целиком и полностью определяется приоритетом: конъюнкция выше дизъюнкции - при этом ДНФ - это последовательность конъюнкций объединенных дизъюнкцией, если расширить Ваш пример, то скажем выражение: (А * (В + (А * С)) - в ДНФ имеет вид: А * В + А * С. Так что для данного задания скобки можно вовсе запретить, хотя технически это будет не верно, поскольку выражение (А * В) + (А * С) - тождественно предыдущему, равно как и ((А * В) + (А * С)). Тогда анализ скобок сводится к тому, что скобка не должна объединять под собой одновременно операции И и ИЛИ, если выражение внутри скобок само по себе не является ДНФ.

Сообщение от Садам А здесь можно обойтись без рекурсии, или никак?

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

0