Построение логических выражений путем разбора файла

Question

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

(p & z => x) =>((p | d) & z)

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

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

(p | d) = result, а затем (result & x)

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

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

Answer 1

Вам нужно построить дерево выражений, где ваши переменные - листья.

Ваше выражение станет тогда:

 => 
    /\ 
    / \ 
    / \ 
    =>  & 
/\ /\ 
    & X | Z 
/\ /\ 
p z P D 

После того, как вы создали этот вид представления, оценка очень проста.

Другой подход, с тем же результатом, уменьшает ваше выражение к чему-то вроде RPN (где вы можете использовать свой стек идею):

P, Z, &, X, =>, P, D, |, Z, &, => 

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