괄호가 균형을 이루고 있는지 확인하려면 - 스택이없는 경우

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