CODEWITHSUNDEEP
python
zahnzy
zahnzy

Reputation: 247

Returning True if the number of opening and closing parentheses are the same

I'm trying to create a function that will return true if the number of opening and closing parentheses in a string are equal. If they're not, I need it to return false. Currently this is not working for all strings. For example, paren_parity('p)(()ld))()(eog((h)k(j(m()(nc)fab)i)',) returns true as it should but paren_parity('d)p))mk)bc))j((eif(()ln)o)h((ag',) is returning True even though the number of open and closed parentheses are not the same.

def paren_parity(z):
  stack = []
  pushChars, popChars = "<({[", ">)}]"
  for c in z :
if c in pushChars :
  stack.append(c)
elif c in popChars :
  if not len(stack) :
    return False
  else :
    stackTop = stack.pop()
    balancingBracket = pushChars[popChars.index(c)]
    if stackTop != balancingBracket:
      return False
else :
  return True
return not len(stack)

Upvotes: 0

Views: 581

Answers (3)

Brian Malehorn
Brian Malehorn

Reputation: 2685

This is your problem:

else :
  return True

If you encounter something that isn't a parenthesis, you always return True. So d( will return True as soon as you hit the d.

You can fix it by just removing the those lines.

Upvotes: 2

mgilson
mgilson

Reputation: 310069

You've got a couple choices. The first is really easy, just count the number of opening parens and closing and check for equality:

def paren_parity(z):
    return z.count('(') == z.count(')')

But, this will pass strings like '))))((((' which you might not want. Otherwise, you can keep a count of the number of opened parens as you walk over the string. If the count ever goes negative, then return False:

def paren_parity(z):
    open_count = 0
    for c in z:
        if c == '(':
            open_count += 1
        if c == ')':
            open_count -= 1
            if open_count < 0:
                return False
    return open_count == 0

Of course, this still doesn't actually work for parsing programming language text because it'll fail for things like a = 5 * ('yeah!)') (since I have a parenthesis embedded in a string). However, I'm going to assume that isn't an issue for your current problem ;-).

Upvotes: 2

Nathaniel Ford
Nathaniel Ford

Reputation: 21239

This is easily resolved with a tail recursive function, including determining if there is a 'mismatch'.

def paren_parity(z, opening=0):
  if len(z) == 0:
    return opening == 0
  head, *tail = z
  if head == "(":
    opening = opening + 1
  elif head == ")":
    if opening == 0:
      return False
    opening = opening - 1
  return paren_parity(tail, opening)

opening acts as the stack you're pushing and popping from. Since you don't care as to the value, just whether it's a push or pop, holding an integer is enough.

Upvotes: -1

Related Questions