☰

入れ子の括弧数を計算する Bash 関数

tag-icon • tag-icon bash function
入れ子の括弧数を計算する Bash 関数

文字列が与えられた場合、入れ子にされた括弧の深さレベルを計算し、括弧のバランスが合わない場合は-1を返すbash関数を作成したいと思います。


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
}

私が試したとき：

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

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

grepを2回使ったのにコストがかかるようです。この機能のパフォーマンスを向上させる方法についてのアイデアはありますか？

答え1

文字ごとに確認できるので、対応する開け括弧なしで閉じ括弧がある場合を検出できます。 Bashを使用してこれを行うことができますが、パフォーマンスに興味がある場合は、他のツールがより良いかもしれません。たとえば、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;
}

出力は、最大ネストされたレベル、または入力が無効な場合はstderrへのメッセージです。

$ 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

また、終了状態はエラー状態なので、次のこともできます。

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

print（またはエラーメッセージに興味がない場合は削除してください。）

Bashでこれを行うには、${var:i:1}位置に文字を指定し、変数の長さを指定します。vari${#var}

答え2

bash独自のパターン一致演算子を使用すると、次のことができます。

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
}

これは内側から外側に機能し、(...)最初に内側のペアを削除してから、一致する括弧がない場合は停止します。

内部を削除するために、(...)ここではksh93の代替演算子とksh拡張演算子（${param//pattern[/replacement]}オプションで有効になっているサブセット）を使用するパターンを使用します。bashextglob'('*([^'()'])')'

次に一致する文字(は0個以上で*(...)、(または)（[^'()']）ではありません)。

だからこれは/(...)がないことです。()

s(と)sはシェル構文で特別なので、引用符で囲む必要があります。より明確にするために、パターンを変数に保存できます。

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

変数に入れると、関数の実行時に問題は発生しません。F（実行はもちろん）このextglob オプションが有効になっていない場合。その後、関数内で（おそらくサブシェルで）オプションを設定できるため、そのオプションは次のように制限されます。

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
)

（関数の本文はコマンドグループでは(...)なくサブシェルです。）{...;}

¹bashまだ設定されているオプションセットのローカルスコープサポートを提供していませんshopt。また、サブシェルはサブプロセスをフォークして実装されるため、効率が悪くなります。

関連情報