To check if parenthesis are balanced- Without stack

Question

Suppose I have a very huge file and I want to check if parenthesis are balanced. I can't use stack, right? Because it'd result in a stack overflow. What approach I can use?

Answer 1

A simple counter. Since all you're doing is counting parenthesis:

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'

Why the (possibly)? Well, with this method, you would find this balanced:

a(bc))d(ef

which is probably not what you expect... so... you probably want to break early here:

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'