我试图处理一个一阶逻辑公式,在python中用嵌套列表和字符串表示,这样它就可以用析取范式了
即['&;',['|','a','b'],['|','c','d']]
变成
['|'['amp;',['amp;','a','c'],['amp;','b','c']],['amp;',['amp;','a','d',['amp;','b','d']]]
其中|是“or”和“and”是“and”。在
目前,im使用递归实现,它对一个公式进行多次传递,直到在“ands”的列表参数中找不到任何嵌套的“或”符号。在
这是我的实现,performDNF(form)是入口点。现在它只对公式执行一次传递,但是while循环检查函数在“&;s”中找不到“|”并终止,请帮助任何让我抓狂的人。在
def dnfDistributivity(self, form):
if isinstance(form, type([])):
if len(form) == 3:
if form[0] == '&':
if form[1][0] == '|':
form = ['|', ['&', form[2], form[1][1]], ['&', form[2], form[1][2]]]
elif form[2][0] == '|':
form = ['|', ['&', form[1], form[2][1]], ['&', form[1], form[2][2]]]
form[1] = self.dnfDistributivity(form[1])
form[2] = self.dnfDistributivity(form[2])
elif len(form) == 2:
form[1] = self.dnfDistributivity(form[1])
return form
def checkDistributivity(self, form, result = 0):
if isinstance(form, type([])):
if len(form) == 3:
if form[0] == '&':
print "found &"
if isinstance(form[1], type([])):
if form[1][0] == '|':
return 1
elif isinstance(form[2], type([])):
if form[2][0] == '|':
return 1
else:
result = self.checkDistributivity(form[1], result)
print result
if result != 1:
result = self.checkDistributivity(form[2], result)
print result
elif len(form) == 2:
result = self.checkDistributivity(form[1], result)
print result
return result
def performDNF(self, form):
while self.checkDistributivity(form):
form = self.dnfDistributivity(self.dnfDistributivity(form))
return form
对不起,我没试着理解你的解决办法。我认为这太难读了,可能方法太麻烦了。在
如果你有一个DNF,你需要做的就是找到所有的原子组合,从每个子列表中取出一个。这几乎可以归结为this问题。。。从每个或子类中,你需要取一个原子,并将所有这些与和结合起来。在
所有可能的与从句的OR组合会产生您想要的结果。正确的?在
好吧,这是一个实际可行的解决方案。在
我不明白你的代码,而且我也没听说过DNF,所以我开始研究这个问题。在
Wikipedia page on DNF非常有用。它包含了一个描述DNF的语法。在
在此基础上,我编写了一组简单的递归函数,我相信这些函数可以正确识别DNF。我的代码包括一些简单的测试用例。在
然后我意识到数据表示的二叉树性质使得应用DeMorgan定律简化“not”情况变得相对简单,方法是编写一个名为
negate()
的函数,它递归地求反,剩下的部分就就位了。在我已经包括了测试用例。似乎有用。在
我没有进一步的计划。如果有人发现了bug,请提供一个测试用例,我会查看它。在
这段代码应该在任何python2.4或更新版本上运行。您甚至可以通过用一个简单的字符列表替换frozenset来将其移植到较旧的Python版本。我用python3.x进行了测试,发现异常语法已经改变了,因此如果您想在python3下运行它,就需要更改
raise
行;重要的部分都可以工作。在在这个问题中,您没有提到您对}使用了{},我假设您很可能使用},并相应地编写了代码。关于您的代码,这是让我困惑的一件事:难道您不希望在您的输入中找到
not
使用了什么字符;鉴于您对and
使用了&
,而对{!
来表示{not
?在我做这件事很有意思。它不像数独游戏那样毫无意义。在
现在,我很抱歉这么说,但我想得越多,我就越觉得你让我帮你做作业。所以,我刚刚编写了这段代码的一个改进版本,但我不打算在这里共享;我将把它留给您作为练习。在我描述之后,你应该可以很容易地做到。在
我有一个
while
循环反复调用__rewrite()
,这是一个可怕的黑客行为。rewrite()
函数应该能够通过对__rewrite()
的单个调用重写树结构。只需做一些简单的更改,您就可以摆脱while
循环;我做了它,并对其进行了测试,它工作了。您希望__rewrite()
沿着树向下走,然后在返回的过程中重写内容,它将在一个过程中工作。您还可以修改__rewrite()
以在列表格式不正确的情况下返回错误,并取消对is_wf()
的调用;这也很简单。在我怀疑你的老师会为
while
循环扣分,所以你应该有动力尝试这个。我希望你做的愉快,我希望你从我的代码中学到了一些有用的东西。在相关问题 更多 >
编程相关推荐