current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 4 down vote favorite
1

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
share|improve this question
2  
Please never edit the code after receiving an amswer, it invalidates it. – Caridorc 8 hours ago
    
@Caridorc, sorry didn't think it was a problem because I mentioned it in edit and it was just style, but I see your point, I won't do it in the future. – jeremy radcliff 8 hours ago
up vote 6 down vote

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

share|improve this answer
    
Thank you, good point. – jeremy radcliff 8 hours ago
    
Or just return not counter to take advantage of the fact that non-zero integers resolve to True and 0 resolves to False. The not then makes x == 0 True as you would expect. This is not as readable (and probably not as fast), but an interesting trick to shorten the line by one character :-) – pycoder 5 hours ago
up vote 3 down vote

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.

share|improve this answer
1  
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. – jeremy radcliff 8 hours ago
    
@jeremyradcliff extending is easy just add for lparen, rparen in ( ( '(', ')' ), ( '[', ']' )) and modify accordingly – Caridorc 8 hours ago
    
@Caridorc, good point, thank you. – jeremy radcliff 8 hours ago
up vote 0 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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