文字列が与えられた場合、入れ子にされた括弧の深さレベルを計算し、括弧のバランスが合わない場合は-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}
位置に文字を指定し、変数の長さを指定します。var
i
${#var}