Чтобы проверить, сбалансированы ли скобки - Без стека

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