主页 / unix / 问题 / 680920
Accepted
Algerian_Amazigh_05
Asked: 2021-12-11 04:30:02 +0800 CST

Bash函数来计算嵌套括号的数量

  • 772

我想创建一个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 两次，这似乎很昂贵。有什么想法可以提高该功能的性能吗？

bash function

2 个回答

  1. Best Answer

    您可以逐个字符地进行检查，这样您就可以检测出有右括号而没有相应的左括号的情况。您可以使用 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（或者如果您不关心错误消息，只需删除s 即可。）

    如果你想在 Bash 中做，在位置给出${var:i:1}字符，给出变量的长度。vari${#var}

    • 4

  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
}

    那就是从内到外(...)先删除内部对，然后在没有匹配的括号时停止。

    要删除内部(...)，我们在${param//pattern[/replacement]}此处使用 ksh93 中的替换运算符和使用 ksh 扩展运算符的模式（其中的一个子集bash通过选项启用）extglob：'('*([^'()'])')'

    匹配 on(后跟 0 个或多个字符*(...)，而不是( ) 后跟.()[^'()'])

    所以这是一个(...)不包含(/的)。

    (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，而不是一个{...;}命令组）。

    ¹ as尚未bash对其设置的一组选项提供本地范围支持shopt。还要注意它的子shell是通过分叉一个子进程来实现的，这样会降低效率。

    • 4

相关问题