CODEWITHSUNDEEP
python
James Sapam
James Sapam

Reputation: 16950

Find bracket which are not closed without using regex in python

I am trying to find out if any bracket is not closed without using regex, this is what I am trying but it is failed when the string are like "re(d))()(()"

def bracket(str):
   return [0,1][str.count(')') == str.count('(')]
s = "re(d))()(()"
print bracket(s)

Is there any better way to do it.

Upvotes: 0

Views: 233

Answers (3)

freakish
freakish

Reputation: 56587

Something like this?

def check_brackets(s):
    counter = 0
    for chr in s:
        if chr == "(":
            counter += 1
        elif chr == ")":
            counter -= 1
            if counter < 0:
                return False
    return counter == 0

EDIT: Here's how you can do that with many different bracket types:

BRACKETS = ("()", "[]", "{}")
def check_brackets(s):
    counter = []
    for chr in s:
        for br in BRACKETS:
            open = br[0]
            close = br[1]
            if chr == open:
                counter.append(open)
                break
            elif chr == close:
                try:
                    last_br = counter.pop()
                except IndexError:
                    return False
                if last_br != open: # ensures that the end matches the beginnig
                    return False
    return not bool(counter)

Note that it will mark ([)] as invalid (which is as it should be).

Upvotes: 6

Ashwini Chaudhary
Ashwini Chaudhary

Reputation: 251156

Using the approach from Shunting-yard algorithm:

from collections import deque
def solve(s):
    queue = deque()
    for c in s:
        if c == ')':
            if queue:
               queue.pop()
               continue
            return False
        elif c == '(':
            queue.append(c)
    return not bool(queue)

Demo:

>>> solve("re(d))()(()")
False
>>> solve("(re(d)()())")
True
>>> solve("(re(d)()((())))")
True
>>> solve(")))(((")
False

Upvotes: 4

zhangxaochen
zhangxaochen

Reputation: 34047

In [44]: from collections import deque
    ...: def solve(s):
    ...:    queue = deque()
    ...:    for c in s:
    ...:        if c == ')':
    ...:            if queue:
    ...:                queue.pop()
    ...:            else:
    ...:                return False
    ...:        elif c == '(':
    ...:            queue.append(c)
    ...:    return not bool(queue)
    ...: 

In [45]: print solve('()'), solve('())'), solve('re(d))()(()')
True False False

it's important to check if the deque being empty when a ')' comes

Upvotes: 1

Related Questions