Loop Never Completes Within Recursive Function

Question

I am building a program to restore parenthesis to sentences to make them into well-formed formulas (WFF in sentential logic). For example,

- the sentence a is a WFF.

- The sentence a > b only has 1 way to have parenthesis restored to make it a WFF which is (a > b).

- The sentence a > b > c has 2 ways to have parenthesis restored to make it a WFF - either ((a > b) > c) or (a > (b > c)).

Etc...

There is an iterative and recursive element to this algorithm

# 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"))

My output is (a>(b>c)) when it should be (a>(b>c)) AND ((a>b)>c). This occurs because the loop inside of the recursive function never selects the second operator to perform the recursive call on. When the return statement is outside of the for loop, the output is ((a>b)>c)

How do I make it so the function goes through all operators (aka the entire loop executes for each function call)

Answer 1

Although the return in the for loop in rec() is the specific issue, I believe the overall issue is you're making the problem harder than it needs to be. You're also being inconsistent in your handling of connectives, sometimes its a collection of characters, range(len(connectives)), sometimes its a single character, wff[i] == connectives[j]. Here's my simplification of your code:

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"))

OUTPUT

% python3 test.py
['(a>(b>c))', '((a>b)>c)']
%