Учитывая строку, какова длина одного из самых длинных WFF в польской нотации?

Question

Я пытаюсь написать версию всегда популярного раздела Count-A-WFF игры WFF 'N Proof (без нарушения авторских прав) на Python. Хорошо, не так популярно.

Я думаю, что у меня есть все, что нужно, до 4-буквенной строки.

def maximum_string(s):
if cs(s) == True:
    return len(s)
elif len(s) == 2:
    l1 = [cs(s[0]), cs(s[1])]
    if True in l1:
        return len(s) - 1
    else:
        return 0
elif len(s) == 3:
    first = s[0] + s[1]
    second = s[0] + s[2]
    third = s[1] + s[2]
    l1 = [cs(first), cs(second), cs(third)]
    if True in l1:
        return len(s) - 1
    l2 = [cs(s[0]), cs(s[1]), cs(s[2])]
    if True in l2:
        return len(s) - 2
    else:
        return 0
elif len(s) == 4:
    first = s[0]+s[1]+s[2]
    second = s[0]+s[1]+s[3]
    third = s[1]+s[2]+s[3]
    fourth = s[0]+s[2]+s[3]
    l1 = [cs(first), cs(second), cs(third), cs(fourth)]
    if True in l1:
        return 3
    first = s[0] + s[1]
    second = s[0] + s[2]
    third = s[0] + s[3]
    fourth = s[1] + s[2]
    fifth = s[1] + s[3]
    sixth = s[2] + s[3]
    l2 = [cs(first), cs(second), cs(third), cs(fourth), cs(fifth), cs(sixth)]
    if True in l2:
        return 2
    first = s[0]
    second = s[1]
    third = s[2]
    fourth = s[3]
    l3 = [cs(first), cs(second), cs(third), cs(fourth)]
    if True in l3:
        return 1
    else:
        return 0

def cs(string):
global length_counter, counter, letter
counter = 1
length_counter = 0
letters_left = len(string)
while letters_left != 0 and length_counter < len(string):
    letter = string[length_counter]
    if letter == 'C' or letter == 'A' or letter == 'K' or letter == 'E' or letter == "K":
        counter += 1 
    elif letter == 'N':
        counter += 0
    else:
        counter -= 1  
    length_counter += 1
    letters_left -= 1
if counter == 0 and len(string) == length_counter:
    return True
else:
    return False

Вспомогательная функция Maximum_string предназначена для того, чтобы, учитывая любую строку S, найти длину одного из самых длинных возможных wffs, которые вы можете сделать только из букв S. Конечно, я могу продолжить шаблон, который у меня есть на данный момент для вспомогательной функции Maximum_string. до длины 13. Но, комбинаторный взрыв очевиден. Таким образом, есть ли более элегантный способ завершить максимальную вспомогательную функцию строки?

Answer 1

По сути, одна из функций, которые у меня были ранее, будет возвращать расстояние от строки до перестановки в польской записи. Таким образом, это было удивительно проще исправить, чем я ожидал. Вот что я искал:

def maximum_string(string):
    global length_counter, counter, letter
    counter = 1
    length_counter = 0
    letters_left = len(string)
    while letters_left != 0 and length_counter < len(string):
        letter = string[length_counter]
        if letter == 'C' or letter == 'A' or letter == 'K' or letter == 'E' or letter == "K":
            counter += 1 
        elif letter == 'N':
            counter += 0
        else:
            counter -= 1  
        length_counter += 1
        letters_left -= 1
    if ('p' in string) or ('q' in string) or ('r' in string) or ('s' in string) or ('t' in string) or ('u' in string):
        return len(string) - abs(counter)
    else:
        return 0