我正在将命题逻辑语句翻译成合取范式。我遇到的问题是解析可能复杂的括号级别。我需要解决的问题是正确的顺序，我认为在向外移动之前应该先使用递归来解决内括号，但我不知道如何实现我的想法。该程序是用 Java 编写的。任何人都可以帮忙吗？
问问题
3127 次
3 回答
1
您能否举例说明您要转换为 CNF 的语句？我在想你的意思是在开始的逻辑语句中有括号，但这会有所帮助。
与此同时，我会说你不需要递归......但堆栈会非常有帮助:) 将项目及其数学运算推入堆栈，然后将它们弹出并在适当的时候对它们进行操作。由于是家庭作业，我不会详细介绍，但您会发现您将 push-push-push-pop-multiply-push-push-pop-add-pop-divide... 使用堆栈作为一种专注于当前操作的方式。
对 Postfix Notation 的调查也是相关的，可能会有所帮助……甚至关于它的维基百科文章也会给你一些想法（尽管那里绝对有更多面向计算机科学的文章）。
免责声明：在我的示例中，我没有考虑这些推送和弹出的数量或顺序：)
更新
您不需要多次传递数据，并且可以即时转换为 CNF。
你正朝着正确的方向前进，所以一些帮助/提示：
- 使用两个堆栈，一个用于操作数，一个用于运算符。
- 当您有两个操作数和一个运算符时，您弹出操作数，应用运算符，然后将结果作为新的（合并的）操作数推回
- 后缀的优点是您可以即时进行转换...例如，当您遇到 → 时，将 ¬ 应用于操作数堆栈并将 ⋁ 压入运算符堆栈
减少您的示例：
F→(E⋀(A→B))
转换的第一步看起来像这样（我假设您已经掌握了底层逻辑转换规则，并且这只是您正在制定的代码）：
F→(E⋀(A→B))
¬F⋁(E⋀(A→B))
¬F⋁(E⋀(¬A⋁B))
在 CNF 后缀中，它将如下所示：
F¬EA¬B⋁⋀⋁ // (Parentheses are obviated in postfix notation)
要到达那里，请从左到右一次通读您的初始逻辑语句...将操作数推入操作数堆栈，并将运算符推入操作数堆栈。
在应用运算符时，从操作数堆栈中弹出所需的操作数，应用运算符，然后将生成的字符串作为新的操作数推回堆栈。
右括号或较低优先级的操作会触发 pop-apply-push。整个事情看起来像这样：
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)。
如果您在阅读本文中的 unicode 逻辑符号时遇到问题，请告诉我；我可以用标准字符重做它，但它在 uni 中读起来好多了:)
HTH，
詹姆斯
PS：一个漂亮的小程序说明后缀在这里： http:
//fac-web.spsu.edu/cs/faculty/bbrown/web_lectures/postfix/
于 2012-04-30T19:27:39.940 回答
0
伪代码：
parseRestOfString (int openParens, String rest) {
c = rest (0);
if (c == ')' && openParens == 0) ...
这给你一个提示吗？
于 2012-04-30T19:23:22.433 回答