在检查括号是否平衡时，我得到的结果不正确(即，我知道输入字符串是平衡的，但输出是不平衡的)

Question

我正在研究数据结构和算法。我很难理解为什么在实现 Stack 并使用它来检查括号是否平衡时，我没有得到所需的输出(即输入字符串是平衡的，但我得到的字符串是不平衡的(。

class Stack(object): 
def __init__(self):
self.items = []
def __str__(self):
return str(self.items)
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()    
def isMatched(brackets):
opening = ('(', '[','{')
closing = (')', ']', '}')
stack = Stack()
for char in brackets:
if char in opening:
stack.push(char)
elif char in closing:
if stack.isEmpty or char != stack.pop():
#print('The brackets currently in the stack are: {}'.format(char), sep = ', ') 
return False
elif char not in opening and closing:
raise ValueError('Unknown character {char}'.format(char=char))
if not stack.isEmpty():
return False
return True

string = "[]()"
print(string, "-", "Balanced" if isMatched(string) else "Unbalanced")   

Answer 1

首先：

if stack.isEmpty or ...

stack.isEmpty实际上总是正确的。您需要调用该方法：stack.isEmpty()。

第二：

elif char not in opening and closing:

and closing部分实际上也总是正确的，但在这种情况下它是无关紧要的，因为此时您已经知道char不在closing.您应该完全省略and closing。

第三：

... or char != stack.pop():

char永远不能等于stack.pop()因为此时您知道char是右括号，而stack只包含左括号。您需要一些逻辑将每个右括号与其左括号对应项相关联。