给定一个字符串，波兰表示法中最长的 WFF 之一的长度是多少？

Question

我正在 to write Python 中 WFF 'N Proof 游戏（无意侵犯版权）中一直很受欢迎的 Count-A-WFF 部分的一个版本。好吧，人气不高

我想我已经准备好了所有内容，并且运行根据需要准备了最多 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

实际上，我之前使用的函数之一会 return 一个字符串与波兰表示法排列的距离。因此，这比我预期的更容易修复。这就是我要找的东西：

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

给定一个字符串，波兰表示法中最长的 WFF 之一的长度是多少？

Given a String, What is the Length of the One of the Longest WFF in Polish Notation?

python

string

algorithm

python-2.7

polish-notation