7
\$\begingroup\$

I'd appreciate feedback on the code itself (style, performance optimization (both space and time)), and also on the algorithm (because I think this is typically implemented using a stack).

The assumption I'm making here is that there are only two constraints to having balanced parentheses; one is that there be the same number of opening and closing parentheses, the other one that there not be at any point more closing parentheses than opening ones.

With this in mind, I implement my balanced parentheses checker using a simple counter, which is incremented with each opening paren, and decremented with each closing paren.

The two "checks" within the function are that the counter never go negative (return False if it does at any point), and that at the end the counter be 0.

def paren_checker(string):
    counter = 0
    for c in string:
        if c == '(':
            counter += 1
        elif c == ')':
            counter -= 1
        if counter < 0:
            return False

    if counter == 0:
        return True
    return False
\$\endgroup\$
3
\$\begingroup\$

Here is a somewhat improved version of the algorithm that allows for the three types:

def add_vectors(a, b):
    for i, x in enumerate(b):
        a[i] += x  # a is a list, so it supports item assignment

    return a


def is_balanced(string):
    #         (  [  {
    counts = [0, 0, 0]

    # dict of tuples to add based on char (like a switch statement)
    d = {'(': ( 1, 0, 0), '[': ( 0, 1, 0), '{': ( 0, 0, 1),
         ')': (-1, 0, 0), ']': ( 0,-1, 0), '}': ( 0, 0,-1)}

    for char in string:
        try:
            counts = add_vectors(counts, d[char])
        except KeyError:  # char is not in dict, so it isn't '(', '{', etc.
            continue

        if -1 in counts:  # close without open
            return False

    return counts == [0, 0, 0]  # will resolve to initial state if correct

Of course, this still doesn't cover the case of {[}] as is common in non-stack implementations.

\$\endgroup\$
8
\$\begingroup\$

I would replace your last lines with return counter == 0 as it is more compact and easier to read

\$\endgroup\$
  • 1
    \$\begingroup\$ @pycoder not counter may be shorter but counter == 0 is more readable IMO \$\endgroup\$ – ovs Jan 20 '17 at 6:53
3
\$\begingroup\$

I checked your algorithm against a few examples on paper and it should actually work if I haven't missed anything. Nevertheless, it has a drawback. If you would like to introduce new types of parenthesis like braces {} or squared parenthesis [] it may not work properly and extending it may not be easy. When you use the stack data structure, it will be handled without huge problems.

\$\endgroup\$
  • 1
    \$\begingroup\$ You're right; I actually just looked into extending my algorithm to other kinds of brackets and it does run into the problem of returning True for stuff like ( { ) }, which is obviously wrong. The stack makes the most sense I guess, but I'm thinking what I have above might be faster than a stack in case we're only dealing with the opening and closing of a single kind of symbol, since we only have to update a varialbe and not deal with a stack. \$\endgroup\$ – jeremy radcliff Jan 19 '17 at 22:17
  • \$\begingroup\$ @jeremyradcliff extending is easy just add for lparen, rparen in ( ( '(', ')' ), ( '[', ']' )) and modify accordingly \$\endgroup\$ – Caridorc Jan 19 '17 at 22:28
1
\$\begingroup\$

Your code is good, but I have, in my opinon, a slightly more readable and potentially faster one: (This code will NOT check for the balenced open/closing part -- but it may still help others, or you could use it before checking with your idea)

def paren_checker(string):
    if string.count("(") == string.count(")"):
        return True
    else:
        return False

Or even better yet:

def paren_checker(string):
    return string.count("(") == string.count(")")

I hope you find this useful (I had to do something similar before, but trust me, sometimes there are even more weird things that users could do!)

Even better yet: (Allows you to check ANY type of brackets, they don't even have to be brackets, they could be any type of start/close things you want)

def any_bracket_checker(string, bracket_type_start, bracket_type_end):
    return string.count(bracket_type_start) == string.count(bracket_type_end)

print any_bracket_checker("(string)","(",")")
\$\endgroup\$
  • \$\begingroup\$ This code does not work. You should re-read OP's assumptions: the string should contain equal amount of '(' and ')', that's one part; but you failed at considering the balanced part where there is more closing part than opening ones at some point, like in '()))((()'. \$\endgroup\$ – Mathias Ettinger Jan 20 '17 at 10:53
  • \$\begingroup\$ @MathiasEttinger Oh yes. My bad. But i still believe some people may have a use for this code. Also, it can be used as a check before hand perhaps on a long string to save time (would it?). I will edit it my post to warn people of this caveat \$\endgroup\$ – John Hon Jan 20 '17 at 11:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.