检查字符串是否用括号平衡

Question

我得写Python补充函数:

def find(searched, open)

对于递归检查输入字符串是否具有平衡括号的函数：

def balanced (text):
    #....
    return find(text, None)[1]

我不能使用堆栈。当输入字符串为空时，当括号开始和结束时，我必须包含一个选项（以及一个小提示，不是每个结束括号我们都应该做出相同的反应），并包含对括号以外字符的反应。补充函数必须返回未处理的文本和以前的结果。

我有代码，遗憾的是它并不适用于我找到的每个例子:

PAIRS = {'(' : ')', '[' : ']'}

def balanced(text):
    #supp. f.
    def find(searched, open):         
        if not searched:
            return "", open is None
        rest, val = find(searched[1:], searched[0])
        if searched[0] in PAIRS.keys():
            return find(rest, open)
        elif searched[0] in PAIRS.values():
            if val is False:
                return rest, False
            elif open is not None and searched[0] == PAIRS [open]:
                return searched[1:], True
        else:
            return find(searched[1:], open)    
    return find(text, None)

if __name__ == '__main__':
    print("No string: ")
    print(balanced(""))
    print("########################")
    print("-----abc: ")
    print(balanced("abc"))
    print("########################")
    print("-----(a): ")
    print(balanced("(a)"))
    print("########################")
    print("-----)a(: ")
    print(balanced(")a("))
    print("########################")
    print("-----((a): ")
    print(balanced("((a)"))
    print("########################")
    print("-----((a(: ")
    print(balanced("((a("))
    print("########################")
    print("-----))a): ")
    print(balanced("))a)"))
    print("########################")
    print("-----()(a): ")
    print(balanced("()(a)"))
    print("########################")
    print("-----a(a): ")
    print(balanced("a(a)"))

在测试中，错误的答案在

((a)

和

((a(

我试图从 pythontutor.com 使用pdb和在线可视化调试器，但我无法将递归作为一个整体包装在那里......棘手的情况是，这也是帕森的谜题，我不能只是写得有太大不同。

我哪里做错了？

Answer 1

我在朋友的帮助下找到了正确的答案，命令的顺序是错误的，有些意图也没有出现在正确的地方。

我发现这段代码很难读懂，用起来也太复杂了，尽管这可能是一个挑战。带栈的版本对我来说更通用。

有一个工作版本供未来用户使用：

PAIRS = {'(' : ')', '[' : ']'}

def balanced(text):
#supp. f.
def find(searched, open):         
    if not searched:
        return "", open is None
    if searched[0] in PAIRS.keys():
        rest, val = find(searched[1:], searched[0])
        if val is False:
            return rest, False
        return find(rest, open)  
    elif open is not None and searched[0] == PAIRS[open]:
        return searched[1:], True
    elif searched[0] in PAIRS.values():
        return searched[1:], False
    else:
        return find(searched[1:], open)
return find(text, None)

Answer 2

这会得到您想要的结果：

代码

CASES = ["", 'abc', '(a)', ')a(', '((a)', '((a(', '))a)', '()(a)', 'a(a)' ]

left_pairs  = ['(','[']
right_pairs = [')',']']

def balanced(case):
    count = 0
    for char in left_pairs:
        count += case.count(char)
    for char in right_pairs:
        count -= case.count(char)

    if count == 0 or count % 1:
        return True
    else:
        return False

for case in CASES:
    print(str(balanced(case)) + "  " + case)

返回

True  
True  abc
True  (a)
True  )a(
False  ((a)
False  ((a(
False  ))a)
True  ()(a)
True  a(a)