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)

 

[Jeremy Sanders]

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 ...

Don't you want to just test that the number of "("s equals the number of
")"s or am I missing the point?

Jeremy

 

[Adrian Dziubek]

Strings are immutable, so your method of slicing one letter at time
will be building lots of them. That shouldn't hurt you here, but it
will when you hit a bigger problem. In the i() there should be "return
op == 0" on the end.

def well(expr):
mapping = {'(':1, ')':-1}
count = 0
for s in expr:
if s in mapping:
count += mapping
if s < 0:
return False
return count == 0

def test_well():
examples = [
('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),
]
for expr, expected in examples:
assert well(expr) == expected

 

[Adrian Dziubek]

Don't you want to just test that the number of "("s equals the number of

")"s or am I missing the point?

I had this idea too, but there is additional requirement that any
beginning must have greater or equal number of '(' than ')'.

 

[Jeremy Sanders]

Yep, you are:

"())))((("

is certainly not "well parenthized".

Thanks for that!

 

[Diez B. Roggisch]

Don't you want to just test that the number of "("s equals the number of
")"s or am I missing the point?

Yep, you are:

"())))((("

is certainly not "well parenthized".

Diez

 

[David Smith]

Don't you want to just test that the number of "("s equals the number of
")"s or am I missing the point?


Jeremy

Using straight counting, )z))ab(c(ew( would be well parenthesized. I
suspect a better way would be to iterate over the string using a balance
counter that increases 1 for every open, decreases 1 for every close. A
negative balance at any moment would indicate an error as well as an
ending balance greater than 0.

--David

 

[John Machin]

# 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

E: H c, w t P.
F: A c, b à P.

Suggested better code:

def iterative(string):
paren_count = 0
for char in string:
paren_count += (char == '(') - (char == ')')
if paren_count < 0: break
return paren_count

You don't need the other versions

Try an iterative version of checking that () [] and {}
are balanced and nested appropriately.

Cheers,
John

 

[John Machin]

Using straight counting, )z))ab(c(ew( would be well parenthesized.  I
suspect a better way would be to iterate over the string using a balance
counter that increases 1 for every open, decreases 1 for every close.  A
negative balance at any moment would indicate an error as well as an
ending balance greater than 0.

--David

Ummm isn't that the OP's first function?

 

[John Machin]

In the i() there should be "return
op == 0" on the end.

Hard to tell. In the absence of any docs, we have to resort to divination on the
function name ... is "i" short for "iterative" or "imbalanced"?

 

[Simon Forman]

Try an iterative version of checking that () [] and {}
are balanced and nested appropriately.

Here's how I might approach the more general case:

def balanced(s, parens=("()",)):
    '''
    Example:
    >>> balanced('aAAA(b[bb(c]c))')
    True
    >>> balanced('aAAA(b[bb(c]c))', parens=("()", "[]"))
    False
    '''
    s = re.sub("[^%s]+" % re.escape("".join(parens)), "", s)
    for i in range(len(s)/2):
        for p in parens:
            s = s.replace(p, "")
    return not s

For short strings this is obviously slower than your 'iterative' function,
but the run time mostly depends on the number of pairs of parentheses
rather than the total length of the string, so for example it starts
winning on a string with 2 pairs of parentheses about 75 characters long.

def balanced(s, pairs=('()', '[]', '{}')):
opening = {}
closing = {}
for open_, close in pairs:
opening[open_] = closing[close] = object()

stack = []

for char in s:

marker = opening.get(char)
if marker:
stack.append(marker)
continue

marker = closing.get(char)
if marker:
try:
if stack.pop() is not marker:
return False
except IndexError:
return False

# All markers should be popped.
return not stack


Can parse sequences other than strings. :]