스택으로 검증하는 괄호 문자열: 불변조건부터 실제 파서까지

이 글의 시각적 출발점은 Instagram의 괄호 검증 포스트입니다. 원본 캡션을 옮기거나 이미지·영상·코드 자산을 사용하지 않았습니다. 아래 보드와 설명은 스택 불변조건, 입력 계약, 오류 처리까지 직접 검증할 수 있도록 독립적으로 다시 구성했습니다.

먼저 결론

유효한 괄호 문자열은 여는 괄호와 닫는 괄호의 개수만 같은 문자열이 아니다. 왼쪽부터 어느 지점까지 읽어도 닫는 괄호가 아직 열리지 않은 종류를 요구해서는 안 되고, 가장 최근에 열린 괄호부터 닫혀야 하며, 끝에는 미해결 여는 괄호가 없어야 한다.

스택은 이 세 조건을 하나의 상태로 표현한다.

입력의 어떤 prefix를 처리한 뒤에도 스택에는 아직 닫히지 않은 여는 괄호에 대응하는 기대 닫는 괄호가 쌓여 있고, 맨 위에는 바로 다음에 와야 할 닫는 괄호가 있다.

이 불변조건을 유지하면 구현은 한 번의 순회로 끝난다. 시간은 O(n), 추가 공간은 현재 중첩 깊이 d에 대해 O(d), 최악에는 O(n)이다.

보드는 strict 모드에서 여는 괄호 자체 대신 앞으로 와야 할 닫는 괄호를 push한다. 각 문자를 읽을 때 그 기대값 스택이 어떻게 변하는지 보여준다. 애니메이션은 직관을 돕지만 정답의 근거는 색이나 속도가 아니라 위 불변조건과 아래의 종료 조건이다.

먼저 입력 언어를 정한다

“괄호가 유효한가?”라는 질문은 다른 문자를 어떻게 처리할지 정하기 전에는 완전하지 않다. 이 글에서는 두 모드를 구분한다.

알고리즘 문제의 기본값은 strict가 안전하다. embedded는 로그나 단순 표현식에서 구조 괄호만 훑을 때 쓸 수 있지만, 실제 프로그래밍 언어에서는 문자열·주석 안의 괄호가 구조 문자가 아니므로 단순히 모든 비괄호 문자를 무시하는 것만으로는 충분하지 않다.

괄호 토큰만의 문법은 다음처럼 쓸 수 있다.

S → ε | SS | (S) | [S] | {S}

ε는 빈 문자열이다. 따라서 이 계약에서는 빈 입력을 유효하다고 본다. 제품 요구가 “적어도 한 쌍이 있어야 한다”라면 문법과 최종 조건에 그 요구를 별도로 추가해야 한다.

코드 흐름을 불변조건에 맞춰 읽기

보드가 사용하는 검증 흐름은 다음 여덟 단계로 이해할 수 있다.

1. 여는 괄호를 앞으로 기대할 닫는 괄호로 매핑한다: (→), [→], {→}.
2. 기대하는 닫는 괄호를 담을 빈 스택을 만든다.
3. 입력을 왼쪽에서 오른쪽으로 한 번 순회한다.
4. 여는 괄호를 만나면 대응하는 닫는 괄호를 스택에 push한다.
5. 닫는 괄호를 만나면 스택 맨 위를 pop해 현재 문자와 비교한다.
6. 스택이 비어 있었거나 pop한 기대값이 현재 문자와 다르면 즉시 false다.
7. 다른 문자는 strict에서는 false, embedded에서는 건너뛴다.
8. 끝까지 실패하지 않았고 스택이 비어 있을 때만 true다.

닫는 괄호에서 먼저 맨 위와 비교한 뒤 pop해도 결과는 같다. 중요한 것은 빈 스택을 안전하게 처리하고, 중간 불일치를 발견한 뒤 계속 진행하지 않는 것이다. 잘못된 prefix는 뒤 문자를 더 읽어도 유효해질 수 없다.

왜 맞는가: 세 단계 증명

초기화

아무 문자도 읽지 않은 prefix에는 미해결 여는 괄호가 없다. 빈 스택이 불변조건을 만족한다.

유지

• 여는 괄호를 읽으면 그 괄호의 짝이 다음에 해결해야 할 가장 최근 항목이므로 대응하는 닫는 괄호를 push하는 것이 정확하다.
• 닫는 괄호를 읽으면 올바른 중첩에서 반드시 스택 맨 위의 기대값과 같아야 한다. 맨 위가 없거나 종류가 다르면 현재 prefix는 어떤 suffix를 붙여도 복구할 수 없다.
• 정책상 무시하는 문자는 괄호 구조를 바꾸지 않으므로 embedded 모드의 스택 상태를 유지한다.

종료

순회를 통과했다는 것은 모든 닫는 괄호가 올바른 맨 위 항목과 짝을 이뤘다는 뜻이다. 스택까지 비었다면 모든 여는 괄호도 닫혔다. 반대로 스택에 항목이 남으면 닫히지 않은 괄호가 있으므로 거짓이다.

이 증명은 단순한 개수 세기가 놓치는 두 반례도 설명한다.

