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)
--
http://mail.python.org/mailman/listinfo/python-list
