I posted a coding challenge in the fifth issue of learnbyexample weekly. I discuss the problem and Python/Perl solutions in this blog post.


Problem statement🔗

Write a function that returns the maximum nested depth of curly braces for a given string input. For example:

  • 'a*{b+c}' should return 1
  • '{{a+2}*{{b+{c*d}}+e*d}}' should return 4
  • unbalanced or wrongly ordered braces like '{{a}*b' and '}a+b{' should return -1

Python solution🔗

Here's one possible solution for this problem:

def max_nested_braces(expr):
    max_count = count = 0
    for char in expr:
        if char == '{':
            count += 1
            if count > max_count:
                max_count = count
        elif char == '}':
            if count == 0:
                return -1
            count -= 1

    if count != 0:
        return -1
    return max_count

info In case you have trouble understanding the above code, you can use pythontutor to visualize the code execution step-by-step.

Here's an alternate solution using regular expressions:

import re

def max_nested_braces(expr):
    count = 0
    while True:
        expr, no_of_subs = re.subn(r'\{[^{}]*\}', '', expr)
        if no_of_subs == 0:
            break
        count += 1

    if re.search(r'[{}]', expr):
        return -1
    return count

And if you are a fan of assignment expressions:

import re

def max_nested_braces(expr):
    count = 0
    while (op := re.subn(r'\{[^{}]*\}', '', expr)) and op[1]:
        expr = op[0]
        count += 1

    if re.search(r'[{}]', expr):
        return -1
    return count

info I verified these solutions using assert statements. See Testing chapter from my 100 Page Python Intro ebook for more details.

info See Working with matched portions chapter from my Python re(gex)? ebook for more details about the re.subn() function.


Perl one-liner🔗

Here's a solution for CLI enthusiasts:

$ cat ip.txt 
{a+2}*{b+c}
{{a+2}*{{b+{c*d}}+e*d}}
a*b{
{{a+2}*{{b}+{c*d}}+e*d}}

$ perl -lne '$c=0; $c++ while(s/\{[^{}]*\}//g);
             print /[{}]/ ? -1 : $c' ip.txt
1
4
-1
-1

info See my Perl one-liners ebook if you are interested in learning to use Perl from the command-line.

info If you are interested in awk and bash solutions, see this unix.stackexchange thread.