• (]는 여는 괄호와 닫는 괄호 수가 같지만 종류가 다르다.
• )(는 괄호 수가 같아도 첫 prefix부터 닫는 괄호가 앞선다.

복잡도는 중첩 깊이로 더 정확히 쓴다

입력 길이를 n, 최대 중첩 깊이를 d라고 하자.

• 각 문자는 한 번 읽고, 각 괄호는 최대 한 번 push와 한 번 pop된다. 시간은 O(n)이다.
• 스택에는 동시에 최대 d개의 기대 닫는 괄호가 있으므로 추가 공간은 O(d)다.
• ((((...처럼 모두 열리는 입력에서는 d=n이어서 최악 공간은 O(n)이다.
• 짝이 바로 닫히는 ()()()...에서는 d가 1이므로 스택 공간은 상수에 가깝다.

세 종류의 괄호 매핑은 크기가 고정되어 있으므로 조회를 O(1)로 본다. 괄호 종류가 runtime에 계속 늘어나는 API라면 mapping 크기와 lookup 자료구조도 계약에 포함해야 한다.

Unicode와 “무시할 문자” 정책

JavaScript의 index 접근은 UTF-16 code unit 기준이지만 for...of는 Unicode code point 단위로 순회한다. 이 문제의 구조 토큰은 ASCII 여섯 글자라 둘 다 괄호 자체를 찾는 데는 문제가 없지만, 오류 위치와 무시 정책에서는 차이가 생긴다.

• fullwidth （와 ）는 ASCII (, )가 아니므로 기본 계약에서는 괄호로 취급하지 않는다.
• emoji처럼 surrogate pair인 문자를 strict에서 오류로 보고 위치를 표시할 때 code unit offset과 화면상의 문자 위치를 구분해야 한다.
• NFKC 정규화로 모양이 비슷한 문자를 조용히 ASCII로 바꾸면 식별자·보안 의미까지 달라질 수 있다. 지원하려면 허용 목록 기반의 명시적 전처리로 둔다.
• embedded 모드에서 “다른 문자를 모두 무시”한다는 결정은 공백만 허용하는 결정과 다르다. API 이름과 문서에서 범위를 드러낸다.

실제 서비스에서는 boolean 하나보다 { valid, index, expected, actual, depth } 같은 진단 결과가 유용하다. 이때 index가 byte, UTF-16 code unit, code point 중 무엇인지도 명시해야 한다.

경계 사례 테스트

마지막 두 행이 embedded 모드의 한계를 보여준다. “구조를 검증했다”가 아니라 “ASCII 괄호 subsequence를 검증했다”가 정확한 표현이다.

단위 테스트 외에도 다음 성질을 생성형 테스트로 확인할 수 있다.

• 유효한 문자열 a와 b를 이어 붙인 ab는 유효하다.
• 유효한 문자열 a를 같은 종류의 괄호로 감싼 결과는 유효하다.
• 검증기가 true를 반환하면 세 종류의 여는·닫는 개수는 각각 같다.
• reference grammar로 만든 작은 문자열과 검증기 결과가 일치한다.
• 최대 길이와 최대 깊이 제한 직전·직후에서 명시한 오류가 난다.

개수 일치는 필요조건일 뿐 충분조건이 아니므로 마지막에서 두 번째 성질의 역은 테스트 oracle로 쓰면 안 된다.

운영 입력이라면 깊이 제한도 계약이다

O(n) 알고리즘도 공격자가 수천만 개의 여는 괄호를 보내면 memory와 CPU를 소모한다. API나 editor service라면 다음을 함께 둔다.

• 최대 byte 또는 code point 길이
• 최대 중첩 깊이
• streaming 입력의 시간·크기 제한
• 실패 위치까지만 보존하는 bounded diagnostic

streaming validator는 chunk 사이에 스택을 유지하면 된다. 단, UTF-8 byte chunk를 직접 받는다면 decoder가 잘린 code point를 다음 chunk와 안전하게 합친 뒤 validator에 넘겨야 한다.

실제 parser로 확장할 때 달라지는 것

괄호 스택은 parser의 한 구성요소이지 parser 전체가 아니다.

1. lexer를 먼저 둔다. 문자열 literal, escape, line/block comment를 token으로 분리하면 그 안의 괄호를 구조에서 제외할 수 있다.
2. 위치를 저장한다. 스택에 괄호 종류뿐 아니라 line과 column을 넣으면 “어디서 열린 괄호가 닫히지 않았는가”를 알려줄 수 있다.
3. 문법별 상태를 둔다. <와 >는 언어에 따라 비교 연산자, generic, HTML tag가 될 수 있어 문자 하나만으로 결정할 수 없다.
4. 오류 복구를 설계한다. editor parser는 첫 오류에서 끝내기보다 동기화 token까지 이동해 여러 진단을 내야 한다.
5. resource limit을 유지한다. 재귀 descent parser라면 call stack 제한도 명시적 스택과 함께 고려한다.

핵심 아이디어는 그대로 남는다. 가장 최근에 열린 구조부터 닫힌다는 문법에서는 스택이 자연스러운 상태 표현이다. 좋은 구현은 이 사실을 외우는 데서 끝나지 않고, 어떤 문자를 구조로 인정하는지와 실패를 어떻게 설명하는지까지 계약으로 만든다.