Learn how you can become a Python programmer in just 12 weeks.

    We respect your privacy. Unsubscribe at anytime.

    Explaining and Solving the Balancing Bracket Problem and Analysing the Performance and Run-time

    We are going to answer the following questions.

    • Why is the Balancing Bracket Problem interesting?
    • How a Stack can help you solve the Balancing Bracket Problem efficiently?
    • What is the time complexity and do our implantation have that performance?

    How to solve the problem in Python

    You need a stack. You could use a Python list as a stack, while the append and pop last element in the Python list are amortised O(1) time, it is not guaranteed to get the performance you need.

    Implementing your own stack will give the the worst case O(1) time complexity. So let us begin by implementing a Stack in Python.

    It is more simple than you think.

    class Node:
        def __init__(self, element=None, next_node=None):
            self.element = element
            self.next_node = next_node
    class Stack:
        def __init__(self):
            self.stack = None
        def push(self, element):
            self.stack = Node(element, self.stack)
        def pop(self):
            self.stack = self.stack.next_node
        def is_empty(self):
            return self.stack is None

    If you want to read more about stacks also check out this post.

    Then given that stack solving the Balancing Bracket Problems becomes easy.

    def balancing_bracket(s):
        stack = Stack()
        for c in s:
            if c in "([{":
            elif c in ")]}":
                if stack.is_empty():
                    return False
                e = stack.pop()
                if e == "(" and c == ")":
                elif e == "[" and c == "]":
                elif e == "{" and c == "}":
                    return False
        if not stack.is_empty():
            return False
            return True

    Time complexity analysis of our solution

    Well, the idea with the solution is that it should be O(n), that is, linear in complexity. That means, that a problem of double size should take double time to solve.

    The naive solution takes O(n^2), which means a problem of double size takes 4 times longer time.

    But let us try to investigate the time performance of our solution. A good tool for that is the cProfile library provided by Python.

    But first we need to be able to create random data. Also notice, that the random data we create should be balancing brackets to have worst case performance on our implementation.

    To generate random balancing brackets string you can use the following code.

    import random
    def create_balanced_string(n):
        map_brackets = {"(": ")", "[": "]", "{": "}"}
        s = Stack()
        result = ""
        while n > 0 and n > s.get_size():
            if s.is_empty() or random.randint(0, 1) == 0:
                bracket = "([{"[random.randint(0, 2)]
                result += bracket
                result += map_brackets[s.pop()]
            n -= 1
        while not s.is_empty():
            result += map_brackets[s.pop()]
        return result

    Back to the cProfile, which can be called as follows.

    import cProfile

    That will generate an output like the following.

             14154214 function calls in 6.988 seconds
       Ordered by: standard name
       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
            1    0.000    0.000    6.988    6.988 <string>:1(<module>)
            2    0.000    0.000    0.000    0.000 BalacingBracketProblem.py:11(__init__)
      1000000    0.678    0.000    0.940    0.000 BalacingBracketProblem.py:15(push)
      1000000    0.522    0.000    0.522    0.000 BalacingBracketProblem.py:19(pop)
      1500002    0.233    0.000    0.233    0.000 BalacingBracketProblem.py:25(is_empty)
       998355    0.153    0.000    0.153    0.000 BalacingBracketProblem.py:28(get_size)
            1    0.484    0.484    1.249    1.249 BalacingBracketProblem.py:32(balancing_bracket)
      1000000    0.262    0.000    0.262    0.000 BalacingBracketProblem.py:5(__init__)
            1    1.639    1.639    5.739    5.739 BalacingBracketProblem.py:57(create_balanced_string)
      1498232    1.029    0.000    2.411    0.000 random.py:200(randrange)
      1498232    0.606    0.000    3.017    0.000 random.py:244(randint)
      1498232    0.924    0.000    1.382    0.000 random.py:250(_randbelow_with_getrandbits)
            1    0.000    0.000    6.988    6.988 {built-in method builtins.exec}
      1498232    0.148    0.000    0.148    0.000 {method 'bit_length' of 'int' objects}
            1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      2662922    0.310    0.000    0.310    0.000 {method 'getrandbits' of '_random.Random' objects}

    Where we find our run-time on the highlighted line. It is interesting to notice, that the main time is spend creating a string. And diving deeper into that, you can see, that it is the calls to create random integers that are expensive.

    Well, to figure out whether our code is linear in performance, we need to create data points for various input sizes.

    That looks pretty linear, O(n), as expected.

    Good job.

    Python for Finance: Unlock Financial Freedom and Build Your Dream Life

    Discover the key to financial freedom and secure your dream life with Python for Finance!

    Say goodbye to financial anxiety and embrace a future filled with confidence and success. If you’re tired of struggling to pay bills and longing for a life of leisure, it’s time to take action.

    Imagine breaking free from that dead-end job and opening doors to endless opportunities. With Python for Finance, you can acquire the invaluable skill of financial analysis that will revolutionize your life.

    Make informed investment decisions, unlock the secrets of business financial performance, and maximize your money like never before. Gain the knowledge sought after by companies worldwide and become an indispensable asset in today’s competitive market.

    Don’t let your dreams slip away. Master Python for Finance and pave your way to a profitable and fulfilling career. Start building the future you deserve today!

    Python for Finance a 21 hours course that teaches investing with Python.

    Learn pandas, NumPy, Matplotlib for Financial Analysis & learn how to Automate Value Investing.

    “Excellent course for anyone trying to learn coding and investing.” – Lorenzo B.

    Leave a Comment