2

I would like to create a bash function that, given a string, it count the depth level of nested parentheses, and return -1 if the parentheses are not balanced:


function countNested(){
  str="$1"
  n_left=$(echo $str | grep -o '(' | grep -c '(' )
  n_right=$(echo $str | grep -o ')' | grep -c ')' )
  
  # if the n_left is not equal to n_right return -1
  [[ $n_left -ne n_right ]] && { echo -1; return -1 ; }
  [[ $n_left -ge 1 ]] && echo $((n_left-1))
  [[ $n_left -eq 0 ]] && echo 0
}

When I try it:

countNested '((((((5)))'
# output: -1

countNested '((((((((((((((((5+7))))))))))))))))'
# output: 15

I am using grep two times which seems to be expensive. Any ideas how can I increase the performance of that function?

4
  • how about countNested '(5))(', it returns 1 but the parens aren't actually balanced. You could do that character-by-character with a shell loop, but if you care about performance, you might want to do it with some other tool.
    – ilkkachu
    Dec 10, 2021 at 12:32
  • @ilkkachu: Oh thank you. I was too naive to assume that implementation of that function works correctly. Dec 10, 2021 at 12:34
  • Probably I would need also to check if the string ends with an opening parentheses and vice versa Dec 10, 2021 at 12:35
  • that in itself doesn't help, it could be (5))(() which again has an equal number of both (and would be valid with an extra pair of surrounding parens!), but which isn't valid.
    – ilkkachu
    Dec 10, 2021 at 12:42

2 Answers 2

4

You could do the check character-by-character, that'd let you detect cases where there is a right parenthesis without the corresponding left one. You could do it Bash, but if you care about performance, some other tool is probably better. E.g. with awk:

$ cat parens.awk
#!/usr/bin/awk -f
{
    n = 0;
    max = 0;
    for (i = 1; i <= length($0); i++) {
        c = substr($0, i, 1);
        if (c == "(") n++;
        if (c == ")") n--;
        if (c == ")" && n < 0) {
            printf "mismatching right parenthesis at position %d\n", i > "/dev/stderr";
            exit 1;
        }
        if (n > max) max = n;
    }
    if (n != 0) {
        printf "%d left parentheses left unclosed\n", n > "/dev/stderr";
        exit 1;
    }
    # maximum nesting level
    printf "%d\n", max;   
    exit 0;
}

The output is just the maximum nesting level, or a message to stderr if the input is invalid:

$ echo '((5))' | awk -f parens.awk 
2
$ echo '((5)' | awk -f parens.awk 
1 left parentheses left unclosed
$ echo '((5)))' | awk -f parens.awk 
mismatching right parenthesis at position 6
$ echo '(5))(' | awk -f parens.awk 
mismatching right parenthesis at position 4
$ echo '((5)(6))' | awk -f parens.awk 
2
$ echo '((5)))' | awk -f parens.awk 
mismatching right parenthesis at position 6

Also, the exit status is one on error, so you can also do:

if ! level=$( echo '((5)))' | awk -f parens.awk 2>/dev/null); then
    echo invalid parenthesis
fi

(Or just remove the prints for the error messages if you don't care about them.)

If you want to do it in Bash, ${var:i:1} gives the character in var at position i, ${#var} gives the length of the variable.

5
  • When I run it with ))( I get a wrong error message Dec 10, 2021 at 12:52
  • mismatching right parenthesis at position 1 mismatching right parenthesis at position 2 mismatching right parenthesis at position 3 -1 left parentheses left unclosed Dec 10, 2021 at 12:53
  • @OK-Validation, ah, yes of course, it should only print that if the current character is ), not when going back "up" from negative. Fixed. Though I'm not sure if it's even that useful to print all mismatched right parens, rather than just note the error once.
    – ilkkachu
    Dec 10, 2021 at 13:01
  • with (() I get 1 left parentheses left unclosed maximum nesting level 2 it shouldn't print the maximum nesting level2 since it is not balanced Dec 10, 2021 at 13:06
  • @OK-Validation, well, yes, it might be better to just exit with an error
    – ilkkachu
    Dec 10, 2021 at 13:17
4

With bash's own pattern matching operators, you could do something like:

shopt -s extglob
count_nested() {
  local string="$1" new count=0
  until
    new=${string//'('*([^'()'])')'}
    [[ "$string" = "$new" ]]
  do
    string=$new
    (( ++count ))
  done
  case $string in
    (*['()']*) echo -1; false;;
    (*)        echo "$count";;
  esac
}

That is work your way from the inside out removing the inner (...) pairs first and stop when there are no matched parens left.

To remove the inner (...), we use the ${param//pattern[/replacement]} replacement operator from ksh93 here with a pattern using ksh extended operators (a subset of which is enabled in bash with the extglob option): '('*([^'()'])')'.

That matches on ( followed by 0 or more *(...) characters other than ( or ) ([^'()']) followed by ).

So that's a (...) that doesn't contain (/).

The (s and )s need to be quoted as they're otherwise special in the shell's syntax. To make it more legible, you can store the pattern in a variable:

local pattern='(*([^()]))'
...
new=${string//$pattern}

Having it in a variable also avoids problems when the function is parsed (let alone run) when the extglob option is not enabled. It then allows you to set that option from within the function, possibly in a subshell so it's confined there¹:

count_nested() (
  shopt -s extglob
  string="$1" count=0 pattern='(*([^()]))'
  until
    new=${string//$pattern}
    [[ "$string" = "$new" ]]
  do
    string=$new
    (( ++count ))
  done
  case $string in
    (*['()']*) echo -1; false;;
    (*)        echo "$count";;
  esac
)

(note the body of the function is now a (...) subshell instead of a {...;} command group).


¹ as bash has no local scope support for its set of options set with shopt yet. Also beware its subshells are implemented by forking a child process, so that makes it less efficient.

5
  • Thank you. I don't understand this substitution; what is substituted by what ${string//'('*([^'()'])')'} Dec 10, 2021 at 13:19
  • @OK-Validation see edit Dec 10, 2021 at 13:23
  • I think I understand now. But honestly the part that confused me at the beginning was {var//foo} I was interpreting // as g in sed so I was wondering what is the replacement. So finally I understand it as sed /pattern// Dec 10, 2021 at 13:33
  • One last question: Is it possible to turn on the extended globbing inside the function at the beginning then disable it again when the function quits? Dec 10, 2021 at 13:39
  • @OK-Validation see edit Dec 10, 2021 at 13:59

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.