檢查括號是否平衡 - 沒有堆棧

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. 沒有的情況下，一個右括號打開括號之前發生;
   在僞代碼

   ：

那麼你可以簡單地通過一個簡單的循環加一個計數器做

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; 
}