Создайте логические операторы путем анализа файла
Мне представили проблему чтения входного файла, который содержит логические операторы, и мне необходимо создать таблицу истинности, чтобы определить, соответствует ли ASK какой-либо / всем определенным моделям. Пример некоторых данных, которые я могу ожидать прочитать:
(p & z => x) => ((p | d) & z)
Пожалуйста, не слишком увлекайтесь примером, и если это действительно имеет смысл, я просто придумал, чтобы показать различные композиции, которые мне могут быть представлены. Несколько таких утверждений могут быть разделены точкой с запятой.
Я разобрал точку с запятой без всяких драм, и теперь у меня есть вектор строк, содержащий каждое отдельное утверждение, где каждая строка такая же, как представлена выше. Теперь, без использования круглых скобок, я считаю, что определение утверждений было бы довольно простым, но с их участием я теперь должен вычислять различные разделы раньше других. НАПРИМЕР:
(p | d) = result а потом (result & x)
Я видел людей, обсуждающих концепцию использования стека, чтобы определить, правильно ли закрыты квадратные скобки, но я не верю, что это подойдет для моей ситуации, так как это не позволило бы мне определить, какие утверждения были внутри того или иного набора скобок.
Текущая идея, которую я имею, состоит в том, чтобы использовать идею стека и попытаться определить «глубину» оператора (в частности, насколько далеко он вложен), а затем пометить это число каждым оператором, но я считаю, что это звучит как неэффективное решение. Кто-нибудь есть какие-либо советы о том, как я должен построить алгоритм для правильного решения проблемы?
Решение
Вам нужно построить дерево выражений, где ваши переменные являются листьями.
Ваше выражение станет:
=>
/ \
/ \
/ \
=> &
/ \ / \
& X | Z
/ \ / \
p z P D
После того, как вы создали представление такого рода, оценка проста.
Другой подход, с тем же результатом, сводит ваше выражение к чему-то вроде RPN (где вы можете использовать свою идею стека):
P, Z, &, X, =>, P, D, |, Z, &, =>
Как предлагается в комментариях, вы можете сделать это с помощью алгоритма маневрового двора.
Другие решения