올바른 괄호 문자열(올바른 괄호 문자열)에는 여러 가지 정의가 있습니다.

1) 비형식적 정의

올바른 괄호 문자열은 산술식에서 괄호를 제외한 모든 것을 제거하여 얻어지는, 여는 괄호와 닫는 괄호로 이루어진 문자열입니다.

예를 들어, 식 $(1 + 2) * (3 + 100 * (3 / 2))$에서는 올바른 괄호 문자열 $()(())$이 얻어집니다. 반면 $)(())$는 어떤 식에서도 얻을 수 없습니다.

2) 명시적 정의

올바른 괄호 문자열이란 여는 괄호와 닫는 괄호로 이루어진 문자열로서, 모든 괄호를 쌍으로 나눌 수 있으며, 각 쌍에서 첫 번째 괄호는 여는 괄호이고 두 번째 괄호는 닫는 괄호이며, 여는 괄호가 닫는 괄호보다 앞에 오고, 어떤 두 쌍도 서로 교차하지 않는 문자열입니다.

예를 들어 $((())())$는 올바른 괄호 문자열입니다. 다음과 같이 서로 겹치지 않는 쌍으로 나눌 수 있기 때문입니다: $\textbf{(}\underline{(}\overline{(}\overline{)}\underline{)}\textit{()}\textbf{)}$. 반면 문자열 $(()$는 쌍으로 나눌 수 없습니다. 괄호의 개수가 홀수이기 때문입니다.

3) 재귀적 정의

  • 빈 문자열은 올바른 괄호 문자열입니다
  • $A$가 올바른 괄호 문자열이면 $(A)$도 올바른 괄호 문자열입니다
  • $A$와 $B$가 올바른 괄호 문자열이면 $AB$도 올바른 괄호 문자열입니다

예를 들어, 빈 문자열은 올바른 괄호 문자열이므로 $()$도 올바른 괄호 문자열이고, 따라서 $(())$도 올바른 괄호 문자열이며, 따라서 $(())()$도 올바른 괄호 문자열이고, 따라서 $((())())$도 올바른 괄호 문자열입니다. 반면 $())(()$는 이 규칙들로는 결코 만들 수 없습니다.

4) 균형을 통한 정의: 올바른 괄호 문자열은 여는 괄호와 닫는 괄호로 이루어진 문자열입니다. 길이가 $n$인 접두사에서의 **균형**을 그 접두사에 있는 여는 괄호의 개수와 닫는 괄호의 개수의 차이로 정의합시다. 그러면 올바른 괄호 문자열에서는 다음 두 가지 성질이 성립해야 합니다:

  • 모든 균형은 0 이상입니다
  • 전체 문자열의 균형은 0입니다

즉, 어떤 접두사에서도 여는 괄호의 수가 닫는 괄호의 수보다 적지 않으며, 문자열 전체에서는 그 수가 같습니다.

문자열이 올바른 괄호 문자열인지 판별할 때는 바로 이 마지막 정의를 사용하는 것이 편리합니다. 즉, 문자열을 왼쪽에서 오른쪽으로 훑으면서 여는 괄호를 만나면 $+1$을, 닫는 괄호를 만나면 $-1$을 더해 나갑시다. 그리고 균형 값이 항상 음수가 아니고 마지막에 0이 되는지만 확인하면 충분합니다.

서로 다른 종류의 괄호로 이루어진 올바른 괄호 문자열도 정의할 수 있습니다. 예를 들어, $([](\{\}))$은 올바른 괄호 문자열이지만, $[(])$은 그렇지 않습니다. 명시적 정의에는 한 쌍을 이루는 괄호가 같은 종류여야 한다는 조건만 추가하면 됩니다. 재귀적 정의에는 모든 종류의 괄호에 대해 “$A$가 올바른 괄호 문자열이면, $[A]$도 올바른 괄호 문자열이다"와 같은 형태의 규칙을 추가해야 합니다.

하지만 균형을 이용한 정의는 이렇게 쉽게 일반화되지 않습니다. 그런데 올바른 괄호 문자열인지 확인하는 알고리즘에 쓰려는 것이 바로 이 정의입니다. 이를 확장하려면 스택을 사용해야 합니다.

올바른 괄호 문자열이란 여러 종류의 여는 괄호와 닫는 괄호로 이루어진 문자열로서, 문자열을 따라가며 열린 괄호의 스택을 만들 때 오류가 발생하지 않고 마지막에 스택이 비어 있는 문자열입니다. 구체적으로 말하면, 빈 스택을 하나 만들고 문자열을 왼쪽에서 오른쪽으로 훑으면서 여는 괄호를 만나면 스택의 끝에 넣고, 닫는 괄호를 만나면 스택에서 꺼냅시다. 이때 꺼내는 여는 괄호가 만난 닫는 괄호와 같은 종류인지 확인해야 합니다.

예를 들어, 문자열 $\{[([])()]{}\}$을 봅시다. 알고리즘이 진행되는 동안 스택은 다음과 같이 변합니다:

  • 비어 있음
  • $\{$
  • $\{[$
  • $\{[($
  • $\{[([$
  • $\{[($ - 제거됨, $[$은 $]$와 짝이 맞습니다
  • $\{[$ - 제거됨 $($ 짝이 맞음 $)$
  • $\{[($
  • $\{[$ - 제거됨 $($ 짝이 맞음 $)$
  • $\{$ - 제거된 괄호 $[$ 짝이 맞습니다 $]$
  • $\{\{$
  • $\{$ - 제거된 괄호 $\{$는 $\}$와 짝이 맞습니다
  • 비어 있음 - 꺼낸 $\{$가 $\}$와 짝이 맞습니다

꺼낸 괄호는 모두 만난 닫는 괄호와 짝이 맞았고, 마지막에 스택이 비어 있습니다

  • 따라서 이것은 올바른 괄호 문자열입니다.

반면 문자열 $[ \{ ] \}$은 올바른 괄호 문자열이 아닙니다:

  • 비어 있음
  • $[$
  • $[ \{$
  • 오류입니다. 스택 끝의 $\{$는 $]$와 짝이 맞지 않기 때문입니다.

이 알고리즘은 $O(N)$에 동작합니다. 배열을 한 번 순회하면서 매번 스택 연산 중 하나, 즉 push 또는 pop 중 하나만 수행하기 때문입니다.