Можете ли вы привести пример заявления, которое вы переводите в CNF? Я думаю, вы имеете в виду, что в исходном логическом выражении есть круглые скобки, но это поможет увидеть.
В то же время я скажу, что вам не нужна рекурсия ... но стек был бы очень полезен:) Нажимайте элементы и их математические операции на стек, затем выталкивайте их и действуйте на них, когда это необходимо , Поскольку это домашняя работа, я не буду вдаваться в подробности, но вы обнаружите, что вы будете использовать push-push-push-pop-multip-push-push-pop-add-pop-divide ... использовать стек как способ фокусировки на текущей операции.
Расследование по нотации Postfix также актуально и может помочь ... даже статья в Википедии на нем даст вам некоторые идеи (хотя там есть абсолютно более ориентированные на компьютерные науки статьи).
Отказ от ответственности: я не ставил никаких мыслей в число или порядок этих толчков и хлопков в моем примере:)
Update
Вам не нужно больше, чем один проход через данные, и вы можете конвертировать в CNF «на лету».
Вы двигаетесь в правильном направлении, так что некоторые помощь/советы:
- Используйте два стека, один для операндов и один для операторов.
- Когда у вас есть два операнда и оператор, вы выставляете операнды, применяете оператор и возвращаете результат назад как новый (консолидированный) операнд
- Преимущество постфикса заключается в том, что вы можете совершать конвертацию на лету ... например, когда вы столкнулись с → нанесите ¬ в стек операндов и нажать ⋁ на стек оператора
Принимая сокращение вашего примера:
F→(E⋀(A→B))
первые шаги преобразования выглядит так (я предполагаю, что у вас есть un derlying логико-преобразование правил вниз погладить, и что это просто код, который вы разработки):
F→(E⋀(A→B))
¬F⋁(E⋀(A→B))
¬F⋁(E⋀(¬A⋁B))
В CNF постфикса, он будет выглядеть следующим образом:
F¬EA¬B⋁⋀⋁ // (Parentheses are obviated in postfix notation)
Чтобы попасть туда, читайте через ваш исходный логический оператор за один проход слева направо ... Наведите операнды на стек Операндов и операторы на стек операторов.
Когда вы применяете Операторы, поместите необходимые операнды из стека операндов, примените оператор и нажмите результирующую строку обратно в стек как новый операнд.
Закрывающие круглые скобки или операции с более низким приоритетом запускают поп-наложение. Все это выглядит следующим образом:
Operand Operator
Stack Stack
---------- ----------
Read F: Push onto Operand stack F ........ ..........
Read →: On-the-fly conversion (→ becomes ¬⋁)
Unary Operator ¬ pops F from Operands; applies it; pushes back to Operands
¬F ....... ..........
Push ⋁ onto the op-stack ¬F ....... ⋁ .......
Read (: Discard
Read E: Push onto Operands stack ¬F E .... ⋁ ......
Read ⋀: Push onto Operators stack ¬F E .... ⋁⋀ .....
Read (: Discard
Read A: Push onto Operands stack ¬F E A .. ⋁⋀ .....
Read →: On-the-fly conversion (→ becomes ¬⋁)
Unary Operator ¬ pops A from Operands; applies; pushes back to Operands
¬F E ¬A . ⋁⋀ .....
Push ⋁ onto Operators stack ¬F E ¬A . ⋁⋀⋁ ....
Read B: Push onto Operands stack ¬F E ¬A B ⋁⋀⋁ ....
Read): Triggers Operators/Operands pop; applies; pushes back to Operands
(After, there are three operands on the Operands stack)
¬F E (¬A⋁B) ⋁⋀ ....
Read): Triggers Operators/Operands pop; applies; pushes back to Operands
(After, there are two operands on the Operands stack)
¬F (E⋀(¬A⋁B)) ⋁ ....
No more reads: Final Operators/Operands pop/apply/push (result is output)
¬F⋁(E⋀(¬A⋁B))
Предостережения и примечания:
Это только начало в правильном направлении ... вы будете иметь дело с проблемами, как старшинство операторов (т.е. вы нажимаете и действуете позже, или поп и действуете сейчас). Вы найдете, что ваше решение основано на следующем символе, который вы читаете (а не на закрывающей скобке, как я подразумевал выше).
Это звучит сложнее, чем это ... псевдокод для вышеизложенного не должен превышать 12-15 строк. Тем не менее, есть сложности, которые я не рассматривал ... функция < -> должна быть смоделирована таким образом, чтобы она была → выше ... вам придется взять это мышление и реализовать все правила преобразования.
Подразумеваемые круглые скобки могут вас трогать, например.
6 * (8 * 6) + 4
действительно
(6 * (8 * 6)) + 4
Если вы не обрабатываете приоритета операторов правильно, вы могли бы в конечном итоге с чем-то вроде
686*4+*
, который дает вам 312, вместо правильного ответа (292).
Если у вас возникли проблемы с чтением логических символов юникода в этом сообщении, сообщите мне; Я могу повторить его с помощью стандартных символов, но он читает так много лучше в универе:)
HTH,
Джеймс
PS: Изящный маленький апплет, иллюстрирующий постфикса здесь:
http://fac-web.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
У меня была какая-то фанковая система, где я пробовал работать полупрозрачно. Он попытался начать с самого начала, найти первые открытые парсеры и взять все до первого закрытия parens и рекурсивно прокормить его до тех пор, пока не будет только один открытый parens и один близкий parens. Тогда он попытается решить. Проблема у меня была в том, что при решении, иногда требуется больше парнеров, чтобы метод попадал в петлю. Это и я не закончили логику, поэтому я не смог ее протестировать. – Rambo8000
http://stackoverflow.com/questions/15982087/how-to-convert-statements-into-cnf/15982562?noredirect=1#15982562 – user2260056
[Аналогичный вопрос ....Таким образом, мы должны написать код, используя как IF-ELSE для всех возможных входов например: (Не (не)), (НЕ (NOT (OR (AB)))] [1] [ 1]: http://stackoverflow.com/questions/15982087/how-to-convert-statements-into-cnf/15982562?noredirect=1#15982562 – user2260056