# Python code for testing well parenthesized expression

candide candide at free.invalid
Tue Jul 14 08:37:24 EDT 2009

```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)

```