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

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'

Answer 2

人们通常提到的"堆栈溢出"与在您的情况下使用堆栈(作为数据结构)无关.

使用堆栈大多是合理的方式.如果你的目的只是为了找出答案

1. 所有左括号都有相应的结束括号,
2. 在开括号之前不会出现右括号;

然后你可以通过一个简单的循环加一个计数器来做到这一点:

在psuedo代码中:

function boolean isBalanced(input) {
    int counter = 0;
    while (! input.hasMoreChar) {
      char c = input.readNextChar();
      if (c == OPEN_PARENTHESIS) {
        counter++;
      } else if (c == CLOSE_PARENTHESIS) {
        if (counter == 0) {
          return false;    // Close parenthesis appear without a corresponding open
        } else {
          counter--;
        }
      }
    }

    return counter == 0;
}