parentheses - 检查括号是否平衡 - 没有堆栈

Question

假设我有一个非常大的文件，我想检查括号是否平衡。我不能使用堆栈，对吧？因为它会导致堆栈溢出。我可以使用什么方法？

Answer 1

一个简单的计数器。由于您所做的只是计算括号:

balance = 0
for c in open('filename.ext', 'r'):
    if c == '(':
        balance += 1
    elif c == ')':
        balance -= 1
if balance == 0:
    print 'parenthesis are (possibly) balanced'
else:
    print 'parenthesis are not balanced'

为什么(可能)？好吧，使用这种方法，您会发现这是平衡的:

a(bc))d(ef

这可能不是你所期望的......所以......你可能想在这里早点休息:

balance = 0
for c in open('filename.ext', 'r'):
    if c == '(':
        balance += 1
    elif c == ')':
        balance -= 1
        if balance < 0:
            break # -1 -> we found a closing paren without an opening one...
if balance == 0:
    print 'parenthesis are balanced'
else:
    print 'parenthesis are not balanced'