Counting nested braces

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

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

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

See Working with matched portions chapter from my Understanding 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

See my Perl One-Liners Guide ebook if you are interested in learning to use Perl from the command-line.

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