Python code for testing well parenthesized expression

[candide]

Hi,

I'm trying to implement in Python a function testing if an expression is well
parenthesized. For instance the expression "zx4er(1(er(Yy)ol)ol)ik" is correctly
parenthesized but this one "zx(4er(1(er(Yy)ol)ol)ik" is not.

My code follows at the end.

If you have a better algorithm or a better Python code (I'm a beginner in the
Python world), don't hesitate ...



#----------------------------------

# The obvious iterative version
def i(s):
    op = 0 # op : open parenthesis
    for k in range(len(s)):
        op += (s[k] == '(') - (s[k] == ')')
        if op < 0: break
    return op


# Recursive implementation of the preceding version
def r(s,op=0): # op : open parenthesis
    if len(s)==0:
        return op
    elif s[0]=='(':
        return r(s[1:],op+1)
    elif s[0]==')':
        if op==0:
            return -1
        else :
            return r(s[1:],op-1)
    else :
        return r(s[1:],op)


# "functional" style version
def f(s):
    if (len(s)!=0 and s[0]=='('):
        z=f(s[1:])
        if len(z)!=0:
            return f(z[1:])
        else:
            return None
    elif len(s)==0 or s[0] == ')':
        return s
    else:
        return f(s[1:])


def test(t,f):
    for z in t:
        print (z,f(z)==0)

# True True True True True False False
t=["zx4er(1(er(Yy)ol)ol)ik",
"x(x)x(x(x)xx(xx(x)x(x(x)xx)(xxxx))x(x(x)xx)(xxxx)x)(xxxx)",
"a(ty(y(y(bn)))lokl)kl",
"xc(er(tgy(rf(yh)()uj)ki))",
"e",
"rf(tgt)juj)jkik(jun)",
"zx(4er(1(er(Yy)ol)ol)ik"]

test(t,i)
print

test(t,r)
print

def test(t):
    for s in t: print (s,f(s)=="")

test(t)
#-------------------------------------------

and the corresponding output :


('zx4er(1(er(Yy)ol)ol)ik', True)
('x(x)x(x(x)xx(xx(x)x(x(x)xx)(xxxx))x(x(x)xx)(xxxx)x)(xxxx)', True)
('a(ty(y(y(bn)))lokl)kl', True)
('xc(er(tgy(rf(yh)()uj)ki))', True)
('e', True)
('rf(tgt)juj)jkik(jun)', False)
('zx(4er(1(er(Yy)ol)ol)ik', False)

('zx4er(1(er(Yy)ol)ol)ik', True)
('x(x)x(x(x)xx(xx(x)x(x(x)xx)(xxxx))x(x(x)xx)(xxxx)x)(xxxx)', True)
('a(ty(y(y(bn)))lokl)kl', True)
('xc(er(tgy(rf(yh)()uj)ki))', True)
('e', True)
('rf(tgt)juj)jkik(jun)', False)
('zx(4er(1(er(Yy)ol)ol)ik', False)

('zx4er(1(er(Yy)ol)ol)ik', True)
('x(x)x(x(x)xx(xx(x)x(x(x)xx)(xxxx))x(x(x)xx)(xxxx)x)(xxxx)', True)
('a(ty(y(y(bn)))lokl)kl', True)
('xc(er(tgy(rf(yh)()uj)ki))', True)
('e', True)
('rf(tgt)juj)jkik(jun)', False)
('zx(4er(1(er(Yy)ol)ol)ik', False)