<p>好吧,这是一个实际可行的解决方案。在</p>
<p>我不明白你的代码,而且我也没听说过DNF,所以我开始研究这个问题。在</p>
<p><a href="http://en.wikipedia.org/wiki/Disjunctive_normal_form" rel="nofollow noreferrer">Wikipedia page on DNF</a>非常有用。它包含了一个描述DNF的语法。在</p>
<p>在此基础上,我编写了一组简单的递归函数,我相信这些函数可以正确识别DNF。我的代码包括一些简单的测试用例。在</p>
<p>然后我意识到数据表示的二叉树性质使得应用DeMorgan定律简化“not”情况变得相对简单,方法是编写一个名为<code>negate()</code>的函数,它递归地求反,剩下的部分就就位了。在</p>
<p>我已经包括了测试用例。似乎有用。在</p>
<p>我没有进一步的计划。如果有人发现了bug,请提供一个测试用例,我会查看它。在</p>
<p>这段代码应该在任何python2.4或更新版本上运行。您甚至可以通过用一个简单的字符列表替换frozenset来将其移植到较旧的Python版本。我用python3.x进行了测试,发现异常语法已经改变了,因此如果您想在python3下运行它,就需要更改<code>raise</code>行;重要的部分都可以工作。在</p>
<p>在这个问题中,您没有提到您对<code>not</code>使用了什么字符;鉴于您对<code>and</code>使用了<code>&</code>,而对{<cd7>}使用了{<cd6>},我假设您很可能使用<code>!</code>来表示{<cd3>},并相应地编写了代码。关于您的代码,这是让我困惑的一件事:难道您不希望在您的输入中找到<code>not</code>?在</p>
<p>我做这件事很有意思。它不像数独游戏那样毫无意义。在</p>
<pre><code>import sys
ch_and = '&'
ch_not = '!'
ch_or = '|'
def echo(*args):
# like print() in Python 3 but works in 2.x or in 3
sys.stdout.write(" ".join(str(x) for x in args) + "\n")
try:
symbols = frozenset([ch_and, ch_not, ch_or])
except NameError:
raise Exception, "sorry, your Python is too old for this code"
try:
__str_type = basestring
except NameError:
__str_type = str
def is_symbol(x):
if not isinstance(x, __str_type) or len(x) == 0:
return False
return x[0] in symbols
def is_and(x):
if not isinstance(x, __str_type) or len(x) == 0:
return False
return x[0] == ch_and
def is_or(x):
if not isinstance(x, __str_type) or len(x) == 0:
return False
return x[0] == ch_or
def is_not(x):
if not isinstance(x, __str_type) or len(x) == 0:
return False
return x[0] == ch_not
def is_literal_char(x):
if not isinstance(x, __str_type) or len(x) == 0:
return False
return x[0] not in symbols
def is_list(x, n):
return isinstance(x, list) and len(x) == n
def is_literal(x):
"""\
True if x is a literal char, or a 'not' followed by a literal char."""
if is_literal_char(x):
return True
return is_list(x, 2) and is_not(x[0]) and is_literal_char(x[1])
def is_conjunct(x):
"""\
True if x is a literal, or 'and' followed by two conjuctions."""
if is_literal(x):
return True
return (is_list(x, 3) and
is_and(x[0]) and is_conjunct(x[1]) and is_conjunct(x[2]))
def is_disjunct(x):
"""\
True if x is a conjunction, or 'or' followed by two disjuctions."""
if is_conjunct(x):
return True
return (is_list(x, 3) and
is_or(x[0]) and is_disjunct(x[1]) and is_disjunct(x[2]))
def is_dnf(x):
return is_disjunct(x)
def is_wf(x):
"""returns True if x is a well-formed list"""
if is_literal(x):
return True
elif not isinstance(x, list):
raise TypeError, "only lists allowed"
elif len(x) == 2 and is_not(x[0]) and is_wf(x[1]):
return True
else:
return (is_list(x, 3) and (is_and(x[0]) or is_or(x[0])) and
is_wf(x[1]) and is_wf(x[2]))
def negate(x):
# trivial: negate a returns !a
if is_literal_char(x):
return [ch_not, x]
# trivial: negate !a returns a
if is_list(x, 2) and is_not(x[0]):
return x[1]
# DeMorgan's law: negate (a && b) returns (!a || !b)
if is_list(x, 3) and is_and(x[0]):
return [ch_or, negate(x[1]), negate(x[2])]
# DeMorgan's law: negate (a || b) returns (!a && !b)
if is_list(x, 3) and is_or(x[0]):
return [ch_and, negate(x[1]), negate(x[2])]
raise ValueError, "negate() only works on well-formed values."
def __rewrite(x):
# handle all dnf, which includes simple literals.
if is_dnf(x):
# basis case. no work to do, return unchanged.
return x
if len(x) == 2 and is_not(x[0]):
x1 = x[1]
if is_list(x1, 2) and is_not(x1[0]):
# double negative! throw away the 'not' 'not' and keep rewriting.
return __rewrite(x1[1])
assert is_list(x1, 3)
# handle non-inner 'not'
return __rewrite(negate(x1))
# handle 'and' with 'or' inside it
assert is_list(x, 3) and is_and(x[0]) or is_or(x[0])
if len(x) == 3 and is_and(x[0]):
x1, x2 = x[1], x[2]
if ((is_list(x1, 3) and is_or(x1[0])) and
(is_list(x2, 3) and is_or(x2[0]))):
# (a || b) && (c || d) (a && c) || (b && c) || (a && d) || (b && d)
lst_ac = [ch_and, x1[1], x2[1]]
lst_bc = [ch_and, x1[2], x2[1]]
lst_ad = [ch_and, x1[1], x2[2]]
lst_bd = [ch_and, x1[2], x2[2]]
new_x = [ch_or, [ch_or, lst_ac, lst_bc], [ch_or, lst_ad, lst_bd]]
return __rewrite(new_x)
if (is_list(x2, 3) and is_or(x2[0])):
# a && (b || c) (a && b) || (a && c)
lst_ab = [ch_and, x1, x2[1]]
lst_ac = [ch_and, x1, x2[2]]
new_x = [ch_or, lst_ab, lst_ac]
return __rewrite(new_x)
if (is_list(x1, 3) and is_or(x1[0])):
# (a || b) && c (a && c) || (b && c)
lst_ac = [ch_and, x1[1], x2]
lst_bc = [ch_and, x1[2], x2]
new_x = [ch_or, lst_ac, lst_bc]
return __rewrite(new_x)
return [x[0], __rewrite(x[1]), __rewrite(x[2])]
#return x
def rewrite(x):
if not is_wf(x):
raise ValueError, "can only rewrite well-formed lists"
while not is_dnf(x):
x = __rewrite(x)
return x
#### self-test code ####
__failed = False
__verbose = True
def test_not_wf(x):
global __failed
if is_wf(x):
echo("is_wf() returned True for:", x)
__failed = True
def test_dnf(x):
global __failed
if not is_wf(x):
echo("is_wf() returned False for:", x)
__failed = True
elif not is_dnf(x):
echo("is_dnf() returned False for:", x)
__failed = True
def test_not_dnf(x):
global __failed
if not is_wf(x):
echo("is_wf() returned False for:", x)
__failed = True
elif is_dnf(x):
echo("is_dnf() returned True for:", x)
__failed = True
else:
xr = rewrite(x)
if not is_wf(xr):
echo("rewrite produced non-well-formed for:", x)
echo("result was:", xr)
__failed = True
elif not is_dnf(xr):
echo("rewrite failed for:", x)
echo("result was:", xr)
__failed = True
else:
if __verbose:
echo("original:", x)
echo("rewritten:", xr)
echo()
def self_test():
a, b, c, d = 'a', 'b', 'c', 'd'
test_dnf(a)
test_dnf(b)
test_dnf(c)
test_dnf(d)
lstna = [ch_not, a]
test_dnf(lstna)
lstnb = [ch_not, b]
test_dnf(lstnb)
lsta = [ch_and, a, b]
test_dnf(lsta)
lsto = [ch_or, a, b]
test_dnf(lsto)
test_dnf([ch_and, lsta, lsta])
test_dnf([ch_or, lsta, lsta])
lstnn = [ch_not, [ch_not, a]]
test_not_dnf(lstnn)
test_not_dnf([ch_and, lstnn, lstnn])
# test 'and'/'or' inside 'not'
test_not_dnf([ch_not, lsta])
test_not_dnf([ch_not, lsto])
# test 'or' inside of 'and'
# a&(b|c) > (a&b)|(b&c)
test_not_dnf([ch_and, a, [ch_or, b, c]])
# (a|b)&c > (a&c)|(b&c)
test_not_dnf([ch_and, [ch_or, a, b], c])
# (a|b)&(c|d) > ((a&c)|(b&c))|((a&d)|(b&d))
test_not_dnf([ch_and, [ch_or, a, b], [ch_or, c, d]])
# a&a&a&(b|c) > a&a&(a&b|b&c) > a&(a&a&b|a&b&c) > (a&a&a&b|a&a&b&c)
test_not_dnf([ch_and, a, [ch_and, a, [ch_and, a, [ch_or, b, c]]]])
if __failed:
echo("one or more tests failed")
self_test()
</code></pre>
<p>现在,我很抱歉这么说,但我想得越多,我就越觉得你让我帮你做作业。所以,我刚刚编写了这段代码的一个改进版本,但我不打算在这里共享;我将把它留给您作为练习。在我描述之后,你应该可以很容易地做到。在</p>
<p>我有一个<code>while</code>循环反复调用<code>__rewrite()</code>,这是一个可怕的黑客行为。<code>rewrite()</code>函数应该能够通过对<code>__rewrite()</code>的单个调用重写树结构。只需做一些简单的更改,您就可以摆脱<code>while</code>循环;我做了它,并对其进行了测试,它工作了。您希望<code>__rewrite()</code>沿着树向下走,然后在返回的过程中重写内容,它将在一个过程中工作。您还可以修改<code>__rewrite()</code>以在列表格式不正确的情况下返回错误,并取消对<code>is_wf()</code>的调用;这也很简单。在</p>
<p>我怀疑你的老师会为<code>while</code>循环扣分,所以你应该有动力尝试这个。我希望你做的愉快,我希望你从我的代码中学到了一些有用的东西。在</p>