循环永远不会在递归函数中完成
Loop Never Completes Within Recursive Function
我正在构建一个程序来恢复句子的括号,使它们成为格式正确的公式(句子逻辑中的 WFF)。例如,
- 句子 a
是一个 WFF。
- 句子 a > b
只有一种方法可以恢复括号使其成为一个WFF 即 (a > b)
.
- 句子 a > b > c
有两种方法可以恢复括号使其成为 WFF - ((a > b) > c)
或 (a > (b > c))
.
等等...
这个算法有一个迭代和递归元素
# returns index of wff
def findConnective(wff, indexes):
if len(wff) == None:
return -1
if (len(wff) <= 1):
return -1 # it's an atomic
for i in range(len(wff)): # looping through all chars in wff
if set([i]) & set(indexes): # if operator has already been used
continue
else: # if operator has not been usedl
for j in range(len(connectives)): # looping through all of the connectives
if wff[i] == connectives[j]: # if the wff contains the connective
indexes.append(i) # keeps track of which operators have already been used
return i
# returns what's on left of operator
def createLeft(wff, opIndex):
if opIndex == -1:
return wff # return the atomic
else:
return wff[:opIndex]
# returns what's on right of operator
def createRight(wff, opIndex):
if opIndex == -1:
return wff # return the atomic
else:
return wff[opIndex+1:]
# returns number of connectives
def numConnectives(wff):
count = 0
for c in wff:
if c == connectives:
count += 1
return count
def rec(wff):
result = []
ind = [] # list storing indexes of connectives used
if len(wff) == 1:
return wff
else:
for i in range(numConnectives(wff)):
opIndex = findConnective(wff, ind) # index where the operator is at
right = createRight(wff, opIndex) # right formula
# the first time it goes through, right is b>c
# then right is c
left = createLeft(wff, opIndex) # left formula
# left is a
# then it is b
return "(" + rec(left) + wff[opIndex] + rec(right) + ")"
print(rec("a>b>c"))
我的输出是 (a>(b>c))
,而它应该是 (a>(b>c))
AND ((a>b)>c)
。发生这种情况是因为递归函数内部的循环从不选择第二个运算符来执行递归调用。当return语句在for循环外时,输出为((a>b)>c)
如何使函数通过所有运算符(也就是对每个函数调用执行整个循环)
尽管 rec()
中 for
循环中的 return
是特定问题,但我认为总体问题是您使问题变得比需要的更难。您在处理 connectives
时也不一致,有时是一组字符 range(len(connectives))
,有时是单个字符 wff[i] == connectives[j]
。这是我对您的代码的简化:
connectives = {'>'}
def findConnectives(wff):
''' returns index of wff '''
if wff is None or len(wff) <= 1:
yield -1 # it's an atomic
else:
for i, character in enumerate(wff): # looping through all chars in wff
if character in connectives: # if the wff contains the connective
yield i
def createLeft(wff, opIndex):
''' returns what's on left of operator '''
return wff[:opIndex]
def createRight(wff, opIndex):
''' returns what's on right of operator '''
return wff[opIndex + 1:]
def rec(wff):
if len(wff) == 1:
return [wff]
result = []
for opIndex in findConnectives(wff):
if opIndex == -1:
break
left = createLeft(wff, opIndex) # left formula
right = createRight(wff, opIndex) # right formula
for left_hand in rec(left):
for right_hand in rec(right):
result.append("(" + left_hand + wff[opIndex] + right_hand + ")")
return result
print(rec("a>b>c"))
输出
% python3 test.py
['(a>(b>c))', '((a>b)>c)']
%
我正在构建一个程序来恢复句子的括号,使它们成为格式正确的公式(句子逻辑中的 WFF)。例如,
- - 句子
a
是一个 WFF。- - 句子
a > b
只有一种方法可以恢复括号使其成为一个WFF 即 (a > b)
.- - 句子
a > b > c
有两种方法可以恢复括号使其成为 WFF - ((a > b) > c)
或 (a > (b > c))
. 这个算法有一个迭代和递归元素
# returns index of wff
def findConnective(wff, indexes):
if len(wff) == None:
return -1
if (len(wff) <= 1):
return -1 # it's an atomic
for i in range(len(wff)): # looping through all chars in wff
if set([i]) & set(indexes): # if operator has already been used
continue
else: # if operator has not been usedl
for j in range(len(connectives)): # looping through all of the connectives
if wff[i] == connectives[j]: # if the wff contains the connective
indexes.append(i) # keeps track of which operators have already been used
return i
# returns what's on left of operator
def createLeft(wff, opIndex):
if opIndex == -1:
return wff # return the atomic
else:
return wff[:opIndex]
# returns what's on right of operator
def createRight(wff, opIndex):
if opIndex == -1:
return wff # return the atomic
else:
return wff[opIndex+1:]
# returns number of connectives
def numConnectives(wff):
count = 0
for c in wff:
if c == connectives:
count += 1
return count
def rec(wff):
result = []
ind = [] # list storing indexes of connectives used
if len(wff) == 1:
return wff
else:
for i in range(numConnectives(wff)):
opIndex = findConnective(wff, ind) # index where the operator is at
right = createRight(wff, opIndex) # right formula
# the first time it goes through, right is b>c
# then right is c
left = createLeft(wff, opIndex) # left formula
# left is a
# then it is b
return "(" + rec(left) + wff[opIndex] + rec(right) + ")"
print(rec("a>b>c"))
我的输出是 (a>(b>c))
,而它应该是 (a>(b>c))
AND ((a>b)>c)
。发生这种情况是因为递归函数内部的循环从不选择第二个运算符来执行递归调用。当return语句在for循环外时,输出为((a>b)>c)
如何使函数通过所有运算符(也就是对每个函数调用执行整个循环)
尽管 rec()
中 for
循环中的 return
是特定问题,但我认为总体问题是您使问题变得比需要的更难。您在处理 connectives
时也不一致,有时是一组字符 range(len(connectives))
,有时是单个字符 wff[i] == connectives[j]
。这是我对您的代码的简化:
connectives = {'>'}
def findConnectives(wff):
''' returns index of wff '''
if wff is None or len(wff) <= 1:
yield -1 # it's an atomic
else:
for i, character in enumerate(wff): # looping through all chars in wff
if character in connectives: # if the wff contains the connective
yield i
def createLeft(wff, opIndex):
''' returns what's on left of operator '''
return wff[:opIndex]
def createRight(wff, opIndex):
''' returns what's on right of operator '''
return wff[opIndex + 1:]
def rec(wff):
if len(wff) == 1:
return [wff]
result = []
for opIndex in findConnectives(wff):
if opIndex == -1:
break
left = createLeft(wff, opIndex) # left formula
right = createRight(wff, opIndex) # right formula
for left_hand in rec(left):
for right_hand in rec(right):
result.append("(" + left_hand + wff[opIndex] + right_hand + ")")
return result
print(rec("a>b>c"))
输出
% python3 test.py
['(a>(b>c))', '((a>b)>c)']
%