23
\$\begingroup\$

I'm solving HackerRank "Stacks: Balanced Brackets" in Python.

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is considered to be balanced if the following conditions are met:

It contains no unmatched brackets. The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets. Given strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, print YES on a new line; otherwise, print NO on a new line.

My code:

def is_matched(expression):
    if len(expression) % 2 != 0:
        return False

    opening = ("(", "[", "{")
    closing = (")", "]", "}")
    mapping = {opening[0]:closing[0],
               opening[1]:closing[1],
               opening[2]:closing[2]}

    if expression[0] in closing:
        return False

    if expression[-1] in opening:
        return False

    closing_queue = []
    for letter in expression:
        if letter in opening:
            closing_queue.append(mapping[letter])
        elif letter in closing:
            if not closing_queue:
                return False

            if closing_queue[-1] == letter:
                closing_queue.pop()
            else:
                return False

    return True

t = int(input().strip())
for a0 in range(t):
    expression = input().strip()
    if is_matched(expression) == True:
        print("YES")
    else:
        print("NO")

What could be improved here? What can be done to make my code more idiomatic (pythonic code)?

Is my implementation bad? Why is it?

\$\endgroup\$
24
\$\begingroup\$

Review

Your implementation is quite good, but ofcourse there are always some things that can be improved upon.

  1. Use a if __name__ == '__main__' guard, see what they do.
  2. opening closing and mapping could be done a bit simpler
    • You may use list over the values, to create a list,
    • And you may zip those in a dictionary with the zip keyword.
  3. If you need to add alot of corner cases, your algorithm is likely off somewhere else.
  4. Consider adding Testcases, Docstrings, or both in the form of Doctest. To make it easier to Test your algorithm.

Alternative code

def is_matched(expression):
    """
    Finds out how balanced an expression is.
    With a string containing only brackets.

    >>> is_matched('[]()()(((([])))')
    False
    >>> is_matched('[](){{{[]}}}')
    True
    """
    opening = tuple('({[')
    closing = tuple(')}]')
    mapping = dict(zip(opening, closing))
    queue = []

    for letter in expression:
        if letter in opening:
            queue.append(mapping[letter])
        elif letter in closing:
            if not queue or letter != queue.pop():
                return False
    return not queue

if __name__ == '__main__':
    import doctest
    doctest.testmod()
\$\endgroup\$
  • 6
    \$\begingroup\$ opening = tuple('({[') could be opening = '({[', and similar for closing \$\endgroup\$ – Eric Wilson Nov 16 '17 at 21:42
  • 3
    \$\begingroup\$ Also consider writing mapping = dict(('()', '{}', '[]')). \$\endgroup\$ – 200_success Nov 17 '17 at 19:20
  • 1
    \$\begingroup\$ @SolomonUcko: There is zero significant difference in performance in the two ways of constructing a constant dict of size 3. To choose a less readable option because it is "somewhat more efficient" would be preposterous in this case. \$\endgroup\$ – wchargin Nov 18 '17 at 1:02
  • 2
    \$\begingroup\$ @SolomonUcko: It is faster. But the difference is not meaningful; this is an operation that takes microseconds and is performed only once; it is nowhere close to the bottleneck. This is exactly why people say not to prematurely optimize. Write good code and write readable code; only then should you profile and optimize hot spots. \$\endgroup\$ – wchargin Nov 18 '17 at 19:10
  • 1
    \$\begingroup\$ @Sigur Yes it will ignore all other chars in expression that are not brackets, so if your expression is a really long string it might work \$\endgroup\$ – Ludisposed Jun 8 '18 at 12:01
12
\$\begingroup\$
  • What if you enter something that isn't a bracket? Currently you ignore that, maybe you would want to error.
  • You don't need to make opening and closing. You can just use mapping.
def is_matched(expression):
    mapping = dict(zip('({[', ')}]'))
    queue = []
    for letter in expression:
        if letter in mapping:
            queue.append(mapping[letter])
        elif letter not in mapping.values():
            raise ValueError('Unknown letter {letter}'.format(letter=letter))
        elif not (queue and letter == queue.pop()):
            return False
    return not queue

If however you didn't want to ignore it or error, you could just remove the check, and have the code return False:

def is_matched(expression):
    mapping = dict(zip('({[', ')}]'))
    queue = []
    for letter in expression:
        if letter in mapping:
            queue.append(mapping[letter])
        elif not (queue and letter == queue.pop()):
            return False
    return not queue
\$\endgroup\$
  • \$\begingroup\$ Now I see, what you mean with the opening and closing being unnecessary. Just iterate over the mapping. \$\endgroup\$ – Ludisposed Nov 16 '17 at 10:17
  • 1
    \$\begingroup\$ @Ludisposed At first I meant it as you could just use a string. But then noticed you didn't need them at all... :) \$\endgroup\$ – Peilonrayz Nov 16 '17 at 10:21
  • \$\begingroup\$ To further add to your answer, mapping could be a constant \$\endgroup\$ – Restioson Nov 16 '17 at 11:42
8
\$\begingroup\$

Another thing to fix is the misleading name of the list variable. Items go in and out in LIFO order, making this a stack and not a queue.

\$\endgroup\$
5
\$\begingroup\$

The other answers have already covered what can be improved in your script so I will not repeat any of that. Just wanted to add an alternative I found interesting.

An elimination-based approach:

def f(my_string):
    brackets = ['()', '{}', '[]']
    while any(x in my_string for x in brackets):
        for br in brackets:
            my_string = my_string.replace(br, '')
    return not my_string

In every iteration the innermost brackets get eliminated (replaced with empty string). If we end up with an empty string, our initial one was balanced; otherwise, not.


