![Bash 函数计算嵌套括号的数量](https://linux22.com/image/199532/Bash%20%E5%87%BD%E6%95%B0%E8%AE%A1%E7%AE%97%E5%B5%8C%E5%A5%97%E6%8B%AC%E5%8F%B7%E7%9A%84%E6%95%B0%E9%87%8F.png)
我想创建一个 bash 函数,给定一个字符串,它计算嵌套括号的深度级别,如果括号不平衡则返回 -1:
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 两次,这似乎很昂贵。有什么想法可以提高该功能的性能吗?
答案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}
答案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]}
启用):。bash
extglob
'('*([^'()'])')'
匹配 on(
后跟 0 个或多个*(...)
字符,而不是(
or )
( [^'()']
) 后跟)
。
所以这是一个(...)
不包含(
/的 a )
。
s(
和)
s 需要用引号引起来,因为它们在 shell 语法中很特殊。为了使其更清晰,您可以将模式存储在变量中:
local pattern='(*([^()]))'
...
new=${string//$pattern}
将其放在变量中还可以避免函数运行时出现问题解析的(更不用说运行)当该extglob
选项未启用时。然后,它允许您在函数内(可能在子 shell 中)设置该选项,因此它被限制在那里:
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
)
(请注意,函数主体现在是(...)
子 shell,而不是{...;}
命令组)。
¹ asbash
尚未对其设置的选项集提供本地范围支持shopt
。另请注意,它的子 shell 是通过分叉子进程来实现的,因此效率较低。