☰

중첩된 괄호 수를 계산하는 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을 두 번 사용했는데 비용이 많이 드는 것 같습니다. 이 기능의 성능을 향상시키는 방법에 대한 아이디어가 있습니까?

답변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}

변수에 넣으면 함수가 실행될 때 문제가 발생하지 않습니다.에프(실행은 물론이고) 이 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. 또한 하위 쉘은 하위 프로세스를 포크하여 구현되므로 효율성이 떨어집니다.

관련 정보