Examples and notes:

  • Best case: s = '[](){}{}()[]' -> reduces to nothing in one while iteration.
  • Worst case: s = '({[[{()}]]})' -> same length string requires 6 iterations (destroyed inside out)

You could add some short-circuiting for quickly catching cases of lengthy strings that have an uneven number of opening and closing brackets so that you don't waste your time eliminating...

\$\endgroup\$
  • \$\begingroup\$ @Cimbali try to write it like that and see if you end up with something simpler and easier to understand than the code above. \$\endgroup\$ – Ev. Kounis Nov 20 '17 at 8:42
  • \$\begingroup\$ @Cimbali I do not see any \$\endgroup\$ – Ev. Kounis Nov 20 '17 at 8:48
  • \$\begingroup\$ @Cimbali Nice work. Only the return was changed since it was "upside-down" \$\endgroup\$ – Ev. Kounis Nov 20 '17 at 9:21
1
\$\begingroup\$

I was testing these algorithms, and it works well, but in some cases, they will fail. I would treat it as a string, using a stack, because it could works for a compiler, and could be more than parentheses, brackets and keys.

Test these cases, and if it works in all cases, you are doing well:

string = "[]{}()[][][]"
print "Should be true"
print str(is_matched(string))

string = "([()][][{}])"
print "Should be true"
print str(is_matched(string))

string = "[(])"
print "Should be false"
print str(is_matched(string))

string = "[([])()({})]"
print "Should be true"
print str(is_matched(string))

string = "[(,,),(,,[])]"
print "Should be true but it fails"
print str(is_matched(string))

string = "[(,,,(,,[])]"
print "Should be false"
print str(is_matched(string))

string = "]"
print "Should be false"
print str(is_matched(string))

string = "["
print "Should be false"
print str(is_matched(string))

string = "{[{}][][({})]}"
print "Should be true"
print str(is_matched(string))

string = """
    public static void main(String args[])
    {
        System.out.println("Hello world");
    }
"""

print "Should be true"
print str(is_matched(string))

string = "[[[((({{{}}})))]]]"
print "Should be true"
print str(is_matched(string))

This is my working solution, that works for all cases:

def pairs_stack(string, pairs = {'[': ']', '{': '}', '(': ')'}):

    opening = pairs.keys()

    closing = pairs.values()

    match = list()

    for s in string:
        if s in opening:
            match.insert(0, s)
        elif s in closing:
            if len(match) == 0:
                return False
            if match[0] == opening[closing.index(s)]:
                match.pop(0)
            else:
                return False

    if len(match) == 0:
        return True

    return False

Test it:

import time

millis = float(time.time() * 1000)

string = "[]{}()[][][]"
print "Should be true"
print str(pairs_stack(string))

string = "([()][][{}])"
print "Should be true"
print str(pairs_stack(string))

string = "[(])"
print "Should be false"
print str(pairs_stack(string))

string = "[([])()({})]"
print "Should be true"
print str(pairs_stack(string))

string = "[(,,),(,,[])]"
print "Should be true"
print str(pairs_stack(string))

string = "[(,,,(,,[])]"
print "Should be false"
print str(pairs_stack(string))

string = "]"
print "Should be false"
print str(pairs_stack(string))

string = "["
print "Should be false"
print str(pairs_stack(string))

string = "{[{}][][({})]}"
print "Should be true"
print str(pairs_stack(string))

string = """
    public static void main(String args[])
    {
        System.out.println("Hello world");
    }
"""

print "Should be true"
print str(pairs_stack(string))

string = "[[[((({{{}}})))]]]"
print "Should be true"
print str(pairs_stack(string))

millis = float(time.time() * 1000) - millis
print "Result " + str(millis)
\$\endgroup\$
0
\$\begingroup\$

One of the most frequent remarks on this site also applies here: make sure your code has comments to explain not just what it is doing, but what the reasoning is behind the code the comment is relevant towards.. The next person who needs to maintain your code will thank you for it, and if you ever have to look at your code again in half a year or so, you're going to be thankful you took the effort right now.

\$\endgroup\$
  • 2
    \$\begingroup\$ Do you really think that comments are essential? I think the code must be self-explanatory. If it needs lots of comments it's probably bad or redundant. \$\endgroup\$ – vnbrs Nov 19 '17 at 0:54
  • 2
    \$\begingroup\$ @vnbrs The debate between having well documented code and self-explanatory code is one that's been raging ever since programming was invented. The core of the matter is that even if you think your code is self-explanatory for you right now, in 3 years, someone fresh out of school with very little experience who is hired to maintain your code will be very happy to at least have a clue what's going on in your code from the comments. For example, I would very much like to have comments explaining the algorithm in the question. Not explaining the code, but the algorithm the code is implementing. \$\endgroup\$ – Nzall Nov 19 '17 at 14:02
  • \$\begingroup\$ While the code may be readable, the comments should explain WHY the code is doing what it is doing, since the reader may not be familiar with the algorithm or corner case. \$\endgroup\$ – simpleuser May 6 '18 at 2:58
-1
\$\begingroup\$

Program to check for balanced brackets in an expression using stack:

open_list = ["[","{","("]
close_list = ["]","}",")"]

def balance(myStr):
    stack= []
    for i in myStr:
        if i in open_list:
            stack.append(i)
        elif i in close_list:
            pos = close_list.index(i)
            if ((len(stack) > 0) and (open_list[pos] == stack[len(stack)-1])):
                stack.pop()
            else:
                return "Unbalanced"
    if len(stack) == 0:
        return "Balanced"


if __name__ == '__main__':
    expression = "{(abc)22}[14(xyz)2]"
    print(balance(expression))
\$\endgroup\$

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.